Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Nén Đồ Thị Trong Các Thuật Toán Đấu Giá Tìm Đường Ngắn Nhất
Tóm tắt
Trong bài báo này, chúng tôi xem xét vấn đề tìm đường ngắn nhất từ một nút nguồn đến một nút đích cố định (SSP) hoặc đến tất cả các nút (SPT) trên một đồ thị có hướng. Một gia đình các thuật toán được phát triển từ thuật toán đấu giá đã biết được giới thiệu. Tính năng chính của các thuật toán này dựa trên những biến đổi topo thực hiện trên đồ thị nhằm thay thế một đoạn đường con tối ưu bằng một cung đơn lẻ có cùng độ dài (khái niệm nén đồ thị). Ý tưởng tương tự được áp dụng cho cả thuật toán đấu giá tiêu chuẩn và một phiên bản đã được sửa đổi của thuật toán này. Trong trường hợp đã đề cập, một khoản tiết kiệm đáng kể về chi phí tính toán được thu được như thể hiện trong các ví dụ số được báo cáo.
Từ khóa
#đường ngắn nhất #thuật toán đấu giá #đồ thị có hướng #biến đổi topo #nén đồ thịTài liệu tham khảo
D. Bertsekas, “A distributed algorithm for the assignment problem, ” Lab. for Information and Decision Systems, Working Paper, MIT, March 1979.
D. Bertsekas, “A distributed asynchronous relaxation algorithm for the assignment problem, ” in 24th IEEE Conference on Decision and Control, Ft Lauderdale, Fla., 1985, pp. 1703–1704.
D. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problems, ” Annals of Operation Research, vol. 14, pp. 105–123, 1988.
D. Bertsekas and D.A. Castanon, “The auction algorithm for minimum cost network flow problem, ” Lab. For Information and Decision Systems Report LIDS-P-1925, MIT, 1989.
D. Bertsekas and D.A. Castanon, “The auction algorithm for transportation problems, ” Annals of Operation Research, vol. 20, pp. 67–96, 1989.
D. Bertsekas and D.A. Castanon, “A generic auction algorithm for the minimum cost network flow problem, ” Lab. For Information and Decision Systems Report LIDS-P-2084, MIT, 1991.
D. Bertsekas, “The auction algorithm for shortest paths, ” SIAM J. on Optimization, vol. 1, pp. 425–447, 1991.
D. Bertsekas, Linear Networks Optimization: Algorithms and Codes, MIT Press, 1991.
D. Bertsekas, S. Pallottino, and M.G. Scutellá, “Polynomial auction algorithms for Shortest Paths, ” Computational Optimization and Application, vol. 4, pp. 99–125, 1995.
R. Cerulli, R. De Leone, and G. Piacente, “A modified auction algorithm for the shortest path problem, ” Optimization Methods and Software, vol. 4, 1994.
B.V. Chernassky, A.V. Goldberg, and T. Radzik, “Shortest path algorithms: Theory and experimental evaluation, ” Math. Programm. vol. 73, pp. 129–174, 1996.
E. Dijkstra, “A note on two problems in connexion with graphs, ” Numerishe Mathematik, vol. 1, 1959.
G. Gallo and S. Pallottino, “Shortest path methods: A unified approach, ” Math. Programming Study, vol. 26, pp. 38–64, 1986.
G. Gallo and S. Pallottino, “Shortest path methods, ” Ann. Oper. Res., vol. 13, pp. 3–79, 1988.
G. Gallo, S. Pallottino, C. Ruggeri, and G. Storchi, Metodi ed algoritmi per la determinazione di cammini minimi, Monografie di Software Matematico n. 29, 1984.
D. Klingman, A. Napier, and J. Stutz, “NETGEN—A program for generating large scale (un) capacitated assignment, transportation, and minimum cost flow network problems, ” Management Science, vol. 20, pp. 814–822, 1974.
J. Larsen and I. Pedersen, “Experiments with the auction algorithm for the shortest path problem, ” DIKU Technical Report 97/6.
S. Pallottino and M.G. Scutellá, “Strongly polynomial auction algorithms for shortest path, ” Ricerca Operativa, vol. 21, p. 60, 1991.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Practice-Hall: Eaglewood Cliffs, N.J., 1982.