Metody rozwiązywania problemu najkrótszych dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki w sieciach o strukturze kraty

• Autorzy: Tarapata Z. , Wrocławski S.

Warianty tytułu

EN

Methods for solving node-disjoint shortest paths visiting specified nodes problem in mesh networks

• Języki publikacji: PL

Abstrakty

PL

W pracy zaprezentowano modele i metody służące do rozwiązywania problemu wyznaczania K dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki, o najmniejszym sumarycznym koszcie w sieci prostokątnej (tzw. kracie) opartej o graf G. Zdefiniowano problem jako zadanie optymalizacji liniowej ciągłej oraz przedstawiono dwie metody przybliżone jego rozwiązania: metodę SGDP (bazującą na pewnej iteracyjnej procedurze wyznaczania dróg najkrótszych w podgrafach grafu G) oraz modyfikację metody Edmondsa-Karpa rozwiązywania problemu wyznaczania przepływu zaspokajającego o minimalnym koszcie. Przeprowadzono analizę ich złożoności oraz dokonano porównania jakości obu metod na podstawie eksperymentalnych wyników.

EN

In the paper, models and methods for solving K node-disjoint shortest paths visiting specified nodes problem in mesh networks (based on a graph G) have been presented. The problem has been defined as continuous linear programming problem and two approximation methods for solving it have been presented: SGDP method (based on some iterative procedure of finding shortest paths in subgraphs of G) and modification of Edmond's-Karp method for solving minimal cost flow problem. Complexity and quality analysis of presented methods based on experimental results using real terrain models have been done.

Słowa kluczowe

PL

drogi rozłączne wierzchołkowo; symulacja pola walki; generowanie podgrafów; planowanie przemieszczania

EN

node-disjoint paths; battlefield simulation; subgraphs generating; movement planning

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Biuletyn Wojskowej Akademii Technicznej
• Rocznik: 2011
• Tom: Vol. 60, nr 4
• Strony: 201--229
• Opis fizyczny: Bibliogr. 36 poz., wykr.

Twórcy

autor

Tarapata Z.

autor

Wrocławski S.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Systemów Informatycznych, 00-908 Warszawa, ul. S. Kaliskiego 2,

Bibliografia

• [1] A. Aggarwal, J. Kleinberg, D. Williamson, Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout, SIAM Journal on Computing, 29, 4, 2000, 1321-1333.
• [2] R. Andersen, F. Chung, A. Sen, G. Xue, On Disjoint Path Pairs with Wavelength Continuity Constraint in WDM Networks, Proceedings of the IEEE Infocom'2004, Hong Kong (China), 7-11 March, 2004, 524-535.
• [3] R. Antkiewicz, W. Kulas, A. Najgebauer, D. Pierzchała, J. Rulka, Z. Tarapata, R. Wantoch-Rekowski, The Automation of Combat Decision Processes in the Simulation Based Operational Training Support System, Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Security and Defense Applications (CISDA), Honolulu (Hawaii, USA), April 1-5 2007.
• [4] J. R. Benton, S. S. Iyengar, W. Deng, N. Brener, V. S. Subrahmanian, Tactical route planning: new algorithms for decomposing the map, Proceedings of the IEEE International Conference on Tools for AI, 268-277, 1995.
• [5] R. Bhandari, Survivable networks. Algorithms for Diverse Routing, Boston, 2001.
• [6] G. S. Brodal, Fast Meldable Priority Queues, Proceedings of the 4th International Workshop on Algorithms and Data Structures, London, 282-290, 1995.
• [7] R. G. Busacker, P. J. Gowen, A procedure for determining a family of minimum-cost flow patterns, Operations Research Office Technical Report 15, John Hopkins University, Baltimore, 1961.
• [8] C. Campbell, R. Hull, E. Root, L. Jackson, Route planning in CCTT, Proceedings of the 5 th. Conference on Computer Generated Forces and Behavioural Representation, University of Central Florida, 233-244, 1995.
• [9] E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, 1, 1959, 269-271.
• [10] J. Edmonds, R. M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM, 19, 2, 1972, 248-264.
• [11] D. Eppstein, Finding common ancestors and disjoint paths in DAGs, Technical Report 95-52, Department of Information and Comp. Science, Univ. of California, Irvine, 1995.
• [12] S. Even, A. Itai, A. Shamir, On the complexity of time-table and multicommodity flow problems, SIAM Journal on Computing, 5, 1976, 691-703.
• [13] J. F. Lynch, The equivalence of theorem proving and the interconnection problem, SIG DA Newsletter, 5, 3, 1975, 31-36.
• [14] A. Jongh, M. Gendreau, M. Labbe, Finding disjoint routes in telecommunications networks with two technologies, Operations Research, 47, 1999, 81-92.
• [15] R. M. Karp, On the computational complexity of combinatorial problems, Networks, 5, 1975, 48-68.
• [16] T. Kreitzberg, T. Barragy, B. Nevin, Tactical movement analyzer: a battlefield mobility tool, Proceedings of the 4th Join Tactical Fusion Symposium, 1990, 363-383.
• [17] C. L. Li, S. T. McCormick, D. Simchi-Levi, Finding disjoint paths with different path-costs: Complexity and algorithms, Networks, 22, 1992, 653-667.
• [18] C. L. Li, S. T. McCormick, D. Simchi-Levi, The complexity of finding two disjoint paths with min-max objective function, Discrete Applied Math., 26, 1990, 105-115.
• [19] M. Longtin, D. Megherbi, Concealed routes in ModSAF, Proceedings of the 5th Conference on Computer Generated Forces and Behavioral Representation, University of Central Florida, 1995, 305-314.
• [20] Y. Perl, Y. Shiloach, Finding two disjoint paths between two pairs of vertices in a graph, Journal of the ACM, 25, 1978, 1-9.
• [21] M. D. Petty, Computer generated forces in Distributed Interactive Simulation, Proceedings of the Conference on Distributed Interactive Simulation Systems for Simulation and Training in the Aerospace Environment, The International Society for Optical Engineering, Orlando, 1995, 251-280.
• [22] A. Schrijver, P. Seymour, Disjoint paths in a planar graph - a general theorem, SIAM Journal of Discrete Mathematics, 5, 1, 1992, 112-116.
• [23] H. Sherali, K. Ozbay, S. Subramanian, The time-dependent shortest pair of disjoint paths problem: complexity, models and algorithms, Networks, 31, 1998, 259-272.
• [24] J. W. Suurballe, Disjoint paths in a network, Networks, 4, 1974, 125-145.
• [25] J. W. Suurballe, R. E. Tarjan, A quick method for finding shortest pairs of disjoint paths, Networks, 14, 1984, 325-336.
• [26] Z. Tarapata, Multi-paths optimization in unreliable time-dependent networks, Proceedings of The 2nd NATO Regional Conference on Military Communication and Information Systems, 04-06 October, Zegrze, 1, 2000, 181-189.
• [27] Z. Tarapata, Modeling, optimization and simulation of groups movement according to group pattern in multiresolution terrain-based grid network, Proceedings of The Regional Conference on Military Communication and Information Systems, Zegrze, 1, 2001, 241-251.
• [28] Z. Tarapata, Military route planning in battlefield simulation: effectiveness problems and potential solutions, Journal of Telecommunications and Information Technology, 4, 2003, 47-56.
• [29] Z. Tarapata, Modele harmonogramowania zsynchronizowanego przemieszczania wielu obiektów, Badania Operacyjne i Decyzje, 2, 2007, 83-103.
• [30] Z. Tarapata, Algorytmy harmonogramowania zsynchronizowanego przemieszczania wielu obiektów, Badania Operacyjne i Decyzje, 4, 2008, 101-132.
• [31] Z. Tarapata, Zastosowanie metod wyznaczania przepływu w sieciach do planowania manewru wojsk, Biuletyn Instytutu Systemów Informatycznych, 2, 2008, 31-44.
• [32] Z. Tarapata, Approximation Scheduling Algorithms for Solving Multi-objects Movement Synchronization Problem, ICANNGA '2009, Lecture Notes in Computer Science, 5495, Springer, Heidelberg, 2009, 577-589.
• [33] Z. Tarapata, Movement Simulation and Management of Cooperating Objects in CGF Systems: a Case Study, KES-AMSTA'2010, Lecture Notes in Artificial Intelligence, 6070, Springer, Heidelberg, 2010, 293-304.
• [34] Z. Tarapata, Multiresolution models and algorithms of movement planning and their application for multiresolution battlefield simulation, ACII DS'2010, Lecture Notes in Artificial Intelligence, 5991, Springer, Heidelberg, 2010, 378-389.
• [35] Z. Tarapata, S. Wrocławski, Subgraphs Generating Algorithm for Obtaining Set of Node-Disjoint Paths in Terrain-Based Mesh Graphs, MIG'2010, Lecture Notes in Computer Science, 6459, Springer, Heidelberg, 2010, 398-409.
• [36] S. Wrocławski, Analiza wybranych modeli i metod wspomagania decyzji w sytuacjach konfliktowych, praca magisterska pod kierunkiem Z. Tarapaty, Wydział Cybernetyki, WAT, Warszawa, 2010.