NP-Complete？带特定约束条件的图形的最优嵌入

Question

6

我有一个基于网格的图形，其中节点和边占据单元格。边可以相交，但不能在同一方向上重叠行驶。

假设我想优化这个图形，使边所覆盖的距离最小化。目前我正在为每个连接使用A*搜索，但该算法是贪婪的，不会提前规划。请考虑下面的图表，其中更改了连接的顺序（还请注意，对于任何给定的边缘，可能存在多条最短路径，例如绿色和紫色的连接）。

我直觉认为这是NP-完全问题，并且需要进行彻底的搜索，随着图形的规模增大，这将非常昂贵。然而，我无法证明这一点，而且它与通常涉及最小化交叉的其他图形嵌入问题并不完全相同。

- ddriver1

这与最小成本多商品流有关，它是NP难问题。虽然我不确定是否存在直接约简。 - templatetypedef

你真的需要“最优”解决方案，还是只需要一个好的解决方案？即使这是NP难问题，许多这样的问题都有易于实现的算法来获得“优秀”的解决方案，而不是最优解。 - phs

理想情况下，我希望确定问题是否确实是NP难的（我将研究它与上面提到的多商品流的关系）。然而，我也对能够提供优秀解决方案的算法感兴趣。 - ddriver1

“边缘覆盖的距离被最小化” - 这句话有歧义。您是指一个或多个边缘覆盖的单元格总数吗？ - j_random_hacker

@j_random_hacker 很好的观点。覆盖的距离是以每个单独连接的长度为单位的。这与您的描述不同，这意味着包含两个交叉边的单元格不会比只有一个边的单元格更昂贵。为了明确起见，当我使用我的A*算法时，对于从一个单元格到下一个单元格的每个连续“步骤”，连接的成本增加1。 - ddriver1

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tmyklebu · Answer 1

您并没有详细描述您的问题，而且您的图片已经消失了，但是您的问题听起来像是最小T-联通问题。

最小T-联通问题是在一个图G上定义的。您会得到一个偶数大小的集合T，并试图找到一个子图，其中T的顶点具有奇数度数，其他顶点具有偶数度数。您的边缘上有权重，并且您正在尝试将子图中边缘的权重之和最小化。

令人惊讶的是，由于与非二分图匹配问题存在非常密切的联系，因此可以在多项式时间内解决最小T-联通问题。换句话说，如果您在T的顶点之间找到所有对最短路径，则T的最小联通由T中顶点的最小权重完美匹配实现，在G中两个顶点之间有一条边，其长度为最短路径的长度。

最小T-联通将是一组路径。如果两条不同的路径，比如a->b和c->d，使用相同的边缘uv，则它们可以被a->u->c和b->v->d替换，并减少T-联通的成本。所以它不会重复使用相同的边缘。