Optymalizacja algorytmu - najkrótsza trasa między wieloma punktami

Question

Problem: Mam dużą kolekcję punktów. Każdy z tych punktów ma listę z odniesieniami do innych punktów z odległością między nimi już wyliczoną i zapisaną. Muszę określić najkrótszą trasę, która zaczyna się od miejsca pochodzenia i przechodzi przez określoną liczbę punktów do dowolnego miejsca docelowego.

Np. Jestem na wakacjach i przebywam w określonym mieście. Robię JEDNĄ DROŻNĄ podróż, by zobaczyć DOWOLNE cztery miasta i chcę podróżować jak najmniejszą odległością. Nie mogę odwiedzić tego samego miasta więcej niż jeden raz.

Obecne rozwiązanie: Teraz po prostu ręcznie sprawdzam każdą możliwość i zapisuję najkrótszą ścieżkę. Działa to, ale wydaje się nieskuteczne. Ponadto problem ten zostanie w końcu rozszerzony w celu włączenia wyszukiwania z wielu punktów początkowych do wielu punktów docelowych, więc myślę, że może to spowodować eksplozję przestrzeni wyszukiwania.

Jaki jest lepszy sposób wyszukiwania najkrótszej trasy?

Answer 1

Odpowiadając na zaktualizowany post, twoje rozwiązanie sprawdzenia każdej możliwości jest optymalne (przynajmniej nikt dotąd nie odkrył lepszych algorytmów). Tak, to jest wędrujący sprzedawca, którego esencja nie dotyka każdego miasta, ale dotyka każdego miasta raz. Jeśli nie chcesz szukać najlepszego możliwego rozwiązania, możesz użyć heurystyk, które działają szybciej, ale pozwalają na ograniczoną rozbieżność w stosunku do idealnego rozwiązania.

---

Dla przyszłych Główni odpowiadający: Floyd-Warshall algorithm i wszystko Floyd-podobne zmiany są tu zastosowania.

Answer 2

To brzmi Podróżujący sprzedawca? Jednym z rozwiązań jest zastosowanie techniki optymalizacji, takiej jak algorytm ewolucyjny. Obecnie przeprowadzasz wyczerpujące wyszukiwanie, które bardzo szybko stanie się bardzo powolne. Sądzę jednak, że jest to raczej problem komiwojażera, który został potraktowany przez kilka dekad, jeśli nie stulecia, i istnieje kilka możliwych sposobów ataku. Google to twój przyjaciel.

Answer 3

Na ogół należy do ścisłych złe warianty ... myślę, że należy korzystać z niektórych odmian metody Branch_and_bound http://en.wikipedia.org/wiki/Branch_and_bound

Answer 4

Albo bredth pierwszy wyszukiwanie jako norheim.se powiedział lub Dijkstra's algorithm byłaby moja sugestia, jak również.

Answer 5

Wygląda na to, że krawędzie wykresu są dwukierunkowe. W tym przypadku algorytm, którego szukasz, to Dijkstra's algorithm.

Answer 6

Być może tak właśnie jest w oryginalnym plakacie poprzez "iterowanie każdej z możliwości ręcznie i przechowywanie najkrótszej ścieżki", ale pomyślałem, że chciałbym wyjaśnić, co wydaje się być rozwiązaniem bazowym.

Załóżmy, że masz już algorytm dwuetapowej najkrótszej ścieżki - ma klasyczne rozwiązania dla różnych rodzajów wykresów. Załóżmy, że wszystkie odległości są nieujemne, a d (A-> B-> C) = d (A-> B) + d (B-> C).

Najistotniejsze jest to, że droga rozpoczyna się w S przechodzi przez jeden z pośrednich miastach „ABCD”, a kończy się z E:

np SabcdE, SacbdE, itd ...

Tylko z 4 miast pośrednich, wyliczasz wszystkie 24 permutacje. Dla każdej permutacji użyj swojego najkrótszego algorytmu dwupunktowego do obliczenia ścieżki od głowy do ogona i całkowitej odległości.

Przyznany punkt początkowy i końcowy oferuje 12 możliwości podłączenia do abcd i do każdej z dwóch możliwości wnętrza. Już policzyłeś te odległości, więc dodaj odległość od S do głowy, a ogon do E. Wybierz minimum. Więc po wstępnym obliczeniu odległości pośrednich dla ustalonego zestawu miast wewnętrznych, musisz wykonać 12 punktów o najmniejszej ścieżce dla każdej pary punktów początkowych i końcowych.

To oczywiście słabo skaluje się wraz ze wzrostem liczby miast pośrednich. Nie jest dla mnie jasne, że może to zrobić lepiej, chyba że narzucisz większe ograniczenia na strukturę wykresu (czy to w fizycznej przestrzeni Euclidenan? Trójkąt nierówności?).

Mój przykład: przypuśćmy, że wszystkie odległości pośrednie między miastami to O (1). Bez ograniczeń na wykresie, odległość od S do dowolnego miasta pośredniego może wynosić 1000, z wyjątkiem jednego będącego 1. Takie samo dla ogona. Więc możesz zmusić pierwsze miasto do odwiedzin, żeby było cokolwiek. Teraz idź jedną warstwą w dół, weź pierwsze miasto jako "punkt początkowy". Zastosuj ten sam argument: możesz wykonać najlepszą ścieżkę do dowolnego z poniższych miast, manipulując odległościami na wykresie.

Wygląda więc na to, że złożoności nie da się uniknąć bez dodatkowych założeń.

Answer 7

Jest to bardzo często występująca sytuacja, w której każdy może wpaść. Interfejs użytkownika mapy Google udostępnia ścieżkę w tej samej kolejności, do której dodaje się listę odbiorców. nie zapewnia optymalnej ścieżki, mimo że ich własny interfejs API Google zapewnia rozwiązanie.

Google Maps API zapewnia rozwiązanie tego problemu. W żądaniu znalezienia ścieżki musisz podać flagę "optimizeWaypoints: true". Żądanie będzie wyglądało tak.

var request = { 
      origin: start, 
      destination: end, 
      waypoints: waypts, 
      optimizeWaypoints: true, 
      travelMode: google.maps.TravelMode.DRIVING 
     }; 

i można zobaczyć cały kod narzędzia w źródle widoku, ponieważ kompletne narzędzie zostało opracowane w javascript i HTML.

Mam nadzieję, że to pomoże.