所以我有以下布局:
目标是通过移动白球来收集所有黄色方 block 。我正在尝试提出一种算法来计算有效路径，但我不太确定从哪里开始。
最初我考虑过像 Djikstra 和 A* 这样的寻路算法，但它们似乎不符合我的目标。我也考虑过哈密尔顿路径，它更接近我想要的但似乎仍然没有解决问题。
任何关于可以使用哪种算法的建议都将不胜感激。
最佳答案
你的问题在文献中有一个经典的名字，它是最小汉密尔顿行走问题。注意不要将它与最小哈密顿路径问题混淆，它的“表亲”，因为它更有名，也更难(找到哈密顿行走可以在多项式时间内完成，找到哈密顿路径是 NP 完全) .旅行商问题是最小哈密顿路径问题(path，not walk)的别称。
关于这个问题的资源非常少，但是您可以看看 Takamizawa、Nishizeki 和 Saito 于 1980 年发表的一篇名为“一种在图中寻找短的闭合跨度游走的算法”的文章。他们提供了一个多项式找到这样一条路径的算法。
如果这篇论文有点难读，或者算法太复杂而无法实现，那么我建议你去 christofides algorithm ，因为它在多项式时间内运行，并且在某种程度上是高效的(如果我没记错的话，它是一个 2 近似值)。
另一种可能的方法是采用贪婪算法，例如最近的未访问邻居算法(从某个地方开始，转到最近的尚未在行走中的节点，重复直到每个人都在行走中)。
实际上，我认为最简单也可能是最好的简单解决方案是贪婪。
关于以最高效率访问无向图中所有节点的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55700238/