Go Back   Cựu Học Sinh Lê Quý Đôn - Long An > :: Góc Học Tập :: > Tin học > Học lập trình

Học lập trình Pascal , C+ , C++ , VB

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

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

this thread has 48 replies and has been viewed 50805 times

Gởi Ðề Tài Mới Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 04-06-2008, 03:53 PM   #21
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

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é!
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 11:04 AM   #22
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: 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.
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 11:21 AM   #23
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

Trích:
Nguyên văn bởi khanhan2006_2009 View Post
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.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 04:28 PM   #24
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: 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ị.?
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 06:17 PM   #25
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

Trích:
Nguyên văn bởi khanhan2006_2009 View Post
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 đó.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 10:01 PM   #26
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

???????????????????????
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 10:02 PM   #27
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: 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?"
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 05-06-2008, 10:11 PM   #28
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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?
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Đã có thành viên gửi lời cám ơn đến duyhung123abc vì bạn đã đăng bài:
MyleneFero (15-10-2016)
Old 06-06-2008, 09:53 AM   #29
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Những thuật toán hay thi HSG Tin học

Trích:
Nguyên văn bởi duyhung123abc View Post
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!
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 06-06-2008, 11:37 AM   #30
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Trả lời


Ðiều Chỉnh
Xếp Bài

Quyền Sử Dụng Ở Diễn Ðàn
Bạn không được quyền gởi bài
Bạn không được quyền gởi trả lời
Bạn không được quyền gởi kèm file
Bạn không được quyền sửa bài

vB code đang Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt
Chuyển đến


Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Múi giờ GMT +7. Hiện tại là 11:43 PM.

Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này

Tự động[F9]TELEX VNI VIQR VIQR* TắtKiểm chính tảDấu cũ
phan mem quan ly ban hang | thuê vps