通过迷宫必须穿越的起点和终点之间的最小距离

小编典典

通过迷宫必须穿越的起点和终点之间的最小距离

algorithm

因此，假设我有一个迷宫，迷宫的起点和终点分别标记为橙色和红色，而我的目标是找到它们之间的最小距离。阻塞的路径用黑色表示，开放路径用白色表示。但是，此操作有两个修改。

有一些必须访问的单元格，用灰色标记。
任何单元都可以被访问任意次（甚至开始，结束和必须访问的点）

例如-B =黑色，W =白色，G =灰色，R =红色，O =橙色

         BBBBBB                 BBBBB
         BBGBBB                 BWGGB
MAZE1 => BOWGRB     MAZE2  =>   BOBBB
         BBGBBB                 BWWRB
         BBBBBB                 BBBBB

在这种情况下，ans

MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4]  = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2]            = 6

如您所见，节点出现多次

首先，我想到了使用递归技术（回溯），但是没有一个算法。和

所以我想用这种方式。

我将跟踪必须访问的点，起点和终点的所有坐标
找到每个节点之间的距离（就像在选择排序中，我们比较每个术语，就像这样，我们获得每个节点之间的最小距离（使用BFS））
然后应用一些最小距离算法。我想到了TSP，但是它说节点必须被访问一次，这里可以是多次。我发现了中国邮递员的问题，但不知道是否可以在这里应用。有Floyd Warshall算法，但不包括所有要点

我该如何进行？

阅读 671

2020-07-28

共1个答案

小编典典

好的，所以也许我会再尝试解决这个问题。上次，我没有注意到您可以多次访问一个点的事实，因此建议可能是错误的。

首先，假设“开始”，“结束”和“灰色”节点的总数为N，并且“开始”为0，“结束”为N-1，“灰色”节点的总数为1到N-2。

我们可以看到我们可以state随时(mask, index)用表示，其中index表示我们所在的当前节点，mask表示我们已经访问过的所有节点（0
<mask <2 ^ N）。

首先，状态为（1,0）或（00000 … 1,0），这意味着仅访问了城市0，我们的目标是到达状态（2 ^
N-1，N-1），这意味着访问所有节点，然后在节点N-1结束旅程。

因此，在这一点上，我们可以很容易地看到，我们已经将原始问题转换为状态图，并且我们的目标是找到从状态0（1,0）到状态末端（2 ^ N-1）的最短路径。
，N-1），因此，对这个新图应用Dijkstra最短路径算法，我们就得到了答案。

注意：答案基于一个假设，即N <= 17

另一个要注意的是：对于机器人技术，最短的路径可能并不一定是最佳的路径，因为机器人在旋转和直线运行时的速度是不同的。

2020-07-28