我正在和朋友一起开发一款游戏的算法，但我们陷入了困境。目前，我们有一个循环无向图，我们正在尝试从起始节点 S 找到覆盖每条边的最快路径。我们不是在寻找旅行，可能会有重复的边缘。
关于算法或近似的任何想法？我确定这个问题是 NP 难的，但我不相信它是 TSP。
问问题
4118 次
3 回答
4
巡线
这被称为路由检查问题，它确实有一个多项式解决方案。
基本思想（有关详细信息，请参阅链接）是很容易求解欧拉路径（我们访问每条边一次），但欧拉路径仅适用于某些图。
特别是，一个图必须是连接的并且有 0 或 2 个奇数度的顶点。
但是，可以通过以最便宜的方式添加额外的边来将其推广到其他图，从而生成具有欧拉路径的图。（请注意，我们添加了更多边，因此我们可能会在原始图中的边上多次移动。）
选择添加附加边的最佳方式的方法是一个最大匹配问题，可以在 O(n^3) 中解决。
附言
顺便说一句，我今天早些时候为平面最大切割问题写了一个简单的演示（游戏链接）。这个解决方案原来是基于完全相同的路由检查问题:)
编辑
我刚刚从评论中发现，在您的特定情况下，您的图表可能是一棵树。
如果是这样，那么我相信答案要简单得多，因为您只需要在树上进行 DFS，确保首先访问最浅的子树。
例如，假设您有一棵树，其边为 S->A 和 S->A->B。S 有两个子树，你应该先访问 A，因为它比较浅。
访问的总边将等于完整 DFS 中访问的边数减去最后访问的叶子的深度，这就是为什么要最小化总边以最大化最后一个叶子的深度，从而访问最浅的子树第一的。
于 2013-09-13T21:06:41.943 回答
0
这有点像欧拉路径。主要区别在于可能存在死胡同，您可以修改算法以满足您的需求。修剪死胡同是一种选择，或者您可以将图形减少为许多连接的组件。
于 2013-09-13T20:44:47.430 回答
0
DFS 将在这里工作。但是，您必须具有良好的评估功能才能尽早修剪分支。否则你不能快速解决这个问题。您可以在此处参考我在 Java 中的讨论和实现http://www.capacode.com/?p=650
我的评估函数的细节我的第一次尝试是如果当前路径的长度加上从U到G的距离不小于我们找到的最小长度（存储在minLength变量中），我们将不会访问U，因为它无法引导更短的路径。
实际上，上述评估函数并不高效，因为它仅在我们已经访问了大多数城市时才有效。我们需要更精确地计算所有访问过的城市到达 G 的最小长度。
假设s是从S到U的长度，从U到访问G并经过所有城市，长度至少为s' = s + ∑minDistance(K) 其中K是未访问城市，与U不同；minDistance(K) 是从 K 到未访问状态的最小距离。基本上，对于每个未访问的州，我们假设我们可以以最短的边到达那个城市。请注意，那些最短的边可能不会构成有效路径。然后，如果 s' ≥ minLength，我们将不会访问 U。
有了这个评估功能，我的程序可以在 1 秒内处理 20 个城市的问题。我还添加了另一个优化以进一步提高性能。在运行程序之前，我使用贪心算法来获得一个好的 minLength 值。具体来说，对于每个城市，我们接下来会访问最近的城市。原因是当我们有一个较小的 minLength 时，我们可以修剪更多。
于 2015-03-25T13:23:03.740 回答