algorithm - 迷宫求解最优禁止左转算法

Question

我正在做一个项目，我需要使用最少的右转次数而不是左转来解决迷宫问题。

只要右转最小化，行进的距离就无关紧要。我们被要求使用回溯算法和最佳(时间)算法来实现我们的程序。

对于回溯算法，我打算使用堆栈。我的算法是这样的:

• 将所有四个可能的起始方向压入堆栈。
• 沿着一条路走，尽可能直走。
• 如果我们到达迷宫的尽头，则将当前路径长度作为最佳路径返回。
• 如果我们到达死胡同，回到最后一个可能的右转弯并走。
• 如果当前路径长度大于当前最佳路径长度，则返回到最后一个可能的右转弯并进行。

我想知道是否有人可以为我指明最佳算法的方向。

我很难想出比回溯更好的方法。

Answer 1

我认为你可以通过首先找到所有可以通过 0 次右转到达的点来做到这一点。然后右转 1 次，依此类推。您可以使用队列来执行此操作。请注意，在第 n 个阶段，您已经获得了 n 次右转可以到达的所有点的最佳解决方案。更重要的是 - 任何尚未到达的点都可以通过 > n 点到达或根本无法到达。为了实现最佳时间复杂度，您必须使用这样一个事实，即您只需要从那些已到达的点中搜索新的可到达点，这些点在适当的方向上有一个未到达的邻居。由于每个点只有 4 个邻居，因此您只会从中搜索 4 次。您可以通过为每个方向 D 维护一个单独的列表来实现它，其中包含所有已到达的点以及该方向上未到达的邻居。这为您提供了与迷宫面积成正比的时间复杂度，而迷宫面积与输入数据的大小成正比。

下面我给出一个图形示例:

 .  .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1 (1)   0  1  1  1  1  1
 .  #######  .  .    0  ##########  .    0  ##########  .    0  ##########  2
 .  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  . (2)
 .  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  . (2)
 .  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  2
(.) .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1  1    0  1  1  1  1  1

 0  1  1  1  1  1    0  1  1  1  1  1
 0  ##########  2    0  ##########  2
 0  #  .  #  3  2    0  #  4  #  3  2
 0  # (3) 3  3  2    0  #  3  3  3  2
 0  ####  .  #  2    0  ####  4  #  2
 0  1  1 (1) 1  1    0  1  1  1  1  1

( ) 表示已到达点，但未到达适当的邻居