这是基于文章中，我读到的难题和面试问题问的大型软件企业，但它有一个扭曲......

This is based on an article I read about puzzles and interview questions asked by large software companies, but it has a twist...

常规问题：

什么是算法座位的人在电影院，让他们直接坐在旁边的朋友，但不是旁边自己的敌人。

What is an algorithm to seat people in a movie theater so that they sit directly beside their friends but not beside their enemies.

技术问题：

由于一个N由M网格，填补了网格，N * M - 1项。每一个项目都有每个其他N * M的关联布尔值 - 2项。在N每一行，项目旁边的其他项目应该有其他的正相关值。然而列并不重要，即一个项目可能是敌人，在它前面的项目。 注意：如果项目A对B中的正相关值，则意味着B也有一个正相关值A.它的工作原理是相同的负关联的值。一个项目是为保证为与用于至少一个其他项目正相关。 同时，您可以访问所有的项目及其关联的值开始将它们放置在网格之前。

Given an N by M grid, fill the grid with N * M - 1 items. Each item has an association Boolean value for each of the other N * M - 2 items. In each row of N, items directly beside other items should have a positive association value for the other. Columns however do not matter, i.e. an item can be "enemies" with the item in front of it. Note: If item A has a positive association value for B, then that means B also has a positive association value for A. It works the same for negative association values. An item is guarenteed to have a positive association with atleast one other item. Also, you have access to all of the items and their association values before you start placing them in the grid.

点评：

我一直在研究这个问题，并从昨天开始考虑这件事，从我发现它让我想起了装箱问题的我增加了一些要求。在一些空闲时间，我试图实现它，但大集团的敌人的相邻坐着。我相信，大多数情况下，必须有用于至少一个对敌人坐在旁边给对方的，但我的解决办法是很不理想。实际上，它看起来好像我刚刚随机的。

I have been researching this problem and thinking about it since yesterday, from what I have found it reminds me of the bin packing problem with some added requirements. In some free time I attempted to implement it, but large groups of "enemies" were sitting next to each other. I am sure that most situations will have to have atleast one pair of enemies sitting next to each other, but my solution was far from optimal. It actually looked as if I had just randomized it.

据我实现去了，我做了N = 10，M = 10，项目= 99，并有大小99的每个项目有这样提到的友谊随机布尔值的数组数相应的项目编号。这意味着，每个项目必须与自身对应还有一个友谊的价值，我只是忽略了价值。

As far as my implementation went, I made N = 10, M = 10, the number of items = 99, and had an array of size 99 for EACH item that had a randomized Boolean value that referred to the friendship of the corresponding item number. This means that each item had a friendship value that corresponded with their self as well, I just ignored that value.

我打算尝试稍后重新实现这一次我将张贴code。任何人都可以想出一个好的方式来做到这一点，以尽量减少敌人之间休息冲突？

I plan on trying to reimplement this again later and I will post the code. Can anyone figure out a "good" way to do this to minimize seating clashes between enemies?

推荐答案

这个问题是 NP难。 定义 L = {（G，N，M）|有对于G在米法律座位×M矩阵（U，V）的e。如果u是朋友V} L是这个问题作为一门语言的正式定义。

This problem is NP-Hard. Define L={(G,n,m)|there is a legal seating for G in m×m matrix,(u,v) in E if u is friend of v} L is a formal definition of this problem as a language.

证明： 我们将展示的哈密尔顿问题≤（P）2路≤（P）定义如下汉密尔顿和2路]本-问题 2的步骤，因此，我们得出结论：这个问题是NP难

Proof: We will show Hamiltonian-Problem ≤ (p) 2-path ≤ (p) This-problem in 2 steps [Hamiltonian and 2-path defined below], and thus we conclude this problem is NP-Hard.

（1）我们将证明，发现没有使用任何顶点两次两条路径覆盖所有的顶点是一个NP难[让我们把这样的路径：2路和这个问题，因为2路的问题] 从汉弥尔顿路径问题的减少：

(1) We will show that finding two paths covering all vertices without using any vertex twice is NP-Hard [let's call such a path: 2-path and this problem as 2-path problem] A reduction from Hamiltonian Path problem:

input: a graph G=(V,E)
Output: a graph G'=(V',E) where V' = V U {u₀}.

正确性：

如果G有哈密尔顿路径：V 1→V 2→......→VN，则G'有两个路径： V 1→V 2→......→VN，u₀ 若G'具有2路径中，由于u₀从静止顶点分离，有一个 路径：V 1→......→VN，这是汉密尔顿在G中 if G has Hamiltonian Path: v₁→v₂→...→vn, then G' has 2-path: v₁→v₂→...→vn,u₀ if G' has 2-path, since u₀ is isolated from the rest vertices, there is a path: v₁→...→vn, which is Hamiltonian in G.

因此​​：G有哈密顿路1⇔G'有2个路径，所以：2路的问题是NP难

Thus: G has Hamiltonian path 1 ⇔ G' has 2-path, and thus: 2-path problem is NP-Hard.

（2）现在，我们将证明我们的问题[L]也是NP难： 我们将展示从2路径问题的降低，上述定义

(2)We will now show that our problem [L] is also NP-Hard: We will show a reduction from the 2-path problem, defined above.

input: a graph G=(V,E)
output: (G,|V|+1,1) [a long row with |V|+1 sits].

正确性：

如果G有2路，那么我们就可以坐人，并使用1坐差距 作为一个缓冲的两个路径​​之间使用，这将是一个合法的完美休息 因为如果V 1被坐在旁边的V 2，则V 1 V 1→V 2的路径，从而 （V 1，V 2）是E，所以V 1，V 2是朋友。 如果（G，| V | +1,1）是合法的座椅：[V 1，...，VK，缓冲的，VK + 1，...，VN]，有2路径G中， V 1→......→VK，VK + 1→......→VN If G has 2-path, then we can seat the people, and use the 1 sit gap to use as a 'buffer' between the two paths, this will be a legal perfect seating since if v₁ is sitting next to v₂, then v₁ v₁→v₂ is in the path, and thus (v₁,v₂) is in E, so v₁,v₂ are friends. If (G,|V|+1,1) is legal seat:[v₁,...,vk,buffer,vk+1,...,vn] , there is a 2-path in G, v₁→...→vk, vk+1→...→vn

结论：这个问题是一个NP难，所以不知道多项式解决方案，它

Conclusion: This problem is NP-Hard, so there is not known polynomial solution for it.

指数的解决方案： 您可能要使用回溯的解决方案：这基本上是：建立电子的所有子集与大小| V | -2或更小，检查哪个最好

Exponential solution: You might want to use backtracking solution: which is basically: create all subsets of E with size |V|-2 or less, check which is best.

static best <- infinity
least_enemies(G,used):
  if |used| <= |V|-2:
     val <- evaluate(used)
     best <- min(best,val)
  if |used| == |V|-2: 
     return
  for each edge e in E-used: //E without used 
     least_enemies(G,used + e)

在这里我们假设计算（使用）给出了得分这个解决方案。如果这个解决方案是完全非法的[即顶点出现两次]，评估（使用）=无穷大。当然优化可以被做，修整这些情况。让我们可以存储当前最好的解决方案的实际坐。

in here we assume evaluate(used) gives the 'score' for this solution. if this solution is completely illegal [i.e. a vertex appear twice], evaluate(used)=infinity. an optimization can of course be made, trimming these cases. to get the actual sitting we can store the currently best solution.

（*）可能有更好的解决办法，这仅仅是一个简单可行的解决方案入手，在这个答案的主要目的是的证明的这个问题是NP难。

(*)There are probably better solutions, this is just a simple possible solution to start with, the main aim in this answer is proving this problem is NP-Hard.

编辑：简单的解决方法： 创建一个图 G'=（VU {u₀}，欧盟{（u₀，V），（V，u₀）|在V各自V}） [u₀是垃圾顶点缓冲区]和权重函数的边缘：

simpler solution: Create a graph G'=(V U { u₀ } ,E U {(u₀,v),(v,u₀) | for each v in V}) [u₀ is a junk vertex for the buffer] and a weight function for edges:

w((u,v)) = 1    u is friend of v
w((u,v)) = 2    u is an enemy v
w((u0,v)) = w ((v,u0)) = 0

现在你拥有属于自己的经典 TSP ，它可以是的在 O（| V | ^ 2 * 2 ^ | V |）使用动态规划。

Now you got yourself a classic TSP, which can be solved in O(|V|^2 * 2^|V|) using dynamic programming.

请注意，此解决方案[使用TSP]是一个内衬影院，但它可能是一个不错的领先优势，以寻找一般情况下的解决方案。

Note that this solution [using TSP] is for one lined theatre, but it might be a good lead to find a solution for the general case.