确保部分连接的有向图连接牢固

Question

上下文

我正在使用程序生成来构建一个3D游戏.我试图连接一些预先生成的房间,无论如何,玩家总能到达地图中的任何其他房间.房间有"可能的入口点",连接走廊必须连接.但是,并非所有入口点都可以从房间内的所有其他入口点到达.例如,可能存在陷阱,因此底部的玩家将无法穿过房间到达顶部,并且必须找到另一种方式.

问题

给定嵌入在3d空间中的一组预先存在的有向图,添加一组最小总长度的(双向)路径,将子图连接成更大的图.如果失败(因为一些研究表明这是NP-Hard),使得路径尽可能短,以便在短时间内计算.

到目前为止工作

我最好的解决方案是基于这个程序生成帖子,他创建了所有节点的Delaney三角剖分.我将房间的每个强连通组件(例如,陷阱的顶层和底层)视为单独的节点,然后构建MST,但这限制了一些更有趣的可能性(例如,必须通过两条单向路径回到你开始的地方).

---

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

Answer 1

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

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

您可以实施许多启发式方法。它们可能工作得很好，但我对它们并不真正感兴趣。如果您担心他们表现不佳，那么您可以使用前面提到的 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 的分支定界解决方案，对此应该有大量的教程材料。你不需要做任何全新的事情；事实上，您可以专注于生成子巡游约束/变量，因为梳状不等式等不适用于此问题。