Как вы используете двунаправленную BFS для поиска кратчайшего пути? Допустим, есть сетка 6x6. Начальная точка находится в (0,5), а конечная точка — в (4,1). Каков кратчайший путь с использованием двунаправленного BFS? Стоимость пути отсутствует. И это ненаправлено.
Как вы используете двунаправленную BFS для поиска кратчайшего пути?
Ответы (1)
Как работает двунаправленная BFS?
Одновременно запустите два BFS как из исходной, так и из целевой вершин, завершив работу, как только будет обнаружена вершина, общая для обоих запусков. Эта вершина будет на полпути между источником и целью.
Почему это лучше, чем BFS?
Двунаправленная BFS в большинстве случаев даст гораздо лучшие результаты, чем простая BFS. Предположим, что расстояние между источником и целью равно k
, а коэффициент ветвления равен B
(каждая вершина имеет в среднем B ребер).
- BFS пройдет
1 + B + B^2 + ... + B^k
вершин. - Двунаправленный BFS будет проходить через
2 + 2B^2 + ... + 2B^(k/2)
вершины.
Для больших B
и k
второй, очевидно, намного быстрее первого.
В вашем случае:
Для простоты я буду считать, что в матрице нет препятствий. Вот что происходит:
iteration 0 (init):
front1 = { (0,5) }
front2 = { (4,1) }
iteration 1:
front1 = { (0,4), (1,5) }
front2 = { (4,0), (4,2), (3,1), (5,1) }
iteration 2:
front1 = { (0,3), (1,4), (2,5) }
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) }
iteration 3:
front1 = { (0,2), (1,3), (2,4), (3,5) }
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), }
iteration 4:
front1 = { (0,1), (1,2), .... }
front2 = { (1,2) , .... }
Теперь мы обнаружили, что фронты пересекаются в (1,2) вместе с путями, по которым можно попасть туда из исходной и целевой вершин:
path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2)
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2)
Теперь нам просто нужно перевернуть путь 2 и добавить его к пути 1 (конечно, удалив одну из общих пересекающихся вершин), чтобы получить наш полный путь:
(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)
visited
и для очереди).
- person amit; 06.09.2016
discovered
массиве обхода B и наоборот.
- person mangusta; 04.03.2019