Tại sao sử dụng thuật toán Dijkstra thay vì Tìm kiếm đầu tiên tốt nhất (rẻ nhất)?

Question

Từ những gì tôi đã đọc cho đến nay. Các Best First Search có vẻ nhanh hơn trong việc tìm kiếm con đường ngắn nhất đến mục tiêu bởi vì thuật toán của Dijkstra phải thư giãn tất cả các nút khi nó đi qua biểu đồ. Điều gì làm cho thuật toán của Dijkstra tốt hơn Tìm kiếm đầu tiên tốt nhất?

Answer 1

EDIT: chỉnh sửa của bạn rõ bạn quan tâm đến Best-First Search, và không BFS.

Tìm kiếm tốt nhất đầu tiên thực sự là một thuật toán được thông báo, mở rộng nút hứa hẹn nhất trước tiên. Rất giống với A* algorithm (thực tế A * là thuật toán tìm kiếm tốt nhất đầu tiên).

Dijkstra là thuật toán chưa được định dạng - nó nên được sử dụng khi bạn không có kiến ​​thức về biểu đồ và không thể ước tính khoảng cách từ mỗi nút đến đích.

Lưu ý rằng A * (tìm kiếm tốt nhất đầu tiên) phân rã thành thuật toán Dijkstra khi bạn sử dụng heuristic functionh(v) = 0 cho mỗi v.

Bên cạnh đó, tốt nhất tìm kiếm đầu tiên không phải là tối ưu [không được bảo đảm để tìm ra con đường ngắn nhất], và cũng A *, nếu bạn không sử dụng một admissible heuristic function, trong khi thuật toán Dijkstra là luôn luôn tối ưu, vì nó không chuyển tiếp trên bất kỳ heuristic.

Kết luận: Tìm kiếm tốt nhất đầu tiên nên được ưu tiên hơn dijkstra khi bạn có một số kiến ​​thức về biểu đồ và có thể ước tính khoảng cách từ mục tiêu. Nếu bạn không - Tìm kiếm tốt nhất đầu tiên không được định dạng sử dụng h(v) = 0 và chỉ chuyển tiếp trên các đỉnh đã khám phá, phân rã thành thuật toán của Dijkstra.
Ngoài ra, nếu tối ưu là quan trọng - Thuật toán của Dijkstra luôn phù hợp, trong khi thuật toán tìm kiếm tốt nhất (A * cụ thể) chỉ có thể được sử dụng nếu có sẵn chức năng heuristic thích hợp.

---

Original câu trả lời - trả lời tại sao để chọn Dijkstra trên BFS:

BFS thất bại khi nói đến weighted graphs.

Ví dụ:

 A 
/ \ 
    1  5 
/  \ 
B----1----C 

Tại đây: w(A,B) = w(B,C) = 1, w(A,C) = 5.

BFS từ A sẽ trả lại A->C là đường đi ngắn nhất, nhưng đối với biểu đồ có trọng số, đó là một đường có trọng số 5 !!! trong khi con đường ngắn nhất có trọng số 2: A->B->C.
Thuật toán của Dijkstra sẽ không phạm sai lầm này và trả lại đường dẫn có trọng số ngắn nhất.

Nếu đồ thị của bạn không có trọng số - BFS vừa tối ưu vừa hoàn thành - và thường được ưu tiên hơn dijkstra - cả bởi vì nó đơn giản và nhanh hơn (ít nhất là tiệm cận).

Answer 2

thường Best First Search thuật toán trong việc tìm kiếm con đường, tìm kiếm con đường giữa hai nút đưa ra: Nguồn và Chìm, nhưng thuật toán Dijkstra tìm thấy đường dẫn giữa nguồn và tất cả các nút khác. Vì vậy, bạn không thể so sánh chúng. Ngoài ra Dijkstra chính nó là loại Best First Search (biến thể của A ^*) có nghĩa là bạn không thể nói nó không phải là Tìm kiếm đầu tiên tốt nhất. Thuật toán tìm kiếm đầu tiên tốt nhất bình thường đang sử dụng heuristics và chúng không đảm bảo về tính chính xác, Cuối cùng trong trường hợp có trọng số bình thường thời gian chạy của chúng phụ thuộc vào trọng số, nhưng thuật toán của Dijkstra chỉ phụ thuộc vào kích thước đồ thị.

Answer 3

BFS là tốt cho việc tìm đường đi ngắn nhất từ ​​nguồn đến đỉnh trong trường hợp tất cả các cạnh có cùng trọng số, nghĩa là tìm tối thiểu không có cạnh nào từ nguồn đến đỉnh. Trong khi Dikjstra giữ tốt cho các biểu đồ có trọng số