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

[myhanh]

Còn nhiều lắm viết đến khi nào cho hết mà thời gian ko cho phép! Nếu như có gì cần hỏi em cứ post lên anh nói tiếp! Cái topic này do lần đổi host trước làm mất thời gian nên trình tự nó hơi lộn ngược. Em coi cái bài sau cùng trước nhé!

[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.

[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.

[khanhan2006_2009]

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ị.?

[myhanh]

Nguyên văn bởi khanhan2006_2009

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ị.?

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

[khanhan2006_2009]

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

[khanhan2006_2009]

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?"

[duyhung123abc]

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?

[myhanh]

Nguyên văn bởi duyhung123abc

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?

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!

[duyhung123abc]

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