BFS 在一定规则下遍历沙漠图

Question

我目前正在解决如下 link 所示的问题： http://www.expertsmind.com/questions/python-implementation-of-a-solver-for-the-desert-crossing-30144185.aspx

这需要广度优先搜索（BFS）算法来解决问题。根据我的理解，modified BFS algo 用于查找从源节点连接到目的地的最短路径。但是，我不知道如何在规定的卡车穿越正式规则下的这种情况下实施它。

任何人都可以向我提供 guide/idea 如何使用 BFS 来解决这个问题吗？你的帮助很大appreciated.Thanks

Answer 1

第一步是尝试用图表来表述问题。在这种情况下，图中的每个节点（也称为顶点）代表沙漠的一些可能配置（位置或状态），由卡车位置和每个营地的汽油量描述。由于沙漠是一条固定线，因此将其表示为一组气体量是有意义的。设置好这些细节后，这里是图表的起始节点：

  truck (gas: 3)
  v
 [0, 0, 0, 0, 0]
  ^           ^
start        goal

从这个位置开始，称之为 (A)，到另一个节点的哪些过渡（边）是可能的？他们在这里：

       (B)                  (C)                    (D)

     truck (gas: 0)          truck (gas: 0)           truck (gas: 0)
     v                       v                        v
 [0, 2, 0, 0, 0]      [0, 0, 1, 0, 0]       [0, 0, 0, 0, 0]

以下是转换的图表形式：

      A
     /|\
    / | \
   B  C  D

节点(B)、(C)和(D)都是(A)的child个节点，它们的parent，意思是有从 parent 到 child 的可用过渡。一个一个探索这些children是一个BFS, whereas in a DFS，你会选择第一个child，(B)，并继续探索它的第一个child，直到它到达没有 children.

的叶节点

很明显，(D)是一个终端叶子节点，因为它没有children（不是目标，卡车没油，它所在的营地也没有油，所以卡住了; 没有可供考虑的转换）。

下一步是检查节点 (B) 和 (C) 可用的所有可能 child 状态。以下是 (B) 的 children:

       (E)                  (F)                   (G)

  truck (gas: 3)             truck (gas: 0)           truck (gas: 0)
  v                          v                        v
 [0, 1, 0, 0, 0]      [0, 0, 1, 0, 0]       [0, 0, 0, 0, 0]

       (H)   

        truck (gas: 0) 
        v         
 [0, 1, 0, 0, 0]

现在图表如下所示：

         A
       / | \
      /  |  \
     /   |   \
    B    C    D
  /|\ \
 / | \ \
E  F  G H

请注意，节点 (F) 和 (G) 与 (C) 和 (D) 相同，而 (E) 显然是最有希望的路线。尽管如此，(C) 将是下一个扩展，因为这是 BFS 而不是 DFS。我将跳过图表，但应该清楚 (C) 的 children（(I) 和 (J)）都是终端叶节点（卡车将运行无论它向左还是向右移动都没有气体）。此时，图形如下所示：

           A
         / | \
        /  |  \
       /   |   \
      /    |    \
     /     |     \
    B      C      D
  /|\ \    |\
 / | \ \   | \
E  F  G H  I  J

到这里应该很清楚，除了(E)，所有的东西都通向一个终端节点，其children将被扩展，直到达到目标或图中的所有节点被探索（即没有解决方案）。

如果遇到目标，则保证它是最短路径，因为扩展深度每一步增加 1，并且对于每个深度级别连续考虑所有过渡可能性。

希望这个练习能让算法更清晰；事实上，看起来 (E) 离目标只有两步了——看看你能不能用手找到剩下的路径。

在实现中，请记住使用堆栈（或递归调用）执行 DFS，而 queue 执行 BFS。此外，每个节点都应该有自己的 "desert" 数组副本，或者如果无效则需要一种方法来撤消其移动。最后，在每个节点上，通过减少一定量的气体（如果在大本营则增加 3）并尝试向左和向右移动来遍历所有可能的 child。

最后一步：优化。通过跟踪 already-explored 节点并避免重新计算它们（这也有助于避免图中的无限循环，这在这种情况下似乎不是问题（为什么？）），您可以牺牲存储 space 并获得速度。您还可以使用启发式搜索，通过在图表中优先考虑更有希望的路线来进一步提高速度。

BFS 在一定规则下遍历沙漠图

BFS traversing a desert graph under certain rules

python

breadth-first-search