我的问题如下：
我有一个无向图 . 每个边缘都有成本（或重量） . 其中一个节点标记为S.我想从S开始并至少访问每个节点一次 . 允许多次访问节点 . 允许多次沿着边缘行进，尽管这会使解决方案更加昂贵 - 以3倍的成本行驶边缘将增加总路径的成本6 . 该图有一些"dead-end"节点，因此有时我们不得不多次前进 .
这样做的快速算法是什么？这是一个众所周知的问题吗？
我在找什么：
合理快速 - 我们在这里讨论的图表的相对大小是40-50个节点的顺序 . 所以算法希望不会超过10-15秒 .
合理的最佳 - 我不是在寻找绝对的最优性 . 任何有趣的启发式指导搜索，以使解决方案接近最优是足够好的 .
我将在python中写这个 . 因此，如果你知道算法的任何python实现，那是最好的 .
谢谢你的帮助 .
5 回答
这是旅行商问题的一个版本，wikipedia article对各种不同的启发式方法有很好的概述 .
标准TSP和您的算法之间的最大区别在于TSP通常每个节点只执行一次访问，而您允许多次访问 . 这个问题很好地回答了this问题 .
This guy记录了他的Python TSP解决方案，以及this对于如何在Python中实现图形内容的非常有用的讨论 .
一种简单的方法是为您的图形构建最小生成树，并在其上执行（深度优先）遍历，跳过已访问过的节点 .
事实证明，这不会超过最佳TSP路径的两倍 . 你可以用启发式方法做得更好，但它是一个启动器（并且易于实现） .
使用Iterative Limited深度优先搜索
看到
http://en.wikipedia.org/wiki/Depth-limited_search
单源 - 最短路径
如果你有一个节点$ s $并想找到一个节点$ t $的最短路径 .
如果图形具有非负边缘权重，Dijkstra's Algorithm将在时间$ O（| E | | V | \ log | V |）$中找到最佳答案 .
但是，如果图形包含负边缘权重，Bellman-Ford's Algorithm将在$ O（| V || E |）$ time中找到最佳答案，但受限于图形不包含负权重周期 .
All-Pairs-Shortest-Path
这是为了找到图中任意两个节点$ u，v $之间的最短路径 . 它可以通过Floyd-Warshall's Algorithm及时解决$ O（| V | ^ 3） . $与Bellman-Ford方法类似，图表不得包含负权重周期 .
负权重循环约束的原因是最短路径可以连续地采用循环并减少其重量（如下所示） .
编辑3：不，还在寻找
编辑2：
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈！
Djikstra's Algorithm
D的算法找到距起始节点和图中每个其他节点的最短距离 .
这是一个python实现，看起来合理修改以使用您的代码：
Python Implementation
编辑：正如在评论中正确指出的，A *是（在一次迭代中）用于单个路径 . 因此，不满足您访问每个节点一次的要求 . 我仍然认为TSP是一个比你面临的更复杂的问题，因为你被允许访问节点> 1次 .
原文：A *
A* Wiki Article
我喜欢在大学里解决这个问题，享受！