Могут ли алгоритмы поиска (BFS и DFS) также использоваться для получения кратчайшего пути? - PullRequest
Новая
       33

Могут ли алгоритмы поиска (BFS и DFS) также использоваться для получения кратчайшего пути?

0 голосов
/ 28 октября 2018

На курсе ИИ я узнал о BFS, DFS и UCS.В моем курсе алгоритмов я изучил алгоритм Дейкстры.

Применяем ли мы алгоритмы поиска, такие как BFS и DFS, только для определения, существует ли конкретный узел или нет ИЛИ также дает кратчайший путь, как алгоритм Дейкстры?

1 Ответ

0 голосов
/ 28 октября 2018

Алгоритм Дейкстры - это просто обобщение BFS - BFS концептуально совпадает с алгоритмом Дейкстры, если все веса ребер равны 1.

BFS (поиск в ширину) даст вамсамый короткий (как в самой низкой стоимости) путь, если все веса ребер равны 1, но не будут (обязательно) в противном случае, поскольку порядок, в котором он исследует узлы, вообще не зависит от весов ребер.

DFS (Поиск в глубину) не обязательно даст вам кратчайший путь, потому что он просто исследует один произвольный путь за раз - возможно, вам повезло, и этот путь - самый короткий путь, но обычноэто не будетЭто даст вам кратчайший путь в дереве, но это только потому, что есть ровно один путь к любому данному узлу.

UCS (Поиск с равномерной стоимостью) работает очень похоже на Дейкструалгоритм и также будет возвращать кратчайший путь, но к одному целевому узлу, а не ко всем остальным узлам.

Пример

Для приведенного ниже графика предположим, что мы начинаем сA и переход к E. 

    A 1 C 1 D
    O---O---O
100 |       | 1
    O-------O
    B  100  E

И BFS, и DFS могут или будут возвращать более дорогой путь (ABE = 200 вместо ACDE = 3).

BFS посетит B (AB) и C (AC), а затем E (ABE) и D (ACD).На этом этапе он остановится, потому что он уже достиг цели, и вернет более длинный путь ABE.

DFS может начать произвольно, посещая либо B, либо C. Если он сначала посещает C, он возвращает кратчайший путь ACDE., но если он сначала посетит B, он исследует ABE и вернет этот более длинный путь.

...