Лучший алгоритм поиска BFS?

Question

Я знаю об агоризме Дейкстры, алгоритме Флойда-Варшалла и алгоритме Беллмана-Форда для поиска самых простых путей между двумя вершинами в графах.

Но когда все края имеют одинаковую стоимость, самый дешевый путь - это путь с минимальным количеством ребер? Я прав? Нет никаких оснований для реализации Dijkstra или Floyd-Warshall, лучшим алгоритмом является поиск Breadth-First из источника, пока мы не достигнем цели? В худшем случае вам придется пересекать все вершины, поэтому сложность O (V)? Нет лучшего решения? Я прав?

Но в Интернете есть множество статей, в которых рассказывается о самых коротких дорожках в сетках с препятствиями, и они упоминают Дейкстра или А *. Даже на StackOverfow - Algorithm to find the shortest path, with obstacles или здесь http://qiao.github.io/PathFinding.js/visual/

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

Answer 1

BFS (поиск по ширине) - это просто способ перемещения графика. Цель состоит в том, чтобы посетить все вершины. Это все. Другим способом перемещения графика может быть, например, DFS.

Dijkstra - это алгоритм, целью которого является поиск кратчайшего пути от заданной вершины v до всех других вершин.

Dijkstra не так сложна, даже для новичков. Он перемещает график, используя BFS +, делая что-то еще. Это нечто большее, чем хранение и обновление информации о кратчайшем пути к текущей посещенной вершине.

Если вы хотите найти кратчайший путь между двумя вершинами v и q, вы можете сделать это с небольшой модификацией Dijkstra. Просто остановитесь, когда достигнете вершины q.

Последний алгоритм - A * является несколько наиболее умным (и, вероятно, самым сложным). Он использует эвристику, волшебную фею, которая советует вам, куда идти. Если у вас хорошая эвристическая функция, этот алгоритм превосходит BFS и Dijkstra. A * можно рассматривать как расширение алгоритма Диктры (эвристическая функция является расширением).

Но когда все края имеют одинаковую стоимость, самым дешевым путем является путь с минимальным количеством ребер? Я прав?

Право.

Там нет оснований для осуществления Алгоритм Дейкстры или Флойда-Воршалла, лучший алгоритм поиска в ширину? Я прав?

Когда дело доходит до такого простого случая, когда все ребра имеют одинаковый вес - вы можете использовать любой способ, который вам нравится, все будет работать. Однако A * с хорошей эвристикой должен быть быстрее, чем BFS и Dijkstra. В указанном вами simulation вы можете это заметить.

Итак, все эти люди глупы? Или я глуп? Почему они рекомендуют для начинающих такие сложные вещи, как Дийкстра, которые просто хотят перенести своих врагов на главного героя в обычную сетку?

У них есть другая проблема, которая меняет решение. Прочитайте описание проблемы очень тщательно:

(...) Выгода быть в любой точке (кроме А и В) могут иметь препятствия, затрудняющие путь, и, следовательно, должны быть свернуть.

Враги могут иметь препятствия на пути к главному герою. Так, например, A * - хороший выбор в этом случае.

Answer 2

Но когда все края имеют одинаковую стоимость, самый дешевый путь - это путь с минимальным количеством ребер?. Да

Если вы действительно поняли сообщение, с которым вы связались, вы бы заметили, что проблема, которую они хотят решить, отличается от вашей.

Answer 3

BFS - это как «грубая сила», чтобы найти кратчайший путь в невзвешенном графике. Дейкстра похожа на «грубую силу» для взвешенных графиков. Если бы вы использовали Dijkstra на невзвешенном графике, это было бы точно эквивалентно BFS.

Итак, Dijkstra можно рассматривать как расширение BFS. Это не совсем «сложный» алгоритм; он немного сложнее, чем BFS.

A * - это расширение для Dijkstra, которое использует heuristic для ускорения поиска пути.