我正在使用程序生成构建一个3D游戏。我试图以这样的方式连接一些预先生成的房间，以便无论如何，玩家都可以到达地图中的任何其他房间。房间有“可能的入口点”，连接走廊必须附加到这些点上。然而，并非所有入口点都可以从房间内的所有其他入口点到达。例如，可能会有一个陷阱，因此位于底部的玩家将无法穿过房间到达顶部，必须找到另一种绕路的方法。
给定嵌入在3D空间中的一组预先存在的有向图，添加一组最小总长度的（双向）路径，将子图连接成一个更大的图。如果失败（因为某些研究表明这是NP-Hard），则使路径尽可能短，以在短时间内计算出来。
有没有人知道解决这个问题的更好方法？
这个问题的嵌入部分让它变得非常混乱，所以我假设我们估计连接成本以获得一个有向图，其中我们想要一个最小成本的强连通弧子图。然后使用贪心算法找到一个嵌入。
对于多项式时间内的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