Jakie k-najlepsze algorytmy najkrótszej ścieżki należy wziąć pod uwagę?

Rozwiązuję problem optymalizacji wyszukiwania wykresów. Muszę znaleźć k najlepszych acyklicznych najkrótszych ścieżek poprzez ukierunkowany wykres ważony.

Wiem, że istnieje wiele dokładnych i przybliżonych algorytmów k-best, ale większość ostatnich badań wydaje się być ukierunkowana na bardzo duże, bardzo rzadko powiązane wykresy (np. Trasy i kierunki), a mój wykres nie jest żaden.

Wyróżniające aspekty mojego problemu:

Wykres składa się z około 160 wierzchołków.
Wykres jest prawie w pełni połączony (dwukierunkowo, więc ~ 160 ^ 2 ~ = 25 tys. Krawędzi)
k będzie dość małe (prawdopodobnie mniej niż 10)
Maksymalna długość ścieżki prawdopodobnie będzie ograniczona, a także bardzo mała (np. 3-5 krawędzi)
Powiedziałem „acykliczny” powyżej, ale żeby to powtórzyć - rozwiązania nie mogą obejmować cykli. Nie stanowi to problemu dla 1-najlepszej najkrótszej ścieżki, ale staje się problemem dla k-best - na przykład rozważ trasę - druga najkrótsza ścieżka od A do B może być taka sama jak 1-najlepsza, z szybka podróż dookoła bloku. To może być optymalne matematycznie, ale niezbyt przydatne rozwiązanie. ;-)
Dla każdego obliczenia może być konieczne ponowne ważenie krawędzi w locie. Koszt krańcowy składa się z ważonej sumy kilku czynników, a ostateczne wymagania (za każdym razem, gdy je otrzymamy) mogą pozwolić użytkownikowi na określenie własnego priorytetu dla tych czynników ważących, zmieniając wagi krawędzi. Jest to względnie mały wykres (powinniśmy być w stanie przedstawić go w kilkuset KB), więc prawdopodobnie rozsądnie jest sklonować wykres w pamięci, zastosować ponowne ważenie, a następnie wykonać wyszukiwanie na sklonowanym wykresie. Ale jeśli istnieje bardziej skuteczna metoda przeprowadzania wyszukiwania podczas obliczania ciężarów w locie, jestem zainteresowany.

Patrzę na algorytmy opisane w Santos (algorytmy K najkrótszej ścieżki), Eppstein 1997 (Finding the k Shortest Paths) i innych. Algorytm jena jest interesujący, głównie ze względu na istniejącą implementację Java . Nie boję się czytać artykułów naukowych, ale pomyślałem, że warto wyrzucić szczegóły mojego problemu i poprosić o wskazówki, aby zaoszczędzić trochę czasu na czytanie.

A jeśli masz wskaźniki do implementacji Java, nawet lepiej.

java algorithms

— AaronD
źródło

+1, ponieważ interesują mnie sugestie, które mają ludzie, i wydaje się, że dokładnie taki rodzaj pytania dotyczy tej witryny.

— KChaloux

Czy twój stan acykliczny nie oznacza, że ŻADNA inna ścieżka od początku do celu stworzyłaby cykl z pierwszą ścieżką? A jeśli zarówno początek, jak i bramka znajdują się w ślepym zaułku, każda ścieżka musi korzystać z tych dwóch krawędzi.

— user470365

Może nie byłem jasny. Acykliczne ograniczenie dotyczy tylko jednej ścieżki - oczywiście 2 dowolne dwie ścieżki od A do B utworzą cykl.

— AaronD,

@AaronD: więc którego użyłeś w końcu?

— Dagnelies 15.01.2013

@arnaud: Nie jestem pewien, czy zdecydowałem się na algorytm; Kiedy to zrobię, dodam aktualizację do tego pytania. Wyeliminowałem Eppsteina, ponieważ nie gwarantuje acyklicznych (aka „prostych”) rozwiązań. Obecnie pracuję z algorytmem Yen, ale jeszcze nie doszedłem do szczegółowego profilowania lub optymalizacji, więc być może będę musiał zastąpić go innym. Zaktualizuję za tydzień lub dwa.

— AaronD,

Odpowiedzi:

Aby częściowo odpowiedzieć na moje pytanie:

Od opublikowania tego pytania odkryłem, że musimy radzić sobie z ujemnymi wagami krawędzi i dodatnimi (ograniczenie do ścieżek acyklicznych / prostych / bez pętli oznacza, że zdefiniowane jest najlepsze rozwiązanie, natomiast bez tego ograniczenia najkrótsza ścieżka przez wykres z ujemnym- cykle kosztów są niezdefiniowane).

Algorytm Yena i większość innych, które badałem, zależą od serii 1 najlepszych wyszukiwań; większość używa Dijkstra do pośrednich wyszukiwań. Dijkstra nie obsługuje ujemnych obciążeń krawędzi, ale zamiast niego możemy zastąpić Bellmana-Forda (przynajmniej w jenie; prawdopodobnie także w Lawlerze i Eppsteinie). Opracowałem modyfikację Bellmana-Forda z ograniczeniem długości ścieżki (w krawędziach) i jawnym sprawdzaniem cyklu podczas wyszukiwania (zamiast standardowego wykrywania cyklu po wyszukiwaniu). Złożoność obliczeniowa jest gorsza, ale wciąż możliwa do przełożenia na moje wymagania. Zmienię tę odpowiedź i link do raportu technicznego, jeśli otrzymam pozwolenie na jej opublikowanie.

— AaronD
źródło

Powiedziałbym, że to pytanie można łatwo znaleźć w Google, a także jest duplikatem:

To powiedziawszy, już użyłem i wdrożyłem Eppstein i polecam to. Uważam to za dość eleganckie. Jeśli dobrze pamiętam, może to być również optymalne, a następujący artykuł wyjaśnia to bardzo ładnie:

http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf

— Dagnele
źródło

Po pierwsze, dziękuję za zalecenie Eppsteina. Będę tam więcej szukać. Twierdziłbym, że to nie jest dokładny duplikat, ani nie jest łatwo google; łatwo jest znaleźć algorytm K-best, ale nie jest tak łatwo dokonać rozsądnego wyboru między nimi. Spodziewam się, że chciałbym mieć zupełnie inny algorytm dla rzadko połączonego wykresu milionów wierzchołków niż dla tego problemu. Byłbym bardziej zainteresowany złożonością w k, gdybym chciał 1000 najlepszych zamiast 10 najlepszych. I chociaż stałe czynniki nie są tak ważne przy publikowaniu artykułów, z pewnością mają one miejsce podczas wysyłania kodu produkcyjnego.

— AaronD,

@AaronD: tylko dla twojej informacji, myślę, że algorytm jest bardzo wydajny niezależnie od przypadku. Być może istnieją szczególne przypadki, w których wyszukiwania oparte na heurystyce pokonują to, ale w ogólnym przypadku myślę, że robi to bardzo dobrze. Dokładna wydajność prawdopodobnie będzie zależeć bardziej od tego, jak dokładnie ją zaimplementujesz, wydajności twoich struktur danych i tego, jak jest dostosowany do twojego problemu.

— Dagnelies,

@arnaud Cześć, czy możesz udostępnić implementację swojego eppsteina? Mam podobne pytanie zamieszczone tutaj: math.stackexchange.com/questions/1661737/…

— Tina J