[myhanh]

Nguyên văn bởi khanhan2006_2009

Trong mấy cái thuật toán về tìm kiếm đường đi ngắn nhất trên đồ thị thì cái nào là tối ưu nhất để chạy được các test lớn?Em thường dùng Dijkstra nhưng nghe nói cái đó khi chạy test lớn mất khá nhiều thời gian.

Đúng như em nói trong thực tế để giải quyết bài toán tìm kiếm người ta phải kết hợp giữa Local Search và Meta Search em à! Gỉai thuật Dijkstra là một trong những giải thuật Local search nó tìm kiếm ra một mẫu khi đã bỏ qua rất nhiều ràng buộc. Sau đó dùng mẫu này làm dữ liệu nhập cho các giải thuật meta search như Leo đồi, luyện kim, Tabu, gen ...
Do đó em cứ yên tâm dùng Dijkstra nhé vì khi cho Dijktra thì người ta cũng cho dữ liệu nhỏ thôi
Trong tìm kiếm đường đi ngắn nhất có hai giải thuật: Dijkstra (theo hướng tìn kiếm theo chiều rộng- cây tìm kiếm toả nhánh liên tục từ điểm gốc cho đến điểm đích và kết quả khi kết thúc giải thuật thì ta tìm được tất cả đường đi ngắn nhất từ điểm xuất phát đến các điểm còn lại của đồ thị) . Giải thuật Floyd (theo hướng tìm kiếm theo chiều sâu, cây tìm kiếm sinh ra không liên tục). Cả hai giải thuật có độ phức tạp thuật toán là . Tuy nhiên kinh nghiệm cho thấy Floyd đơn giản, dễ thực hiện và chạy nhanh hơn nhiều.
Đồ thị dày dùng Floyd
Đồ thị không dày () dùng Dijkstra.