Algorytm określający najszybszą trasę?

17

Powiedzmy, że jedziemy od 1 do 5. Najkrótsza trasa to 1-4-3-5 (łącznie: 60 km).

Wykres

W tym celu możemy użyć algorytmu Dijkstry .

Problem w tym, że najkrótsza trasa nie zawsze jest najszybsza z powodu korków lub innych czynników.

Na przykład:

  • Wiadomo, że 1-2 mają częste korki, dlatego należy tego unikać.
  • Nagle zdarza się wypadek samochodowy wzdłuż 4-3, więc należy go również unikać.
  • Itp...

Prawdopodobnie więc możemy przyspieszyć na trasie 1-4-5, z powodu braku korków / wypadków, więc dotrzemy do 5 szybciej.

To jest ogólny pomysł i nie zastanawiałem się jeszcze nad szczegółami.

Czy jest jakiś algorytm do rozwiązania tego problemu?

anta40
źródło
3
Czy to zadanie domowe? Czy to nie jest po prostu en.wikipedia.org/wiki/Travelling_salesman_problem do przemierzania ważonego wykresu?
StuperUser,
9
@StuperUser: Nie, TSP to obwód wszystkich węzłów bez duplikatów. W przykładowym przypadku nie trzeba na przykład naciskać węzła 2.
David Thornley,
2
@DavidThornley Rozumiem. Więc Dijkstra jest najkrótszą trasą na wykresie ważonym? A czy TSP odwiedza każdy węzeł?
StuperUser,
1
@Stuper: Najkrótsza podróż, tak
BlueRaja - Danny Pflughoeft,
2
@StuperUser, tylko FYI, TSP jest silnym problemem NP-Complete bez rozwiązania, które można uruchomić w czasie wielomianowym. ... Więc teraz wiesz.
riwalk

Odpowiedzi:

5

Ponieważ na zdjęciu pojawiło się przekrwienie, uważaj, aby nie dać się złapać paradoksowi Braess . Jeśli każdy wybierze optymalną ścieżkę, spowoduje to gorszy czas podróży dla wszystkich.

Michael Brown
źródło
49

Tak: Dijkstra

Dijkstra działa równie dobrze w tej sytuacji.
Po prostu wykorzystujesz czas, a nie odległość jako wagę każdego łuku.

Martin York
źródło
9
Zazwyczaj „odległość” w Dijkstra będzie ważona dla różnych rzeczy, kosztów / opłat za przejazd, preferencji autostrad, ograniczeń prędkości - użycie samej odległości jest tylko najprostszym podejściem. To sprawia, że ​​algorytm jest tak sprytny
Martin Beckett,
6
Chociaż zrobi to Dijsktra, ogólnie wybrałbym A * do każdej poważnej pracy nad znalezieniem ścieżki; heurystyka bardzo pomoże.
Mircea Chirea,
6
Link: algorytm wyszukiwania * . Jest to rozszerzenie metody Dijkstry.
mgkrebbs,
Tak długo, jak istnieje odpowiednia heurystyka, A * będzie lepszy od Dijkstry (pod względem wydajności).
bummzack,
Dopuszczalna heurystyka byłaby nieco trudna do znalezienia tutaj, biorąc pod uwagę, że wydaje się, że bierzemy pod uwagę wiele czynników (takich jak korki).
pwny 11.01.12
16

Tak. Algorytm Dijkstry rozwiąże ten problem.

Problem w twoim przypadku polega na tym, że automatycznie zakładasz, że najkrótsza ścieżka odpowiada odległości przebytej, podczas gdy w rzeczywistości bardziej odpowiednio odpowiada KOSZTowi pokonania trasy.

Jeśli jedna ścieżka ma blokadę drogi, jej KOSZT powinien być wyższy, a algorytm nadal obowiązuje.

wałek klonowy
źródło
Tak, przepraszam, jeśli nie użyłem właściwego sformułowania. Mam na
myśli
11

Powinieneś być w stanie zastąpić dystans czasem między węzłami i rozwiązać go w ten sam sposób.

DKnight
źródło
10

Dijkstra

Jak wspomniano wcześniej, nie jest on używany tylko na najkrótszą odległość. Wierzę, że ta animacja dobrze rozumie „moc” (z braku lepszego słowa) Dijkstry:

Dijkstra

Dynamiczny
źródło