algorithm - 坐在电影院里的人

Question

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

一般问题:

什么算法可以让人们在电影院里就座，让他们直接坐在 friend 旁边而不是敌人旁边。

技术问题:

给定一个 N×M 的网格，用 N * M - 1 项填充网格。每个项目对于其他 N * M - 2 个项目中的每一个都有一个关联 bool 值。在 N 的每一行中，直接位于其他项目旁边的项目应该与其他项目具有正关联值。然而，列并不重要，即一个项目可以是它前面的项目的“敌人”。 注意:如果项目 A 对 B 具有正关联值，则意味着 B 对 A 也具有正关联值。对于负关联值，它同样适用。一个项目保证与至少一个其他项目有正相关。 此外，在开始将它们放入网格之前，您可以访问所有项目及其关联值。

评论:

从昨天开始我一直在研究和思考这个问题，从我发现它让我想起了bin packing problem有一些额外的要求。在一些空闲时间我试图实现它，但是一大群“敌人”坐在一起。我敢肯定，大多数情况下都必须至少有一对坐在一起的敌人，但我的解决方案远非最佳。它实际上看起来好像我刚刚随机化了它。

就我的实现而言，我让 N = 10，M = 10，项目数 = 99，并且每个项目都有一个大小为 99 的数组，每个项目都有一个随机 bool 值，表示友谊相应的项目编号。这意味着每个项目都有一个与他们自己相对应的友谊值，我只是忽略了那个值。

我计划稍后再次尝试重新实现它，我会发布代码。谁能想出一个“好”的方法来减少敌人之间的座位冲突？

Answer 1

这个问题是NP-Hard .
定义 L={(G,n,m)|如果 u 是 v 的 friend ，则 G 在 m×m 矩阵中有一个合法位置，(u,v) 在 E 中 L 是一个正式的将这个问题定义为一种语言。

证明:
我们将在 2 个步骤中显示 Hamiltonian-Problem ≤ (p) 2-path ≤ (p) This-problem [Hamiltonian 和 2-path defined below]，因此我们得出结论这个问题是 NP-Hard .

(1) 我们将证明找到覆盖所有顶点的两条路径而不使用任何顶点两次是 NP-Hard [让我们称这样的路径为:2 路径，并将此问题称为 2 路径问题]
从 Hamiltonian Path problem 减少:

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

正确性:

• 如果 G 有哈密顿路径:v₁→v₂→...→vn，则 G' 有 2 条路径: v₁→v₂→...→vn,u₀
• 如果 G' 有 2 条路径，因为 u₀ 与其余顶点隔离，所以有 路径:v₁→...→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₁ 坐在 v₂ 旁边，那么 v₁ v₁→v₂ 在路径中，因此 (v₁,v₂) 在 E 中，所以 v₁,v₂ 是 friend 。
• 如果 (G,|V|+1,1) 是合法的席位:[v₁,...,vk,buffer,vk+1,...,vn] ，则有G 中的 2 路径， v₁→...→vk, vk+1→...→vn

结论:这个问题是NP-Hard的，所以没有已知的多项式解。

指数解: 您可能想使用 backtracking解决方案:基本上是:创建大小为 |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₀ 是缓冲区的垃圾顶点]和边缘的权重函数:

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 , 可以是 solved在 O(|V|^2 * 2^|V|) 中使用动态规划。

请注意，此解决方案 [使用 TSP] 适用于一个排成一排的剧院，但它可能是为一般情况找到解决方案的一个很好的线索。