- Tytuł:
-
Metody rozwiązywania problemu najkrótszych dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki w sieciach o strukturze kraty
Methods for solving node-disjoint shortest paths visiting specified nodes problem in mesh networks - Autorzy:
-
Tarapata, Z.
Wrocławski, S. - Powiązania:
- https://bibliotekanauki.pl/articles/210591.pdf
- Data publikacji:
- 2011
- Wydawca:
- Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
- Tematy:
-
drogi rozłączne wierzchołkowo
symulacja pola walki
generowanie podgrafów
planowanie przemieszczania
node-disjoint paths
battlefield simulation
subgraphs generating
movement planning - Opis:
-
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.
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. - Źródło:
-
Biuletyn Wojskowej Akademii Technicznej; 2011, 60, 4; 201-229
1234-5865 - Pojawia się w:
- Biuletyn Wojskowej Akademii Technicznej
- Dostawca treści:
- Biblioteka Nauki
Artykuł