假设您有一个像这样的网格（随机制作）：
现在假设您有一辆汽车随机从其中一个白框出发，通过每个白框的最短路径是什么？您可以根据需要多次访问每个白框，并且不能跳过黑框。黑匣子就像墙壁。简而言之，您只能从白盒移动到白盒。
你可以向任何方向移动，甚至是对角线。
两个子问题：
- 假设您在移动之前知道所有黑盒的位置。
- 假设您只有在与黑盒相邻的白盒中时才知道黑盒的位置。
问问题
3135 次
6 回答
4
您应该将问题建模为一个完整的图形，其中两个节点（白框）之间的距离是这些节点之间最短路径的长度。这些路径长度可以通过Floyd-Warshall算法计算。然后，您可以将其视为“旅行推销员”，就像glowcoder 写的那样。
编辑：为了更清楚：您可以通过一系列不同的白框来描述穿过迷宫的每条“有趣”路径。因为如果您有访问每个白盒的任意路径，您可以将其拆分为子路径，每个子路径都以一个迄今为止未访问过的新白盒结束。从白盒 A 到 B 的每个子路径都可以替换为从 A 到 B 的最短子路径，这就是为什么您需要所有节点对之间的最短路径矩阵的原因。
于 2010-05-20T17:10:34.873 回答
1
医生得到了它。我要补充一点，黑盒子只会改变所有白盒子对之间的距离。进一步阐述 - 如果在任何两个白框之间的对角线上有一个黑框（很容易检查），您需要计算最短路径以获得距离。一旦你有了一个距离矩阵，然后在创建一个到所有其他节点的长度为零的虚拟节点之后通过求解一个 TSP 来求解一个 TSP 或哈密顿路径。
关键是，为了制定和解决 TSP（或任何与此相关的问题），您必须从一个距离矩阵开始。距离矩阵在开始时没有指定，因此必须从头开始开发。
于 2010-05-20T20:09:37.450 回答
1
这似乎是一个 NP 完全问题。
网格图中的哈密顿路径是 NP-Complete 已在此处显示：网格图中的哈密顿路径。
注意网格图 = 完整网格的子图。
当然，我没有看过那篇论文，所以先确认一下，特别是允许对角线移动的部分。
于 2010-05-20T18:16:42.500 回答
1
虽然基于 TSP 的启发式方法是一种合理的方法，但尚不清楚它是否给出了最佳答案。问题（正如 Moron 指出的那样）是跨越路径问题，在评论中提供的链接中，有许多特殊情况存在线性时间最优解。使 OP 的问题与引用论文中使用的网格图公式不同的一个问题是对角线遍历的能力，这在很大程度上改变了游戏。
于 2010-06-30T20:56:42.357 回答
0
这类似于 Knights Tour 问题，其中一个典型的解决方案评估源自起始广场的所有可能路线。当无法完成巡视时，则使用回溯来返回以备份先前的决定。您的问题更轻松，因为您可以多次访问广场。Knights tour 和 Traveling Saleman 问题通常要求每个广场只访问一次。
于 2010-05-20T16:59:43.460 回答
-1
尝试将其构建为图形（每个节点最多有 8 个其他节点）并将其视为http://en.wikipedia.org/wiki/Travelling_salesman_problem
于 2010-05-20T16:57:42.890 回答