访问图中重复访问次数最少的所有节点

Question

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

例如：

地图示例 http://img220.imageshack.us/img220/3488/mapq .png

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

路径示例 http://img222.imageshack.us/img222/7773/mapd.png

该路径中有两次重复访问。 更糟糕的路径是在第一个路口左转，然后在三个已经访问过的方块上原路返回。

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

谢谢。

编辑：

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

http://img220.imageshack.us/img220/3488/mapq。 png

http://img222.imageshack.us/img222/7773/mapd .png

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

Answer 1

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

Answer 2

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

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

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

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