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
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.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00