迷宫求解最优不左转算法

Question

我正在处理一个项目，需要使用最少的右转而没有左转来解决迷宫问题。

只要尽量减少右转次数，行进距离并不重要。我们被要求使用回溯算法和最优（时间）算法来实现我们的程序。

对于回溯算法，我将使用栈。我的算法大致如下：

1. 将所有四个可能的起始方向推入栈中。 2. 沿着路径前进，尽可能直走。 3. 如果到达迷宫尽头，则返回当前路径长度作为最佳路径长度。 4. 如果到达死路，则回溯到最后一个可能的右转点并执行它。 5. 如果当前路径长度大于当前最佳路径长度，则回溯到最后一个可能的右转点并执行它。

我想知道是否有人能够指导我使用更优的算法。

我很难想到比回溯算法更好的算法。

- mussorsky

---

你能详细说明一下这个是如何工作的吗？你可以随意探索迷宫，但必须以最少的转弯次数得出最优解吗？还是你在寻找解决方案时所花费的时间也要计算在内？关于迷宫，你能做出什么样的假设？ - templatetypedef

Answer 1

我认为您可以通过先找到所有可达到的右转为0的点来完成它。然后只需要一个右转，等等。你可以使用一个队列来做到这一点。请注意，在第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

( ) 代表与相应的未达到邻居节点之间的已到达的节点。

- julx

---

这是动态规划。你可以从起点到终点进行操作。但是你不仅需要考虑“点”，还要考虑“点和方向（状态）”。问题是“使用1个RT可以到达哪些状态”，然后是“使用2个RT可以到达哪些状态”...反过来就是“从哪些状态可以在1个RT内到达目标”，“从哪些状态可以在2个RT内到达目标”。 - ysdx

abeln的答案更好。 - Sergey Orshanskiy

Answer 2

为迷宫中的每个位置构建四个节点，建立一个图。每个节点将对应于特定的方向：N、S、E、W。

每个节点与其最多三个相邻节点之间都有边缘连接：前面、后面和右侧（如果存在）。通往“前面”和“后面”节点的边缘权重为0（因为路径长度无关紧要），而通往“右侧”节点的边缘权重为1（这代表了向右转的成本）。

一旦设置好图（可能最好的方法是重用原始的迷宫表示），修改后的 breadth-first search 算法将解决问题。

处理0/1边缘权重的技巧是使用deque而不是标准队列实现。具体来说，通过0权重边缘到达的节点将被推入deque的前面，通过权重为1的边缘到达的节点将被推入deque的后面。

- abeln