bfs 双向宽搜

flatte / 2023-08-22 / 原文

 

1、迷宫问题,找最短路:

  可以同时从起点和终点进行bfs,两个方向搜索的新节点分别存在不同的队列中的,若新节点在对面的状态集合中出现过,说明相遇了。

2、很多bfs问题,都可以用双向宽搜,提高效率。

3、分油问题,能不能用双向宽搜呢?

3个无刻度的油瓶的容量是10 7 3,其中分别有油 10,0 ,0,问倒几次可以 分出 5 ,5, 0?

按双向宽搜的思路:

(10, 0, 0)   倒1次 可得 (3, 7, 0)   

 (5, 5, 0)    倒1次 也可得(3, 7, 0)

那只需2步。但这是错的。

                               

虽然550到370只需1步,但370无法一步变到550,也就是方向不可逆时不能双向宽搜。