Wyznaczanie najkrótszej drogi między wieloma punktami na mapie

Witam.

Szukam aplikacji, ewentualnie najefektywniejszego rozwiązania, które pozwoliłoby na wyznaczenie jak najkrótszej drogi między ponad pięćdziesięcioma punktami na mapie (co oznacza, że droga musi biec przez ulice).

A nawigacja z sortowaniem via nie będzie dobrym rozwiązaniem?

 

Nie ma na to algorytmu o zwykłej złożoności obliczeniowej.Aplikacja liczy grafowo koszty - długości drogi  i wybiera najkrótsze.

Podoba mi się ta liczba 60! (silnia) ale mam kłopoty z jej przeczytaniem :frowning: 60!=8320987112741390144276341183223364380754172606361245952449277696409600000000000000

50! jest znacznie mniejszą liczbą. :slight_smile:

50!=30414093201713378043612608166064768844377641568960512000000000000

 

No niestety wprowadzasz w błąd. Byłoby tak gdyby każde skrzyżowanie miało 60 rozjazdów, kazdy punkt był połączony z każdym na mapie, ale w tym wypadku tak nie jest. Mapa ma niemal 60 punktów zakładając realistycznie że każdy ma ~4 drogi rozjazdu na skrzyżowaniu przy 20 punktach co łatwo sobie wyobrazić  przy pomocy połączonych 5 grupach po 5 punktów w fomie “fraktalu”. Najkrótsza droga od jednego punktu do dowolnego innego wynosi ~góra 4^8 czyli ok 65536 kombinacji. Znacznie znacznie mniej niż tym straszysz. Dla 50 punktów wiele zależy od topologii połączeń, ilość kombinacji rośnie wykładniczo w najlepszym wypadku na oko od 256tyś do 4mld.

I owszem są algorytmy które ten problem upraszczają. np. https://pl.wikipedia.org/wiki/Algorytm_Dijkstry

Kto powiedział że między punktami jest tylko jedna droga ? Poza tym bez znanej kolejności każdy może prowadzić do każdego.