Problem najszerszej ścieżki
W algorytmach grafowych problem najszerszej ścieżki to problem znalezienia ścieżki między dwoma wyznaczonymi wierzchołkami w grafie ważonym , maksymalizujący wagę krawędzi o minimalnej wadze na ścieżce. Problem najszerszej ścieżki jest również znany jako problem ścieżki maksymalnej pojemności . Możliwe jest dostosowanie większości najkrótszej ścieżki do obliczania najszerszych ścieżek, modyfikując je tak, aby wykorzystywały odległość wąskiego gardła zamiast długości ścieżki. Jednak w wielu przypadkach możliwe są jeszcze szybsze algorytmy.
Na przykład na wykresie przedstawiającym połączenia między routerami w Internecie , gdzie waga krawędzi reprezentuje przepustowość połączenia między dwoma routerami, problem z najszerszą ścieżką to problem znalezienia ścieżki od końca do końca między dwoma Internetami węzłów o maksymalnej możliwej przepustowości. Najmniejsza waga krawędzi na tej ścieżce jest znana jako przepustowość lub przepustowość ścieżki. Oprócz zastosowań w routingu sieciowym, problem najszerszej ścieżki jest również ważnym elementem metody Schulze do wyłonienia zwycięzcy wielostronnych wyborów i została zastosowana w komponowaniu cyfrowym , analizie szlaków metabolicznych i obliczaniu maksymalnych przepływów .
Ściśle powiązany problem, problem ścieżki minimax lub problem najkrótszej ścieżki w wąskim gardle, wymaga ścieżki, która minimalizuje maksymalną wagę dowolnej z jej krawędzi. Posiada aplikacje, które obejmują planowanie transportu . Dowolny algorytm dla problemu z najszerszą ścieżką można przekształcić w algorytm dla problemu ze ścieżką minimax lub odwrotnie, odwracając sens wszystkich porównań wag przeprowadzonych przez algorytm lub równoważnie, zastępując każdą wagę krawędzi jej negacją.
Grafy nieskierowane
W grafie nieskierowanym najszerszą ścieżkę można znaleźć jako ścieżkę między dwoma wierzchołkami w maksymalnym drzewie rozpinającym grafu, a ścieżkę minimaksową można znaleźć jako ścieżkę między dwoma wierzchołkami w minimalnym drzewie rozpinającym.
W każdym grafie, skierowanym lub nieskierowanym, istnieje prosty algorytm znajdowania najszerszej ścieżki, gdy znana jest waga jego krawędzi o minimalnej wadze: po prostu usuń wszystkie mniejsze krawędzie i wyszukaj dowolną ścieżkę wśród pozostałych krawędzi, używając przeszukiwania wszerz lub przeszukiwanie w głąb . Na podstawie tego testu istnieje również liniowy algorytm czasu do znajdowania najszerszej ścieżki s - t w grafie nieskierowanym, który nie wykorzystuje maksymalnego drzewa rozpinającego. Główną ideą algorytmu jest zastosowanie algorytmu znajdowania ścieżki w czasie liniowym do mediany wagi krawędzi na grafie, a następnie albo usunąć wszystkie mniejsze krawędzie, albo skrócić wszystkie większe krawędzie w zależności od tego, czy ścieżka istnieje, czy nie, i rekurencyjnie w wynikowym mniejszym grafie.
Fernández, Garfinkel i Arbiol (1998) wykorzystują nieukierunkowane najkrótsze ścieżki wąskich gardeł, aby utworzyć złożone zdjęcia lotnicze , które łączą wiele obrazów nakładających się obszarów. W podproblemie, do którego odnosi się problem najszerszej ścieżki, dwa obrazy zostały już przekształcone we wspólny układ współrzędnych ; pozostałe zadanie polega na wybraniu szwu , krzywej przechodzącej przez obszar nakładania się i oddzielającej jeden z dwóch obrazów od drugiego. Piksele po jednej stronie łączenia zostaną skopiowane z jednego obrazu, a piksele po drugiej stronie łączenia zostaną skopiowane z drugiego obrazu. W przeciwieństwie do innych metod komponowania, które uśredniają piksele z obu obrazów, daje to prawidłowy obraz fotograficzny każdej części fotografowanego regionu. Obciążają krawędzie a wykres siatki za pomocą liczbowego oszacowania, jak wizualnie widoczny byłby szew na tej krawędzi, i znajdź najkrótszą ścieżkę wąskiego gardła dla tych ciężarów. Używanie tej ścieżki jako łączenia, zamiast bardziej konwencjonalnej najkrótszej ścieżki, powoduje, że ich system znajduje szew, który jest trudny do rozróżnienia we wszystkich jego punktach, zamiast pozwolić mu na zamianę większej widoczności w jednej części obrazu na mniejszą widoczność gdzie indziej.
Rozwiązanie problemu ścieżki minimax między dwoma przeciwległymi wierzchołkami wykresu siatki może być użyte do znalezienia słabej odległości Frécheta między dwoma łańcuchami wielokątnymi . Tutaj każdy wierzchołek wykresu siatki reprezentuje parę segmentów linii, po jednym z każdego łańcucha, a waga krawędzi reprezentuje odległość Frécheta potrzebną do przejścia z jednej pary segmentów do drugiej.
Jeśli wszystkie wagi krawędzi grafu nieskierowanego są dodatnie , to minimalne odległości między parami punktów (maksymalne wagi krawędzi ścieżek minimax) tworzą ultrametrykę ; odwrotnie, każda skończona przestrzeń ultrametryczna pochodzi w ten sposób z minimalnych odległości. Struktura danych zbudowana z minimalnego drzewa rozpinającego umożliwia zapytanie o minimalną odległość między dowolną parą wierzchołków w stałym czasie na zapytanie, przy użyciu zapytań o najniższego wspólnego przodka w drzewie kartezjańskim . Korzeń drzewa kartezjańskiego reprezentuje najcięższą minimalną krawędź drzewa rozpinającego, a dzieci korzenia to drzewa kartezjańskie rekurencyjnie zbudowane z poddrzew minimalnego drzewa rozpinającego utworzonego przez usunięcie najcięższej krawędzi. Liście drzewa kartezjańskiego reprezentują wierzchołki grafu wejściowego, a minimalna odległość między dwoma wierzchołkami jest równa wadze węzła drzewa kartezjańskiego, który jest ich najniższym wspólnym przodkiem. Po posortowaniu minimalnych krawędzi drzewa rozpinającego to drzewo kartezjańskie można zbudować w czasie liniowym.
Grafy skierowane
W grafach skierowanych nie można zastosować rozwiązania maksymalnego drzewa rozpinającego. Zamiast tego znanych jest kilka różnych algorytmów; wybór algorytmu zależy od tego, czy wierzchołek początkowy lub docelowy dla ścieżki jest ustalony, czy też ścieżki dla wielu wierzchołków początkowych lub docelowych muszą być znalezione jednocześnie.
Wszystkie pary
Problem najszerszej ścieżki dla wszystkich par ma zastosowanie w metodzie Schulze'a do wybierania zwycięzcy w wyborach wielostronnych , w których wyborcy oceniają kandydatów w kolejności preferencji . Metoda Schulze konstruuje kompletny graf skierowany , w którym wierzchołki reprezentują kandydatów, a każde dwa wierzchołki są połączone krawędzią. Każda krawędź jest skierowana od zwycięzcy do przegranego walki parami między dwoma kandydatami, których łączy, i jest oznaczona marginesem zwycięstwa tej walki. Następnie metoda oblicza najszersze ścieżki między wszystkimi parami wierzchołków, a zwycięzcą jest kandydat, którego wierzchołek ma szersze ścieżki do każdego przeciwnika niż odwrotnie. Wyniki wyborów tą metodą są zgodne z tzw Metoda Condorcet – kandydat, który wygra wszystkie konkursy parami, automatycznie wygrywa całe wybory – ale generalnie pozwala wyłonić zwycięzcę, nawet w sytuacjach, w których sama metoda Concorcet zawodzi. Metodę Schulze stosowało kilka organizacji, w tym Fundacja Wikimedia .
Aby obliczyć najszersze szerokości ścieżek dla wszystkich par węzłów w gęsto skierowanym grafie, takim jak te, które pojawiają się w aplikacji do głosowania, asymptotycznie najszybsze znane podejście wymaga czasu O ( n (3 + ω)/2 ), gdzie ω jest wykładnik do szybkiego mnożenia macierzy . Wykorzystując najbardziej znane algorytmy mnożenia macierzy, to ograniczenie czasowe przyjmuje postać O ( n 2,688 ) . Zamiast tego referencyjna implementacja metody Schulze wykorzystuje zmodyfikowaną wersję prostszej Algorytm Floyda-Warshalla , który zajmuje czas O ( n 3 ) . W przypadku grafów rzadkich bardziej wydajne może być wielokrotne stosowanie algorytmu najszerszej ścieżki z jednego źródła.
Pojedyncze źródło
Jeśli krawędzie są posortowane według ich wag, zmodyfikowana wersja algorytmu Dijkstry może obliczyć wąskie gardła między wyznaczonym wierzchołkiem początkowym a każdym innym wierzchołkiem na grafie w czasie liniowym. Kluczową ideą przyspieszenia w stosunku do konwencjonalnej wersji algorytmu Dijkstry jest to, że sekwencja odległości wąskich gardeł do każdego wierzchołka, w kolejności, w jakiej wierzchołki są uwzględniane przez ten algorytm, jest monotoniczną podsekwencją posortowanej sekwencji wag krawędzi ; dlatego kolejka priorytetowa algorytmu Dijkstry może być zaimplementowana jako kolejka kubełkowa : tablica indeksowana liczbami od 1 do m (liczba krawędzi grafu), gdzie komórka tablicy i zawiera wierzchołki, których odległość wąskiego gardła jest wagą krawędzi o pozycji i w porządku posortowania. Ta metoda pozwala rozwiązać problem najszerszej ścieżki tak szybko, jak sortowanie ; na przykład, jeśli wagi krawędzi są reprezentowane jako liczby całkowite, to ograniczenia czasowe dla sortowania liczby całkowitej listy m liczb całkowitych miałyby zastosowanie również do tego problemu.
Jedno źródło i jedno miejsce docelowe
Berman i Handler (1987) sugerują, że pojazdy serwisowe i pojazdy uprzywilejowane powinny korzystać ze ścieżek minimax podczas powrotu z wezwania serwisowego do swojej bazy. W tej aplikacji czas zwrotu jest mniej ważny niż czas reakcji w przypadku kolejnego wezwania serwisu, gdy pojazd jest w trakcie zwrotu. Wykorzystując ścieżkę minimax, gdzie waga krawędzi jest maksymalnym czasem podróży od punktu na krawędzi do najdalszego możliwego wezwania serwisu, można zaplanować trasę, która minimalizuje maksymalne możliwe opóźnienie między otrzymaniem wezwania serwisu a przybyciem reagujący pojazd. Ullah, Lee i Hassoun (2009) wykorzystywać ścieżki maximin do modelowania dominujących łańcuchów reakcji w sieciach metabolicznych ; w ich modelu ciężarem krawędzi jest energia swobodna reakcji metabolicznej reprezentowanej przez krawędź.
Inne zastosowanie najszerszych ścieżek pojawia się w algorytmie Forda-Fulkersona dla problemu maksymalnego przepływu . Wielokrotne zwiększanie przepływu wzdłuż ścieżki maksymalnej wydajności w resztkowej sieci przepływu prowadzi do małej granicy, O ( m log U ) , liczby zwiększeń potrzebnych do znalezienia maksymalnego przepływu; tutaj zakłada się, że pojemności krawędzi są liczbami całkowitymi, które są co najwyżej U . Jednak ta analiza nie polega na znalezieniu ścieżki, która ma dokładnie maksymalną przepustowość; wystarczy dowolna ścieżka, której pojemność mieści się w stałym współczynniku maksimum. Połączenie tej idei przybliżenia z najkrótszą metodą zwiększania ścieżki algorytmu Edmondsa-Karpa prowadzi do algorytmu maksymalnego przepływu z czasem działania O ( mn log U ) .
Możliwe jest bardzo efektywne znalezienie ścieżek o maksymalnej pojemności i ścieżek minimaksowych z jednym źródłem i jednym miejscem docelowym, nawet w modelach obliczeniowych, które pozwalają tylko na porównania wag krawędzi grafu wejściowego, a nie na nich arytmetyczne. Algorytm utrzymuje zestaw S krawędzi, o których wiadomo, że zawierają krawędź wąskiego gardła optymalnej ścieżki; początkowo S jest tylko zbiorem wszystkich m krawędzi grafu. W każdej iteracji algorytmu dzieli S na uporządkowaną sekwencję podzbiorów S 1 , S 2 , ... mniej więcej równej wielkości; liczba podzbiorów w tym podziale jest wybrana w taki sposób, że wszystkie punkty podziału między podzbiorami można znaleźć przez powtarzane znajdowanie mediany w czasie O ( m ) . Algorytm następnie ponownie waży każdą krawędź wykresu według indeksu podzbioru zawierającego krawędź i używa zmodyfikowanego algorytmu Dijkstry na ponownie ważonym wykresie; na podstawie wyników tego obliczenia może określić w czasie liniowym, który z podzbiorów zawiera wagę krawędzi wąskiego gardła. Następnie zastępuje S Si przez podzbiór że ustalił, że zawiera wagę wąskiego gardła, i rozpoczyna następną iterację z tym nowym zestawem S . Liczba podzbiorów, na które S, rośnie wykładniczo z każdym krokiem, więc liczba iteracji jest proporcjonalna do iterowanej funkcji logarytmicznej, O ( log * n ) , a całkowity czas wynosi O ( m log * n ) . W modelu obliczeniowym, w którym każda waga krawędzi jest liczbą całkowitą maszyny, użycie powtarzanego bisekcji w tym algorytmie można zastąpić techniką dzielenia listy Hana i Thorupa (2002) , pozwalającą podzielić S na O ( √ m ) mniejsze zbiory S i w jednym kroku i prowadzą do liniowego ogólnego ograniczenia czasowego.
Zestawy punktów euklidesowych
Wariant problemu ścieżki minimax został również rozważony dla zbiorów punktów na płaszczyźnie euklidesowej . Podobnie jak w przypadku problemu z grafem nieskierowanym, ten problem euklidesowej ścieżki minimaksowej można skutecznie rozwiązać, znajdując euklidesowe minimalne drzewo rozpinające : każda ścieżka w drzewie jest ścieżką minimaksową. Jednak problem staje się bardziej skomplikowany, gdy pożądana jest ścieżka, która nie tylko minimalizuje długość przeskoku, ale także, spośród ścieżek o tej samej długości przeskoku, minimalizuje lub w przybliżeniu minimalizuje całkowitą długość ścieżki. Rozwiązanie można przybliżyć za pomocą kluczy geometrycznych .
W teorii liczb nierozwiązany problem fosy Gaussa pyta, czy ścieżki minimaksu w liczbach pierwszych Gaussa mają ograniczoną lub nieograniczoną długość minimaksu. To znaczy, czy istnieje stała B taka, że dla każdej pary punktów p i q w nieskończonym zbiorze punktów euklidesowych określonym przez liczby pierwsze Gaussa, ścieżka minimaksu w liczbach pierwszych Gaussa między p i q ma minimalną długość krawędzi co najwyżej B ?