6

我正在做一个项目，我需要使用最少的右转和不左转来解决迷宫。

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

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

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

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

我很难想出比回溯更好的东西。

4

2 回答 2

7

我认为你可以通过首先找到所有可以通过 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

( )表示到达的点与相应的邻居未到达

于 2011-04-09T23:00:44.080 回答
4

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

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

一旦建立了图形（可能最好的方法是重用迷宫的原始表示），广度优先搜索算法的修改变体将解决问题。

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

于 2011-04-09T23:00:05.017 回答