search - 访问图中重复访问最少的所有节点

Question

我有一个基于瓷砖的地图，其中几个瓷砖是墙壁，其他瓷砖是可步行的。可步行的瓷砖构成了我想在路径规划中使用的图表。我的问题是他们是否有任何好的算法来找到访问图中每个节点的路径，最大限度地减少重复访问？

例如：

如果底部的黄色瓷砖是起点，则访问所有重复次数最少的瓷砖的最佳路径是：

这条路径有两次重复访问。更糟糕的路径是在第一个路口左转，然后在三个已经访问过的瓷砖上回溯。

我不关心结束节点，但开始节点很重要。

谢谢。

编辑：

我在我的问题中添加了图片，但在查看时看不到它们。他们来了：

此外，在图表中我需要这个，因为永远不会出现 min repeats = 0 的情况。也就是说，要踩到地图中的每个图块，玩家必须至少穿过自己的路径一次。

score 1 · Accepted Answer

您的措辞不好-它可以简化为NP完全问题。如果您可以最大限度地减少重复访问，那么您可以将它们推到 0，然后您就会有一个哈密顿循环。这是可以解决的，但很难。

score 0 · Accepted Answer

这听起来像是可以映射到旅行商问题......因此很可能最终是 NP 完全的，并且没有已知的有效确定性算法。

找到一条路径相当简单——找到一个（或最小的）生成子树，然后进行深度/广度优先遍历。找到最佳路线是非常困难的一点。

您可以使用其中一种动态优化技术来尝试并收敛到一个相当好的解决方案。

除非最小生成子树的某些属性可用于生成最佳路径......但我不记得足够的图论。

2 回答 2