BFS 在一定规则下遍历沙漠图
BFS traversing a desert graph under certain rules
我目前正在解决如下 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
第一步是尝试用图表来表述问题。在这种情况下,图中的每个节点(也称为顶点)代表沙漠的一些可能配置(位置或状态),由卡车位置和每个营地的汽油量描述。由于沙漠是一条固定线,因此将其表示为一组气体量是有意义的。设置好这些细节后,这里是图表的起始节点:
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 并获得速度。您还可以使用启发式搜索,通过在图表中优先考虑更有希望的路线来进一步提高速度。
我目前正在解决如下 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
第一步是尝试用图表来表述问题。在这种情况下,图中的每个节点(也称为顶点)代表沙漠的一些可能配置(位置或状态),由卡车位置和每个营地的汽油量描述。由于沙漠是一条固定线,因此将其表示为一组气体量是有意义的。设置好这些细节后,这里是图表的起始节点:
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 并获得速度。您还可以使用启发式搜索,通过在图表中优先考虑更有希望的路线来进一步提高速度。