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).
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 60!=8320987112741390144276341183223364380754172606361245952449277696409600000000000000
50! jest znacznie mniejszą liczbą.
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.