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?

graph dijkstra

— 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

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

Algorytm określający najszybszą trasę?

Dijkstra