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
#36858
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
Tìm đường đi ngắt nhất thứ K 9 năm, 11 tháng trước   (+0)
Bài toán: cho đồ thị vô hướng N đỉnh, M cạnh và không có chu trình âm. Trong các đường đi đơn từ đỉnh S đến T, chỉ ra đường đi có trọng số nhỏ thứ k.
Mình mới biết thuật toán O(K*N^3) cho bài toán này. Ai có thuật toán tốt hơn thì share cho mình nhé!
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36860
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)
Theo mình thì bài này có một cách O(K * (N^2 + M))
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36866
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)
Như nào vậy bạn?
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
#36867
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)
Nếu chấp nhận chu trình thì có thể làm trong O(m+nlogn+k).

Nếu là đường đi đơn giản trên đồ thị tổng quát: trên đồ thị có hướng, thuật toán Yen thực hiện ở độ phức tạp O(kn(m+n log n)), còn trên đồ thị vô hướng, độ phức tạp là O(k(m+n log n)).
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.3724&rep=rep1&type=pdf
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36874
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)
Nếu là đường đi cho phép lặp đỉnh thì bài toán trở nên khá đơn giản rồi, dijkstra heap + cấu trúc dữ liệu hoặc là A*.
Nếu là đường đi không cho phép lặp đỉnh thì bài toán sẽ khó hơn rất nhiều (mình nghĩ thế có lẽ vì mình chưa nghĩ ra). Nghe nói có thể giải bằng Ford Bellman Queue vòng hoặc là dựng cây đường đi ngắn nhất sau đó quy hoạch động trên cây này (theo ý tưởng của anh Quỳnh - ĐH Công nghệ).

Thân ái,
HY TRƯỜNG SƠN
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36875
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ái bút: Mà quên mất chưa hỏi rõ bạn Tuấn Anh Ninh Bình là bài này là "K Shortest Paths" or "K Longest Paths" vì bạn ghi ở trên là đường đi dài thứ k.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36876
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)
Cách của mình nói cặn kẽ thì hơi dài dòng. Nhưng cơ bản là thế này, đầu tiên ta cực tiểu hóa các đường đi ngắn nhất từ S tới các đỉnh, rồi cực tiểu hóa các đường đi ngắn nhì, ... cuối cùng cực tiểu hóa đường đi ngắn thứ k.
- Bước 1: cực tiểu hóa đường đi ngắn nhất thì đơn giản
- Bước 2: cực tiểu hóa đường đi ngắn nhì: trước hết fải update các d[2, u] từ các d[1, v] (trong đó d[i, j] là đường đi ngắn thứ i từ S -> j, (u, v) là một cạnh nhưng lưu ý không update từ những d[1, v] thuộc đường đi ngắn nhất của d[1, u]). Sau đó Dijk giữa các d[2] như bình thường.
- Bước 3: update các d[3] giống như bước 2 từ các d[1, v] và d[2, v]. Nếu xử lí khéo kiểu cộng dồn thì có thể chỉ cần update từ d[2, v]. Dijk giữa các d[3].
* Như vậy ta mất K bước, mỗi bước mất một lần update mất M và một lần Dijk mất (NlogN + M) -> ĐPT là O(K*(NlogN + M)). Không biết là có giống cách trong tài liệu trên không?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36877
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)
Có thể dùng cấu trúc dữ liệu để tối ưu hơn nữa hoặc là có thể dùng thêm A* (N,K<=10000 vẫn ok, theo ý tưởng của anh Nguyễn Duy Khương)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36879
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
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)
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ả =.=
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#36880
tuananhnb2011 (Thành viên)
Đang tập code
Bài viết: 1
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ách củae lightning cũng ổn đó.Tuấn anh xài thử xem em
 
Đã lưu IP Đã lưu IP  
  Đã 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