11

语境

我正在使用程序生成构建 3d 游戏。我正在尝试以这样一种方式连接多个预先生成的房间，即无论如何，玩家总是可以到达地图中的任何其他房间。房间有“可能的入口点”，连接走廊必须连接到这些入口点。但是，并非所有入口点都可以从房间内的所有其他入口点到达。例如，可能有一个坑陷阱，因此位于底部的玩家将无法穿过房间到达顶部，而必须另谋出路。

问题

给定一组嵌入在 3d 空间中的预先存在的有向图，添加一组总长度最小的（双向）路径，将子图连接成更大的图。做不到这一点（因为一些研究表明这是 NP-Hard）使路径尽可能短，以便在短时间内计算。

工作至今

我最好的解决方案是基于这个程序生成帖子，他在其中创建了所有节点的德莱尼三角剖分。我将房间的每个强连接组件（例如陷阱的顶层和底层）视为单独的节点，并以此构建 MST，但这限制了一些更有趣的可能性（例如，必须通过两条单向路径返回您开始的位置）。

有谁知道解决这个问题的更好方法？

4

2 回答 2

1

也许您可以更好地利用您正在建模 3d 空间这一事实。这意味着您可以将问题划分为一组平面图，每个平面图代表不同的楼层。您可以从将每个楼层构建为紧密连接开始。然后当你加入楼层时（可能只有几个楼梯和陷阱），通过移除一些边来扰乱解决方案，同时仍然保持整体强连接图。移除边缘的有趣选择是那些会导致地板本身失去强连通性但在考虑其他地板时保持属性的选择。这些被称为桥梁，并且有一种线性算法可以找到它们。

如果您只计算边而不是它们的长度，那么孤立地求解平面图（楼层）会将其转换为多个欧几里德斯坦纳树问题，虽然仍然是 NP-hard，但可以使用接近最优的多项式时间逼近方案来解决. 但是，您提到您希望最小化路径的总长度，这使得这是一个直线施泰纳树问题。由于它适用于电路设计，因此对这个问题进行了很多 研究。存在的近似值可以达到最佳值的 1.5 倍，这可能更适合您正在做的事情：稍微长一点的走廊而不是一个地方的所有入口。

于 2014-03-26T19:23:06.400 回答
0

这个问题的嵌入部分使它变得非常混乱，所以我将假设我们估计连接成本以获得有向图，我们想要一个最小成本的强连接弧子图。然后只需使用贪心算法找到嵌入。

对于多项式时间内的 2 近似解：选择任意根顶点，然后使用Chu--Liu 和 Edmonds 的算法来计算最小成本的根向和叶向跨越树状结构。返回这些的并集。这是一个 2 近似值，因为每个强连接弧子图都包含一个根向和叶向跨越树状结构（尽管不一定具有最低成本）。我现在从您的一个链接中看到 Keith Randall 也有这个想法。

您可以实施任意数量的启发式方法。它们可能工作得很好，但它们并不是我真正感兴趣的。如果您担心它们表现不佳，那么您可以使用前面提到的 2 近似值“支持”它们。

如果您真的想要一个最佳解决方案，那么您最好的选择可能是整数规划。这个问题被表述为一个整数规划，与 TSP 有一些相似之处。TSP 的程序如下所示。

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
(-) for all v, sum_{v -> w} x(v -> w) = 1
(-) for all w, sum_{v -> w} x(v -> w) = 1
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

对于您的问题程序，我们删除了标记为 的约束(-)，这将强制选择的弧为游览。

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

该程序的对偶如下。

maximize sum_{subsets S of vertices} y(S)
subject to
for all v -> w, sum_{subsets S of vertices, v in S, w not in S} y(S) <= cost(v -> w)
for all subsets S of vertices, y(S) >= 0

现在我们可以为 TSP 调整分支定界解决方案，那里应该有大量的教程材料。您不必做任何根本上新的事情；事实上，您可以专注于生成子旅游约束/变量，因为梳状不等式等不适用于这个问题。

于 2014-03-26T16:58:39.343 回答