Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: Tìm đường đi ngắt nhất thứ K (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - Trả lời: Tìm đường đi ngắt nhất thứ K
#36881
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
Xin lỗi mọi người vì viết sai chính tả tên toppic .
Dù sao đọc kĩ thì cũng đoán ra là mình hỏi về đường đi đơn ngắn nhất thứ k.

Ngoài thuật toán Yen ra thì mình biết là còn có Katoh và Hoffman và 2 cái này đều tốt hơn. Nhưng thuật toán chi tiết thế nào thì mình chưa tìm được tài liệu. Thế nên mới phải hỏi mọi người :d.

@anh vanhoa có lẽ anh nhầm về dpt của thuật toán trong trường hợp đường đi có thể có chu trình.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36883
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (-1)
Ý tưởng -> hành động (cái này ai học triết sẽ biết). Nhiều ý tưởng điên rồ được giải Nobel (thực tế đã chứng minh, không tin lên mạng search). Nêu ý tưởng của những cá nhân khác không phải là cách tự phủ định bản thân mình. Ngoài ý tưởng của anh Quỳnh thì em đã thấy 80% code của tất cả các ý tưởng còn lại (của những người có máu mặt mà anh đã từng gặp). Nhiều topic trên VNOI cũng chỉ có những ý tưởng nhỏ ban đầu nhưng từ đó rất nhiều members acc các bài mình chưa làm được (đúng hay sai thì tự lên VNOI mà thống kê). Muốn tiếp thu ý tưởng nào thì người chủ topic (mà ở đây là bạn Tuấn Anh) cần có sự chọn lọc và suy nghĩ. Chém gió hay không chém gió có lẽ nên để thời gian và mọi người phán xét.

Thân ái,
HY TRƯỜNG SƠN
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36884
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (-1)
@Tuấn Anh Ninh Bình: Lần sau nói đề bài thì bạn cố gắng nói rõ vào kẻo xảy ra rất nhiều hiểu lầm.

Tái bút: Rất vui vì được gặp và trao đổi với bạn.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36895
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
@Sơn: Lần sau mình sẽ cẩn thận hơn.
Anh Trung nói thế là do những ý tưởng mà cậu đưa ra chỉ là tên các thuật toán cơ bản và rất khó để người đọc dẫn đến hành động được. Đã là tìm đường đi ngắn nhất thì ai chả nghĩ đến mấy thuật toán đó. Bạn đã được xem code thì cố gắng nói rõ hơn tư tưởng thuật toán cho mọi người nhé!
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36897
lightning31 (Thành viên)
lightning31
Nhắm mắt code không bug
Bài viết: 168
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
EternalAutumn viết:
QUOTE:
Anh vanhoa có thể nói rõ hơn cách chấp nhận chu trình được ko ạ?

@Sơn + Tùng: đồ thị ko có chu trình âm chứ vẫn có cạnh trọng số âm mà --> dijk ?
@Sơn: mấy cái em nói chỉ là ý tưởng nhưng thực tế thì nó chả hề đơn giản và dễ hình dung thế nào. Em đã cài thử và ACC được với cách A* chưa? Nếu có thì em nên nói chi tiết là em định làm ntn vì anh thấy biết ý tưởng thế cũng chả có ý nghĩa thực tế gì cả. Đâu phải cứ nói tên người nêu ra ý tưởng là nó chắc chắn đúng và có ý nghĩa :| Nói đơn giản thì nói mỗi ý tưởng thế chả khác gì chém gió cả =.=

@Anh RR: Đúng là em không để ý thật.
Nhưng mà để biến đổi đồ thị về thành đồ thị không có cạnh âm cũng không khó lắm anh ạ.
- Trước hết dùng FordBellMan một lần tính được đường đi ngắn nhất từ S đến các đỉnh còn lại gọi đường đi đó là c[i].
- Với mỗi cạnh (u, v) có trọng số cost[u, v] ta thay cost[u, v] bằng cost[u, v] - c[v] + c[u].
* Nhận xét:
+ ta thấy giữa cost[u, v] >= c[v] - c[u] (với mọi u, v) (vì nếu cost[u, v] < c[v] - c[u] thì c[v] không còn lai đường đi ngắn nhất từ S -> v nữa) => Sau khi biến đổi thì mọi cạnh trong đồ thi đều ko âm.
+ Hơn nữa ta xét một đường đi bất kì từ S -> u bất kì. Giả sử qua A, B, C sẽ bằng: cost[S, A] - c[A] + c[S] + cost[A, B] - c[B] + c[A] + ... + cost[C, u] - c[u] + c[C] = cost[S, A] + cost[A, B] + .. + cost[C, u] + c[S] - c[u] -> Mọi đường từ S -> u sẽ đều tăng thêm một chi phí là c[S] - c[u]. Vậy thứ tự đường ngắn thứ k từ S-> u là không đổi. Sau khi biến đổi trọng số của đồ thị, ta áp dụng thuật toán em nêu ở bài trên là ok. Kết quả chỉ cần trừ đi (c[S] - c[T]) là ổn.

* vậy độ phức tạp vẫn như trên cộng thêm đoạn FOrdBellMan ban đầu thì ĐPT sẽ là: O(n^3 + k(m + nlogn))
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36898
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
Cảm ơn lightning31.
Cách loại bỏ cạnh âm để dijk như vậy là ổn rồi. Chỉ có điều mình vẫn chưa hiểu cách update d[i] từ các d[j < i]. Để mình xem kĩ lại vậy.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36904
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (-1)
@Tuấn Anh: Bạn có bộ test + đề chính thức + nguồn của bài này không? Nếu có thì chia sẻ đi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36905
vanhoa (Thành viên)
vanhoa+18
Nhắm mắt code không bug
Bài viết: 147
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
@mr_invincible: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
@son: A* chỉ dùng tốt cho các đồ thị mà phần định lượng khoảng cách giữa 2 cặp điểm có thể xử lý tốt, ví dụ ở các đồ thị lưới. Với đồ thị tổng quát họ không xài A* nữa mà xài các thuật toán di truyền khác có tốc độ tốt hơn.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36906
vanhoa (Thành viên)
vanhoa+18
Nhắm mắt code không bug
Bài viết: 147
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
@tuananh: Em tham khảo thuật toán Yen ở đây http://www.mat.uc.pt/~eqvm/OPP/KSPP/KSPP.html
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36908
tuananh93x (Admin)
tuananhnb93+129
Admin
Bài viết: 436
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tìm đường đi ngắt nhất thứ K 9 năm, 10 tháng trước   (+0)
@anh vanhoa: thank anh, mặc dù thuật toán Yen em đã biết rồi.
@Sơn: cái này mình tình cờ đọc được thôi, không phải từ contest nào cả.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
  • Trang:
  • << < 1 2 > >>
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS