[我正在与朋友一起开发游戏算法，但我们陷入了困境。当前，我们有一个循环的无向图，我们试图找到从起始节点S覆盖所有边缘的最快路径。我们不想要游览，并且可能会有重复的优势。
关于算法或近似的任何想法？我确定这个问题很难解决，但我不认为这是TSP。
这被称为route inspection problem，并且确实具有多项式解。
基本思想（有关更多详细信息，请参见链接）是很容易解决的是一条欧拉路径（一次访问每个边一次），但是欧拉路径仅适用于某些图形。
特别是，一个图必须被连接并且具有0或2个奇数度的顶点。
但是，可以通过以最便宜的方式添加其他边来生成其他具有欧拉路径的图，从而对其他图进行概括。 （请注意，我们添加了更多的边，因此我们可以在原始图形的边上多次穿越。）
选择添加额外边缘的最佳方法的最大匹配问题可以在O（n ^ 3）中解决。
顺便说一下，我今天早些时候写了一个简单的演示（link to game），用于演示平面最大割问题。事实证明，此解决方案基于完全相同的路线检查问题：）
我刚刚从评论中发现，在您的特定情况下，您的图形可能是一棵树。
如果是这样，那么我认为答案要简单得多，因为您只需要在树上进行DFS，并确保先访问最浅的子树即可。
例如，假设有一棵树的边缘为S-> A和S-> A-> B。 S有两个子树，您应该先访问A，因为它较浅。
访问的总边数等于完整DFS中访问的边数，减去最后访问的叶子的深度，这就是为什么要最小化总边，而要最大化最后一个叶子的深度，并因此访问最浅的子树优先。
这有点像Eulerian Path。主要区别在于可能会有死胡同，您也许可以修改算法以适合您的需求。修剪死角是一种选择，或者您可以将图形简化为许多连接的组件。
DFS将在这里工作。但是，您必须具有良好的评估功能才能及早修剪分支。否则您将无法快速解决此问题。您可以在这里http://www.capacode.com/?p=650
引用我在Java中的讨论和实现。我的评估功能的详细信息我的第一个尝试是，如果当前路径的长度加上从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较小时，我们可以修剪更多。