迷宫解决最优无左转算法

2 回答

• 7

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

  每个节点和最多三个相邻邻居之间将存在边缘：“前”，“后”和“右”（如果它们存在） . 通向“前”和“后”节点的边将具有权重0（因为路径长度无关紧要），而“右”中节点的边将具有权重1（这是代表的转弯的成本） .

  一旦图形被设置（并且可能最好的方法是重用迷宫的原始表示），breadth-first search算法的修改变体将解决该问题 .

  处理0/1边权重的技巧是使用deque而不是标准队列实现 . 具体而言，通过0个重量边缘到达的节点将被推到前梁的前部，而通过重量1的边缘到达的节点将被推到后面 .

  回复于 2024-04-28T05:24:50+08:00
• 4

  我认为你可以通过首先找到0转右转的所有点来做到这一点 . 然后只用右转1，依此类推 . 您可以使用队列来执行此操作 . 请注意，在第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
  

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

  回复于 2024-04-28T05:24:50+08:00