Por lo que he leído hasta ahora. El Best First Search parece más rápido en términos de encontrar el camino más corto hacia la meta porque el algoritmo de Dijkstra tiene que relajar todos los nodos a medida que atraviesa el gráfico. ¿Qué hace que el algoritmo de Dijkstra sea mejor que Best First Search?¿Por qué usar el algoritmo de Dijkstra en lugar de la primera búsqueda mejor (más barata)?
EDITAR: Tu edición aclara que está interesado en Best-First Search y no BFS.
Best-First Search es en realidad un algoritmo informado, que expande primero el nodo más prometedor. Muy similar al bien conocido A* algorithm (en realidad, A * es el mejor algoritmo de búsqueda específico).
Dijkstra es el algoritmo desinformado - se debe utilizar cuando no se tiene conocimiento del gráfico y no se puede estimar la distancia desde cada nodo al objetivo.
Tenga en cuenta que A * (que es la primera búsqueda mejor) se descompone en el algoritmo de Dijkstra cuando usa heuristic functionh(v) = 0 para cada v.
Además, mejor primera búsqueda no es óptima [no garantizados para encontrar el camino más corto], y también A *, si no se utiliza un admissible heuristic function, mientras que el algoritmo de Dijkstra siempre es óptima, ya que no retransmite en cualquier heurística.
Conclusión: Best-First Search debe preferirse a dijkstra cuando tiene algún conocimiento sobre el gráfico, y puede estimar una distancia desde el objetivo. Si no lo hace, una Mejor búsqueda no informada que utiliza h(v) = 0, y retransmite solo en vértices ya explorados, se descompone en el algoritmo de Dijkstra.
Además, si la optimalidad es importante, el Algoritmo de Dijkstra siempre se ajusta, mientras que el mejor algoritmo de búsqueda (A * específicamente) se puede usar solo si está disponible una función heurística apropiada.
Respuesta original - respondiendo a qué eligió Dijkstra sobre BFS:
BFS falla cuando se trata de weighted graphs.
Ejemplo:
A
/ \
1 5
/ \
B----1----C
En aquí: w(A,B) = w(B,C) = 1, w(A,C) = 5.
BFS de A devolverá A->C como la ruta más corta, pero para el gráfico ponderado, es una ruta de peso 5 !!! mientras que el camino más corto es de peso 2: A->B->C.
El algoritmo de Dijkstra no cometerá este error y devolverá la ruta ponderada más corta.
Si su gráfico no está ponderado - BFS es óptimo y completo - y generalmente debe preferirse a dijkstra - porque es más simple y más rápido (al menos de forma asintótica).
¿Quiso decir la primera búsqueda de Breadth, no es la más barata primero por BFS? –
@ user25464: Su pregunta original no estaba clara (al menos para mí), pensé que se refería a BFS. Mire la edición - ¿eso responde su pregunta? Guardo el original allí para futuros lectores, quizás alguien lo encuentre útil. – amit
dado que su respuesta original fue en respuesta a una edición "errónea" de @dmeister (que debería aprender a google antes de corregir las preguntas de otras personas), creo que sería mejor eliminarla. no está relacionado con la pregunta y solo ayuda a perpetuar la confusión iniciada por el error de dmeister. –
Normalmente Best First Search algoritmos en la búsqueda de camino, en busca de camino entre dos nodos dados: Fuente y fregadero, pero el algoritmo de Dijkstra encuentra camino entre la fuente y todos los demás nodos. Entonces no puedes compararlos. También Dijkstra en sí es tipo de Best First Search (variación de A *) significa que no puede decir que no es la mejor primera búsqueda. También los algoritmos normales de Best First Search utilizan heurísticas y no garantizan la corrección. Finalmente, en el caso ponderado, normalmente su tiempo de ejecución depende de los pesos, pero el algoritmo de Dijkstra solo depende del tamaño del gráfico.
BFS es bueno para encontrar la ruta más corta desde la fuente hasta un vértice en caso de que todos los bordes tengan el mismo peso, es decir, para encontrar un mínimo de bordes desde la fuente hasta un vértice. Mientras que Dikjstra es válido para gráficos ponderados
Estoy bastante seguro de que la B en BFS significa "Amplitud". Edité la pregunta en consecuencia. – dmeister
Creo que BFS es más lento en muchos escenarios. Cuando el rendimiento es importante, su precisión puede ser degradada para favorecer el rendimiento. –
@dmeister ¿es difícil dejar un comentario y dejarme corregirlo? –