Powiedzmy, że jedziemy od 1 do 5. Najkrótsza trasa to 1-4-3-5 (łącznie: 60 km).
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?
Odpowiedzi:
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.
źródło
Tak: Dijkstra
Dijkstra działa równie dobrze w tej sytuacji.
Po prostu wykorzystujesz czas, a nie odległość jako wagę każdego łuku.
źródło
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.
źródło
Powinieneś być w stanie zastąpić dystans czasem między węzłami i rozwiązać go w ten sam sposób.
źródło
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:
źródło