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.
źródło
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.
ź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
źródło