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


(Tinnuir) #1

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).


(dark__jedi) #2

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

 


(Johny) #3

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.


(floyd) #4

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

 


(stasinek) #5

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


(Drobok) #6

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