这个问题是
NP-Hard的。定义
L={(G,n,m)|在m×m矩阵中有一个合法的G座位,(u,v)∈E,如果u是v的朋友}
L是该问题的正式语言定义。
证明:
我们将用2步骤展示
哈密顿路径问题 ≤ (p) 2路径问题 ≤ (p) 这个问题 [哈密顿路径和2路径的定义如下],从而我们得出结论,这个问题是NP-Hard的。
(1) 我们将展示找到两条覆盖所有顶点的路径,而不使用任何顶点两次是NP-Hard的[让我们称这样的路径为:2-path问题]
从
哈密顿路径问题进行约简:
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₂是朋友。
- 如果(G,|V|+1,1)是合法的座位:[v₁,...,vk,buffer,vk+1,...,vn],则G中存在2路径,v₁→...→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₀对于缓冲区是一个垃圾顶点]和边的权重函数:
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的解决方案仅适用于单行剧院,但可能是解决通用情况的良好线索。