在电影院里坐人

Question

这是基于我读到的关于大型软件公司提出的谜题和面试问题的文章,但它有一个转折...

一般问题:

什么是算法让人们坐在电影院里,以便他们直接坐在他们的朋友旁边而不是他们的敌人旁边.

技术问题:

给定N×M网格,用N*M-1项填充网格.每个项目具有每个其他N*M-2项目的关联布尔值.在N的每一行中,与其他项目直接相邻的项目应该具有另一项的正关联值.然而,列无关紧要,即一个项目可以与其前面的项目"敌人".注意:如果项目A具有B的正关联值,则表示B也具有A的正关联值.对于负关联值,它的作用相同.保证项目与至少一个其他项目有正面关联.此外,在开始将它们放入网格之前,您可以访问所有项目及其关联值.

评论:

我一直在研究这个问题并从昨天开始考虑它,从我发现它让我想起了包装问题以及一些额外的要求.在一些空闲时间里,我试图实现它,但是大群"敌人"坐在一起.我相信大多数情况都必须至少有一对敌人坐在一起,但我的解决方案远非最佳.它实际上看起来好像我已经随机化了它.

就我的实现而言,我做了N = 10,M = 10,项目数= 99,并且对于每个具有随机布尔值的大小为99的数组,该布尔值引用相应项目编号的友谊.这意味着每个项目都有一个与他们自己相对应的友谊值,我只是忽略了这个值.

我打算稍后再尝试重新实现这个,我会发布代码.谁能想出一个"好"的方法来做到这一点,以尽量减少敌人之间的座位冲突？

Answer 1

这个问题是NP-Hard.
定义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是该问题作为语言的正式定义.

证明:
我们将显示哈密​​顿量问题≤(p)2路径≤(p)这个问题分2步[哈密顿量和2路径定义如下],因此我们得出结论这个问题是NP-Hard.

(1)我们将证明在不使用任何顶点两次的情况下找到覆盖所有顶点的两条路径是NP-Hard [让我们称这样的路径:2路径,这个问题就像2路径问题]
从哈密​​顿路径问题减少:

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

正确性:

• 如果G有哈密顿路径:v 1→v 2→...→vn,那么G'有2路:v 1→v 2→...→vn,u 0
• 如果G'有2路径,由于u 0与其余顶点隔离,有一条路径:v 1→...→vn,在G中是哈密顿量.

因此:G具有哈密顿路径1⇔G'具有2路径,因此:2路径问题是NP-Hard.

(2)我们现在将证明我们的问题[L]也是NP-Hard:
我们将显示上面定义的2路问题的减少.

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,buffer,vk + 1,...,vn],G中有一条2路,v 1→. ..→vk,vk + 1→...→vn

结论:这个问题是NP-Hard,因此没有已知的多项式解.

指数解决方案: 您可能希望使用回溯解决方案:基本上:创建大小为| V | -2或更小的E的所有子集,检查哪个是最佳的.

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)

在这里我们假设evaluate(used)给出了这个解决方案的'得分'.如果此溶液完全非法[即一个顶点出现两次] evaluate(used)=infinity.当然可以进行优化,修剪这些情况.为了获得实际的坐姿,我们可以存储当前最好的解决方案.

(*)可能有更好的解决方案,这只是一个简单的可能的解决方案,这个答案的主要目的是证明这个问题是NP-Hard.

编辑:更简单的解决方案:
创建一个图形G'=(V U { u? } ,E U {(u?,v),(v,u?) | for each v in V})[u 0是缓冲区的垃圾顶点]和边缘的权重函数:

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|)使用动态规划.

请注意,此解决方案[使用TSP]适用于一个带衬里的影院,但它可能是一个很好的导致找到一般情况的解决方案.