Wikipedia

Bài toán đường đi rộng nhất

Bài toán đường đi rộng nhất, còn gọi là bài toán đường đi nút cổ chai rộng nhất hay bài toán tìm đường đi có khả năng thông qua lớn nhất, là bài toán yêu cầu tìm đường đi giữa hai đỉnh trong đồ thị có hướng có trọng số sao cho trọng số của cung có trọng số nhỏ nhất là lớn nhất có thể.

Trong đồ thị này, đường đi rộng nhất từ Maldon tới Feering có chiều rộng 29, và đi qua Clacton, Tiptree, Harwich, và Blaxhall.

Một ví dụ cụ thể là khi đồ thị biểu diễn mạng lưới các bộ định tuyến trên mạng internet, và trọng số của các cung là băng thông của cáp nối giữa hai bộ định tuyến. Bài toán đường đi rộng nhất tương ứng với tìm đường đi giữa hai bộ định tuyến cho trước với băng thông lớn nhất có thể.[1] Chiều rộng của cung hẹp nhất được gọi là khả năng thông qua hay băng thông của đường đi. Ngoài ứng dụng trong định tuyến trên mạng, bài toán đường đi rộng nhất còn là một thành phần quan trọng của phương pháp Schulze cho việc xác định người thắng cuộc trong bầu cử nhiều ứng cử viên[2], và có ứng dụng trong tổng hợp số,[3] phân tích sự trao đổi chất,[4] và trong thuật toán tìm luồng cực đại.[5] Hầu hết các thuật toán tìm đường đi ngắn nhất đều có thể được sửa đổi để tính đường đi rộng nhất thay vì đường đi ngắn nhất.[6] Tuy nhiên, trong nhiều trường hợp, có những thuật toán nhanh hơn để tính đường đi rộng nhất.

Một bài toán liên quan mang tên bài toán đường đi minimax yêu cầu tìm đường đi sao cho trọng số lớn nhất trên đường là nhỏ nhất có thể. Bất kì thuật toán tìm đường đi rộng nhất nào cũng đều có thể được dùng để tìm đường đi minimax và ngược lại, bằng cách đảo ngược tất cả các phép so sánh của thuật toán hoặc thay mọi trọng số bằng số đối của chúng.

Đồ thị vô hướng

sửa

Trong đồ thị vô hướng, đường đi rộng nhất giữa hai đỉnh chính là đường đi giữa chúng trên cây bao trùm lớn nhất của đồ thị, và đường đi minimax giữa hai đỉnh chính là đường đi trên cây bao trùm nhỏ nhất.[7][8][9]

Trong bất kì đồ thị nào, dù có hướng hay vô hướng, đều có thể áp dụng thuật toán đơn giản sau để tìm đường đi rộng nhất sau khi đã biết trọng số nhỏ nhất trên đường đi đó: xóa tất cả các cung có trọng số nhỏ hơn và tìm đường đi trên các cung còn lại bằng tìm kiếm theo chiều rộng hoặc tìm kiếm theo chiều sâu. Dựa trên ý tưởng này, có thể xây dựng một thuật toán chạy trong thời gian tuyến tính để tìm đường đi rộng nhất từ s đến t mà không cần đến cây bao trùm lớn nhất. Ý tưởng chính của thuật toán là tìm trọng số trung vị trong đồ thị, rồi kiểm tra xem có tồn tại đường đi rộng hơn giá trị trung vị hay không theo phương pháp trên. Nếu đường đi tồn tại, thì xóa hết các cung nhỏ hơn giá trị trung vị. Nếu đường đi không tồn tại, thì hợp mỗi thành phần liên thông tạo bởi các cung lớn hơn lại thành một đỉnh. Trong cả hai trường hợp, thuật toán tiếp tục trên đồ thị nhỏ hơn mới thu được.[8][10][11]

Đồ thị có hướng

sửa

Có nhiều thuật toán khác nhau cho đồ thị có hướng, tùy theo nhu cầu sử dụng chẳng hạn như đỉnh xuất phát hay kết thúc có cố định hay không, và có cần tìm đường cho nhiều cặp đỉnh cùng một lúc hay không.

Mọi cặp đỉnh

sửa

Bài toán đường đi rộng nhất giữa mọi cặp đỉnh có ứng dụng trong phương pháp Schulze để xác định người thắng cuộc trong bầu cử với nhiều ứng cử viên trong đó trên mỗi phiếu, các ứng cử viên được xếp hạng theo thứ tự ưu tiên. Phương pháp Schulze xây dựng một đồ thị đấu loại trong đó mỗi đỉnh biểu diễn một ứng cử viên và hai đỉnh bất kì đều được nối với nhau bằng 1 cung. Mỗi cung có hướng từ người thắng cuộc đến người thua cuộc trong cuộc đấu tay đôi giữa hai ứng viên ở hai đầu của cung, và được gắn nhãn bằng chênh lệch giữa hai người. Sau đó, tính đường đi rộng nhất giữa mọi cặp đỉnh của đồ thị và người thắng cuộc là ứng cử viên có đường đi tới mỗi đối thủ rộng hơn đường đi rộng nhất theo hướng ngược lại.[2]. Kết quả của phương pháp này tương thích với phương pháp Condorcet - nếu một ứng cử viên thắng trong tất cả các kết quả so sánh tay đôi thi người đó thắng chung cuộc - nhưng nó cũng cho phép lựa chọn người thắng cuộc trong nhiều trường hợp khi phương pháp Condorcet thất bại.[12] Phương pháp Schulze đã được sử dụng bởi nhiều tổ chức, chẳng hạn như Wikimedia Foundation.[13]

Để tính chiều rộng của đường đi rộng nhất giữa mọi cặp đỉnh trong đồ thị trù mật có hướng, chẳng hạn như đồ thị thu được trong ứng dụng bầu cử, thuật toán nhanh nhất hiện nay chạy trong thời gian O(n(3+ω)/2) trong đó ω là lũy thừa trong thời gian chạy của thuật toán nhân ma trận nhanh. Nếu sử dụng thuật toán nhân ma trận nhanh nhất hiện nay, thì độ phức tạp trên trở thành O(n2.688).[14] Thay vào đó, cách lập trình thông thường của phương pháp Schulze sử dụng một phiên bản của thuật toán Floyd-Warshall chạy trong thời gian O(n3).[2] Trên đồ thị thưa, có thể việc chạy thuật toán tìm đường đi rộng nhất với đỉnh nguồn cố định nhiều lần còn hiệu quả hơn các phương pháp trên.

Một đỉnh nguồn cố định

sửa

Nếu độ dài các cạnh đã được sắp xếp thì có thể sử dụng một biến thể của thuật toán Dijkstra để tìm các đường đi rộng nhất từ một đỉnh nguồn cố định tới tất cả các đỉnh khác trong thời gian tuyến tính. Ý tưởng chính ở đây là trong bài toán đường đi rộng nhất, thứ tự các đỉnh được xem xét trong thuật toán chính là một dãy con tăng dần của danh sách các cung sắp xếp theo trọng số. Do đó hàng đợi ưu tiên của thuật toán Dijkstra trong trường hợp này có thể thay bằng một mảng kích thước m lưu trữ các cung của đồ thị theo trọng số tăng dần. Phương pháp này cho phép tìm kiếm đường đi rộng nhất trong thời gian ngang với thời gian sắp xếp. Nếu các trọng số là số nguyên thì thuật toán có cùng thời gian chạy với thuật toán sắp xếp số nguyên.[11]

Một nguồn và một đích

sửa

Có thể tìm đường đi rộng nhất cho một đỉnh nguồn và một đỉnh đích duy nhất một cách hiệu quả ngay cả trong mô hình chỉ cho phép so sánh trọng số của các cung mà không được tính toán trên chúng.[11][15] Thuật toán duy trì một tập hợp các cung S sao cho các cung trên đường đi rộng nhất chắc chắn nằm trong S. Ban đầu, S chứa tất cả m cung của đồ thị. Trong mỗi lượt, thuật toán chia tập S thành một danh sách các tập con được sắp thứ tự S1, S2,... (các số trong tập trước nhỏ hơn hoặc bằng các số trong tập sau) có kích thước xấp xỉ nhau. Số lượng tập hợp con được chọn sao cho các giá trị để phân chia S thành các tập con có thể được xác định bằng cách lặp đi lặp lại việc tìm phần tử trung vị trong thời gian O(m). Sau đó, thuật toán thay trọng số của các cung trên đồ thị bằng số thứ tự của tập chứa nó. Do ta đã có danh sách các cung sắp xếp theo trọng số mới, có thể tìm đường đi rộng nhất trong thời gian tuyến tính theo kết quả ở trên và do đó xác định được cung hẹp nhất của đường đi nằm trong tập nào. Sau đó, thuật toán thay tập S bằng tập Si đã được xác định là chứa cung hẹp nhất trên đường, và lặp lại các bước trên. Số lượng tập hợp mà ta có thể chia S tăng theo hàm mũ sau mỗi lần lặp nên số lần lặp là O(log*n). Tổng thời gian, do đó, là O(m log*n).[15] Khi các trọng số là số nguyên, bước lặp đi lặp lại việc tìm kiếm trung vị có thể thay bằng kĩ thuật phân chia danh sách bởi Han & Thorup (2002), cho phép chia S thành   tập con Si trong một bước và toàn bộ thuật toán chạy trong thời gian tuyến tính.[16]

Ghi chú

sửa
  1. ^ Shacham, N. (1992), “Multicast routing of hierarchical data”, IEEE International Conference on Communications (ICC '92), 3, tr. 1217–1221, doi:10.1109/ICC.1992.268047; Wang, Zheng; Crowcroft, J. (1995), “Bandwidth-delay based routing algorithms”, IEEE Global Telecommunications Conference (GLOBECOM '95), 3, tr. 2129–2133, doi:10.1109/GLOCOM.1995.502780
  2. ^ a b c Schulze, Markus (2011), “A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method”, Social Choice and Welfare, 36 (2): 267–303, doi:10.1007/s00355-010-0475-4
  3. ^ Fernandez, Elena; Garfinkel, Robert; Arbiol, Roman (1998), “Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths”, Operations Research, 46 (3): 293–304, JSTOR 222823
  4. ^ Ullah, E.; Lee, Kyongbum; Hassoun, S. (2009), “An algorithm for identifying dominant-edge metabolic pathways”, IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009), tr. 144–150
  5. ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), “7.3 Capacity Scaling Algorithm”, Network Flows: Theory, Algorithms and Applications, Prentice Hall, tr. 210–212, ISBN 0-13-617549-X
  6. ^ Pollack, Maurice (1960), “The maximum capacity through a network”, Operations Research, 8 (5): 733–736, JSTOR 167387
  7. ^ Hu, T. C. (1961), “The maximum capacity route problem”, Operations Research, 9 (6): 898–900, JSTOR 167055
  8. ^ a b Punnen, Abraham P. (1991), “A linear time algorithm for the maximum capacity path problem”, European Journal of Operational Research, 53 (3): 402–404, doi:10.1016/0377-2217(91)90073-5
  9. ^ Malpani, Navneet; Chen, Jianer (2002), “A note on practical construction of maximum bandwidth paths”, Information Processing Letters, 83 (3): 175–180, doi:10.1016/S0020-0190(01)00323-4, MR 1904226
  10. ^ Camerini, P. M. (1978), “The min-max spanning tree problem and some extensions”, Information Processing Letters, 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3
  11. ^ a b c Kaibel, Volker; Peinhardt, Matthias A. F. (2006), On the bottleneck shortest path problem (PDF), ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Bản gốc (PDF) lưu trữ ngày 7 tháng 8 năm 2011, truy cập ngày 25 tháng 9 năm 2011
  12. ^ Cụ thể hơn, trường hợp duy nhất phương pháp Schulze không thể phân định người thắng cuộc là khi hai ứng viên có đường đi rộng bằng nhau đi tới nhau
  13. ^ Xem Jesse Plamondon-Willard, Board election to use preference voting, tháng 5 năm 2008; Mark Ryan, 2008 Wikimedia Board Election results, tháng 6 năm 2008; Bầu cử hội đồng năm 2008, tháng 6 năm 2008; và Bầu cử hội đồng năm 2009, tháng 8 năm 2009.
  14. ^ Duan, Ran; Pettie, Seth (2009), “Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths”, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), tr. 384–391 Có thể tham khảo một thuật toán cũ hơn cũng sử dụng nhân ma trận nhanh ở Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael (2007), “All-pairs bottleneck paths for general graphs in truly sub-cubic time”, Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC '07), New York: ACM, tr. 585–589, doi:10.1145/1250790.1250876, MR 2402484 và chương 5 của Vassilevska, Virginia (2008), Efficient Algorithms for Path Problems in Weighted Graphs (PDF), Ph.D. thesis, Report CMU-CS-08-147, Carnegie Mellon University School of Computer Science
  15. ^ a b Gabow, Harold N.; Tarjan, Robert E. (1988), “Algorithms for two bottleneck optimization problems”, Journal of Algorithms, 9 (3): 411–417, doi:10.1016/0196-6774(88)90031-4, MR 0955149
  16. ^ Han, Yijie; Thorup, M. (2002), “Integer sorting in   expected time and linear space”, Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), tr. 135–144, doi:10.1109/SFCS.2002.1181890.
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Bài_toán_đường_đi_rộng_nhất&oldid=69948300”