Ðề: Những thuật toán hay thi HSG Tin học
 

Ðề: Những thuật toán hay thi HSG Tin học
 

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.

Ðề: Những thuật toán hay thi HSG Tin học
 

Đú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.

Ðề: Những thuật toán hay thi HSG Tin học
 

Theo em biết thì Dijkstra chỉ là n^2 thôi.
Đồ thị dày là sao anh?
Nếu như Floyd đơn giản, dễ thực hiện và chạy nhanh hơn thì sao ko dùng Floyd cho tất cả các dạng đồ thị.?

Ðề: Những thuật toán hay thi HSG Tin học
 

Đúng là n^2 nhưng để so sánh với F thì phải chạy D n lần cơ!
Đồ thị dày tức là trái với độ thị không dày đã định nghĩa rùi đó.

Ðề: Những thuật toán hay thi HSG Tin học
 

???????????????????????

Ðề: Những thuật toán hay thi HSG Tin học
 

ah!Em hiểu rồi,ý anh là tìm đường đi ngắn nhất giữa mọi cặp đỉnh?
Nếu như vậy thì Dijkstra là n^3.
"Nếu như Floyd đơn giản, dễ thực hiện và chạy nhanh hơn thì sao ko dùng Floyd cho tất cả các dạng đồ thị mà phân ra dày hay không dày?"

Ðề: Những thuật toán hay thi HSG Tin học
 

Nếu sử dụng Dijkstra trên cấu trúc HEAP có lẽ sẽ chạy nhanh hơn FLOYD, đúng hem ta?

Ðề: Những thuật toán hay thi HSG Tin học
 

Khi D dùng Heap với ma trận kề thì độ phức tạp thuật toán là => Nhanh hơn Floyd. Nhưng nếu đồ thị đầy tức là thì Floyd lại nhanh hơn nên dùng Floyd ở đây!

Ðề: Những thuật toán hay thi HSG Tin học
 

Vậy nghĩa là chỉ trường hợp đó FLOYD mới nhanh hơn DIJKSTRA, haha, KA ui, tụi mình thắng kiện roài