以最高效率访问无向图中所有节点的算法？
Algorithm to visit all nodes in an un-directed graph with greatest efficiency?
所以我有以下布局：
graph representation
objective是通过移动白球来收集所有的黄色方块。我正在尝试提出一种可以计算出有效路径的算法，但是我不太确定从哪里开始。
最初我考虑过像 Djikstra 和 A* 这样的寻路算法，但它们似乎不符合我的目标。我也考虑过哈密尔顿路径，它更接近我想要的但似乎仍然没有解决问题。
任何关于可以使用哪种算法的建议都将不胜感激。
你的问题在文献中有一个经典的名字，它是最小汉密尔顿游走问题。注意不要将它与最小哈密顿路径问题混淆，它是 'cousin'，因为它更有名，也更难（找到哈密顿行走可以在多项式时间内完成，找到哈密顿路径是 NP-完全的）。旅行商问题是最小哈密顿路径问题（path，not walk）的别称。
关于这个问题的资源很少，但是你可以看看 Takamizawa、Nishizeki 和 Saito 在 1980 年发表的一篇名为 'An algorithm for finding a short closed spanning walk in a graph' 的文章。他们提供了一种多项式算法来找到这样的路径。
如果论文有点难读，或者算法太复杂无法实现，那么我建议你选择 christofides algorithm，因为它在多项式时间内运行，并且在某种程度上是高效的（如果我没记错的话，这是一个2-近似值）。
另一种可能的方法是采用贪心算法，例如最近的未访问邻居算法（从某处开始，转到最近的尚未在行走中的节点，重复直到每个人都在行走中）。
实际上，我认为最简单也是最好的简单解决方案是贪心。
所以我有以下布局：
graph representation
objective是通过移动白球来收集所有的黄色方块。我正在尝试提出一种可以计算出有效路径的算法，但是我不太确定从哪里开始。
最初我考虑过像 Djikstra 和 A* 这样的寻路算法，但它们似乎不符合我的目标。我也考虑过哈密尔顿路径，它更接近我想要的但似乎仍然没有解决问题。
任何关于可以使用哪种算法的建议都将不胜感激。
你的问题在文献中有一个经典的名字，它是最小汉密尔顿游走问题。注意不要将它与最小哈密顿路径问题混淆，它是 'cousin'，因为它更有名，也更难（找到哈密顿行走可以在多项式时间内完成，找到哈密顿路径是 NP-完全的）。旅行商问题是最小哈密顿路径问题（path，not walk）的别称。
关于这个问题的资源很少，但是你可以看看 Takamizawa、Nishizeki 和 Saito 在 1980 年发表的一篇名为 'An algorithm for finding a short closed spanning walk in a graph' 的文章。他们提供了一种多项式算法来找到这样的路径。
如果论文有点难读，或者算法太复杂无法实现，那么我建议你选择 christofides algorithm，因为它在多项式时间内运行，并且在某种程度上是高效的（如果我没记错的话，这是一个2-近似值）。
另一种可能的方法是采用贪心算法，例如最近的未访问邻居算法（从某处开始，转到最近的尚未在行走中的节点，重复直到每个人都在行走中）。
实际上，我认为最简单也是最好的简单解决方案是贪心。