在一个网格中寻找访问所有非阻塞方块的最短路径。

Question

假设你有一个像这样的网格（随机生成）：

现在假设你有一辆车从其中一个白色方块开始随机行驶，问通过每个白色方块的最短路径是什么？你可以无限制地访问每个白色方块，但不能越过黑色方块。黑色方块就像墙壁一样。简单地说，你只能在白色方块之间移动。

你可以向任何方向移动，甚至对角线。

两个子问题：

1. 假设你在移动前知道所有黑色方块的位置。
2. 假设你只有在相邻的白色方块中才知道黑色方块的位置。

- Laz

---

“如何才能通过每个白色方框的最短路径？”你在这里问什么？你是指“去到每一个白色方框”吗？ - amara

要找到最短的路径，你必须进行暴力搜索。事实上，你事先是否知道黑盒子并不重要。 - mdma

访问一个图中所有节点，使重复访问最少。 - Rubys

这不是TSP。在TSP中，您只能访问一个顶点一次。如果是这种情况，大多数这些方格将无法到达！ - Laz

@系统管理员：这不是旅行推销员问题。在TSP中，每个节点都是相互连接的，并且你只会访问每个节点一次。 - BlueRaja - Danny Pflughoeft

Answer 1

您应该将问题建模为完全图，其中两个节点（白色方框）之间的距离是这些节点之间最短路径的长度。这些路径长度可以通过 Floyd-Warshall 算法计算。然后，您可以像 glowcoder 写的那样将其视为 "旅行商问题"。

编辑：为了更清楚地说明：您可以通过一系列不同的白色方框来描述迷宫中的每条“有趣”的路径。因为如果您有任意一条访问每个白色方框的路径，您可以将其分成子路径，每个子路径都以一个尚未访问过的新白色方框结束。从白色方框 A 到 B 的每个子路径都可以替换为从 A 到 B 的最短子路径，这就是为什么需要所有节点对之间的最短路径矩阵的原因。

- Doc Brown

---

这很复杂。TSP可以直接应用。为什么要经过Floyd-Warshall算法？在你进一步阐述之前，我给出-1分。 - Aryabhatta

@Moron：从维基百科来看，第一句话是：“任务是找到一条最短的路径，恰好访问每个城市一次。”这就是我的建议所做的：即使您必须多次访问每个方格，也可以将问题视为这种类型的TSP问题。 - Doc Brown

@Moron：如果你有更好的想法让它“不那么复杂”，请告诉我。 - Doc Brown

@文档：即使我们找到了结果TSP的精确最优解，我们是否拥有原问题的最优答案？为了使近似算法更简单化，像最小生成树的欧拉路径之类的一些简单算法存在。这必须是一个经过深入研究的问题。如果您有一个可以证明您方法可行的参考资料，那太好了！ - Aryabhatta

@文档：我没有看到你编辑答案。你是对的。那似乎可以工作！再加上它很可能是NP-Complete... +1。 - Aryabhatta

Answer 2

这似乎是一个NP完全问题。

在网格图中的哈密顿路径已被证明是NP完全问题。相关链接：网格图中的哈密顿路径。

值得注意的是，网格图是完整网格的子图。

当然，我还没有阅读过那篇论文，请先确认一下，特别是允许对角线移动的部分。

- Aryabhatta

---

这如何简化为寻找哈密顿路径？他明确表示您可以随意访问每个白色方块，而在哈密顿路径中并非如此。 - bnaul

@bnaul：类似于https://dev59.com/VkzSa4cB1Zd3GeqPlUpg#2360303的缩减可能有效。 - Aryabhatta

Answer 3

Doc已经得到了。 我会补充说明，黑盒子只会改变所有白盒子之间的距离。更进一步解释-如果在任意两个白盒子之间的对角线上有一个黑盒子（易于检查），则需要计算最短路径以获取距离。一旦你拥有一个距离矩阵，然后通过创建一个长度为零的虚拟节点到所有其他节点，来解决TSP或哈密顿路径问题。

关键是，为了制定和解决TSP（或任何问题制定），你必须先有一个距离矩阵。距离矩阵不是一开始就指定的，因此必须从头开始开发它。

- Grembo

Answer 4

虽然基于TSP的启发式方法是一个合理的方法，但并不清楚它是否给出了最优解。问题（正如Moron所指出的）是跨越路径问题，在评论中提供的链接中，有许多特殊情况可以使用线性时间最优解来解决。一个使得OP的问题与引用论文中使用的网格图公式不同的陷阱是能够对角线遍历，这会改变游戏的很多方面。

- Suresh

Answer 5

这类似于骑士巡游问题，其中典型的解决方案评估从起始方块开始的所有可能路径。当无法完成旅行时，使用回溯返回以追溯以前的决策。 你的问题更加轻松，因为你可以多次访问方块。 骑士巡游和旅行推销员问题通常需要恰好访问每个方块。

请参见 http://en.wikipedia.org/wiki/Knight's_tour

- mdma

---

如果可以多次访问正方形，如何确定旅行无法完成（因此需要开始回溯）？通常情况下，当所有附近的正方形已经被访问时就会确定 - 但是，如果您可以访问它们两次，这种情况就不再适用 :-) - psmears

你可以从一个方格到另一个方格进行可达性分析 - 例如，评估从源方格到目标方格的所有路径。在这里，避免循环，我们只需要一条路径，因此每个方格只被访问一次。例如，考虑一个棋盘，黑色方块沿中心将其分成两半。您开始的那一半的方格是可达的，而另一半的方格则不可达。 - mdma

Answer 6

尝试将其构建为一个图形（其中每个节点最多有8个其他节点），并像http://en.wikipedia.org/wiki/Travelling_salesman_problem一样对待它

- corsiKa

---

“它可以被简化为一个NP完全问题（你甚至没有展示）的事实，与告诉他暴力解决没有什么区别。” - BlueRaja - Danny Pflughoeft

@BlueRaja：仅仅因为你不喜欢这个答案，并不代表它是错误的。我会给glowcoder打-1分，因为他的回答忽略了TSP通常需要每个城市只被访问一次这一事实，而这在这里并不是适当的模型，因为有些白色方块需要被多次访问。 - Doc Brown

TSP并不要求每个城市都必须被访问一次，它只关心两个城市之间的最短路径，无论途中是否经过已经访问过的城市。无论如何，这都是一个NP难问题，我认为最好采用与TSP相同的方法来解决。 - corsiKa

@BlueRaja，@Doc Brown。在网格图（网格的子图）中找到跨越路径（每个顶点至少一次）是NP完全问题。这是链接：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3040。@DocBrown：在一般图中找到访问每个顶点至少一次的最短路径也是NP完全问题，很容易证明。试试看。 - Aryabhatta

@glowcoder：NP问题（因此也包括P问题）可以通过TSP进行建模，因此可以使用TSP算法来解决，因此这个答案并没有帮助（仍然可能存在有效的解决方案）。有用的是展示一个有效的解决方案将给出TSP的有效解决方案，从而证明它是NP完全问题（在这种情况下，这个解决方案就是你能得到的最好的解决方案）。我相信这是正确的，但是这里没有人展示过。 - BlueRaja - Danny Pflughoeft

@BlueRaja：看起来是NP完全问题。请查看我回答中的链接。 - Aryabhatta