PDAclub.pl - Forum użytkowników technologii mobilnych
Nawigacja GPS => AutoMapa => Wątek zaczęty przez: luksik w Luty 23, 2007, 16:30:18
-
Witam serdecznie.
Od jakiegos czasu nosze sie z zamiarem zakupu AM. Jednak zastanawiam sie czy posiada ona cos takiego jak inteligentne planowanie trasy. Kiedys czytalem o tym na jakims zagranicznym forum i program do nawigacji (ktorego nazwy za zadne skarby nie moge sobie przypomniec) posiadal cos takiego. Konkretnie chodzi mi o taki przypadek:
Mam do odwiedzenia przypuscmy 10 punktow w miescie, ktorych polozenie mam i moge wprowadzic do AM. Za pewnik moge przyjac punkt poczatkowy i docelowy. Reszta punktow jest znana, ale ich kolejnosc jest dowolna. I tutaj pojawia sie moje pytanie. Czy AM potrafi zanalizowac liste tych punktow i wyliczyc najszybsza trase zawierajaca te punkty, bez mojej ingerencji w ich kolejnosc ?
Bardzo chetnie dowiedzialbym sie od Was czy jest taka mozliwosc w AM.
Pozdrawiam i czekam na ewentualna info.
-
Czy AM potrafi zanalizowac liste tych punktow i wyliczyc najszybsza trase zawierajaca te punkty, bez mojej ingerencji w ich kolejnosc ?
Nie potrafi
-
Mam do odwiedzenia przypuscmy 10 punktow w miescie, ktorych polozenie mam i moge wprowadzic do AM. Za pewnik moge przyjac punkt poczatkowy i docelowy. Reszta punktow jest znana, ale ich kolejnosc jest dowolna. I tutaj pojawia sie moje pytanie. Czy AM potrafi zanalizowac liste tych punktow i wyliczyc najszybsza trase zawierajaca te punkty, bez mojej ingerencji w ich kolejnosc ?
Z matematycznego punktu widzenia jest to w teorii grafów tzw. problem komiwojażera (Travelling Salesman Problem - jak zaliczyć n punktów na mapie jak najkrótszą drogą) i zdaje się, że odkąd problem został zdefiniowany (chyba kilkadizesiąt lat temu) nie ma ogólnego rozwiązania tego problemu więc ciężko, żeby AM je miała ;)
Zdaje się, że jedyna metoda to bruteforce ale jest to zagadnienie bardzo złożone obliczeniowo i przy więcej niż kilku punktach wyznaczanie najkrótszej drogi mogłoby trwać zdecydowanie za długo ;) Załóżmy że znalezienie 1 trasy przez 10 punktów trwa 5 sekund. Chcemy znaleźć najkrótszą trasę przez te 10 punktów. 10 punktów można ułożyć w unikalnej kolejności na strzelam 100000 możliwości (permutacje bez powtórzeń - ktoś pamięta jaki jest wzór ? n! ? Jeśli tak do dla n=10 wychodzi już dość kosmiczna liczba). Czas na znalezienie najkrótszej trasy 10*100000 sekund, brrrr....
Dla małej ilości punktów (kilka) da radę ale AM tego i tak nie umie...
Pozdr,
Zbyszek
-
A Garmin Que znalezienie drogi najoptymalniejszej przez 10 pkt zajmuje ok. 1-3 minut
-
Dzieki wielkie za wyczerpujace odpowiedzi. Faktycznie nie przemyslalem pytania i zapomnialem o problemie komiwojazera :/ Zasugerowalem sie autoroutingiem w Protela i jakos mi tak umysl przycmilo :)
Mimo wszystko dzieki. Jednak bede musial czasem do planowania trasy uzyc mozgu :>
-
A Garmin Que znalezienie drogi najoptymalniejszej przez 10 pkt zajmuje ok. 1-3 minut
Wszystko jeszcze zależy od tego jak dużo czasu potrzeba na wyznaczenie trasy przy zadanej kolejności punktów. Jeśli trasa pomiędzy dowolnymi dwoma punktami jest jednoznaczna i prosta to wyznaczenie całej trasy jest błyskawiczne (nawet te 100000 możliwości razy np. 1ms nie jest straszną wielkością). Jeśli trasa pomiędzy dwoma punktami jest złożona z większej ilości odcinków i jej znalezienie zajmuje więcej czasu (jak 5 sek z mojego przykładu) to czas proporcjonalnie wzrośnie...
Zmierzam do tego, że znalezienie najkrótszej trasy w obrębie 10 punktów na jednym kwartale ulic to nie to samo co znalezienie najkrótszej trasy pomiędzy 10 punktami w obrębie Polski. W jakich warunkach zajmuje wyznaczenie najkrótszej trasy 1-3 minut ?
Poza tym jeśli dla 10 punktów zajmuje kilka minut to dla 11 będzie to już o rząd wielkości więcej...
Mogę się w tym wszystkim mylić i nie chcę się wymądrzać ale skoro matematycy nie rozwiązali problemu TSP to nie jest on trywialny. W prostych przypadkach da radę (tak jak łamanie hasła z 3 znaków), w bardziej złożonych - ni hu hu.
Niby na dzień dobry algorytm można uprościć (np. połowa tras to będą te same trasy w przeciwnym kierunku - choć to zależy czy mówimy o przypadku symetrycznego czy asymetrycznego TSP) to i tak niewielka pociecha.
Poza tym dodając jakieś elementy poszukiwania heurystycznego lub inne uproszczenia można pewnie skrócić ten czas wielokrotnie to kosztem tego, że nie mamy pewności, że trasa jest najkrótsza.
Pozdr,
Zbyszek
-
Generalnie "opcję komiwojażera" ma wspomniany Garmin Que oraz iGO.
Jak działa ta opcja - nie pytaj, nie używałem żadnego z tych programów.
Być może algorytmy wyznaczania tras upraszczają problem, jednak opinie użytkowników tej opcji są pozytywne - znaczy że w codziennym użyciu się sprawdza...
-
Generalnie "opcję komiwojażera" ma wspomniany Garmin Que oraz iGO.
Jak działa ta opcja - nie pytaj, nie używałem żadnego z tych programów.
Być może algorytmy wyznaczania tras upraszczają problem, jednak opinie użytkowników tej opcji są pozytywne - znaczy że w codziennym użyciu się sprawdza...
Potwierdzam. iGO daje zupelnie dobre wyniki. Korzystam sam. Obliczenie optymalnej trasy zajmuje kilkanascie sekund.
-
A jak z dokladnoscia map polskich miast w iGO ?
Sa one chociaz zblizone do tych z AM ? Z tego co slyszalem to AM ma bardzo dopracowane mapy, wlacznie z numerami domow.
-
iGo ma mało ulic , stąd też świetne rezultaty w liczeniu tras .
-
Ehh. A juz myslalem, ze jakis program mi ulatwi zycie :/ No coz, zostalo mi zakupic AM i uzywac przemeczonego juz mozgu :)
Dzieki za info :)
-
Ehh. A juz myslalem, ze jakis program mi ulatwi zycie :/ No coz, zostalo mi zakupic AM i uzywac przemeczonego juz mozgu :)
Dzieki za info :)
Niekoniecznie - Que ma mapy lepsze od tych które są w Automapie, no i ma opcje komiwojażera. Poczytaj o nim na odpowiednim podforum, albo popytaj GPS maniaka, który używa zarówno Que jak również iGO.
Map Automapy bym nie przeceniał - np. takie miasto jak Toruń dostało numerację ulic dopiero w drugiej połowie zeszłego roku, podczas gdy np. TomTom miał tam numerację już na początku 2006 (wcześniejszych map nie sprawdzałem). Nadal zresztą są miejsca gdzie inni producenci mają numerację a AM jest jeszcze "w lesie" (vide Ciechanów). Z drugiej strony, AM dysponuje planami miast (ale bez numeracji) mniejszych miast, dla których TomTom czy iGO mają tylko drogi przelotowe i ew. główniejsze ulice. Nadal jednak pod tym względem (zresztą numeracji też) jest "bita" przez Que i GPMapę lub mapy typu Citynavigator (o ile dobrze pamiętam nazwę tego ostatniego produktu)
IMO póki nie wyjdzie AM 4.0 i nie okaże się że jest ona wyraźnie lepsza od poprzedniczki, nie ma sensu "rzucać się" na ten program. W obecnej formie jest to zdecydowanie najmniej ergonomiczny i najbardziej zawodny z programów z którymi miałem styczność. Sam zamieniłem AM na TomToma (niestety dla Ciebie nie ma w nim opcji "komiwojażera") i nie żałuję tej decyzji.
-
AutoPilot ma funkcję optymalizacji trasy. Działa całkiem dobrze i szybko.
-
iGo ma mało ulic , stąd też świetne rezultaty w liczeniu tras .
jak ja lubię czytać takie posępne pierdoły :))
to se posępnie przećwicz trasę w Berlinie jak Ci ulic u nas mało :)
-
Z tego co slyszalem to AM ma bardzo dopracowane mapy, wlacznie z numerami domow.
Każda mapa ma. Odrębnym zagadnieniem jest ilość miejscowości z takimi informacjami.
A jak z dokladnoscia map polskich miast w iGO ?
W moim odczuciu, iGO to najlepszy soft :proud: zawierajacy (jak na razie) najgorszą mapę (mówimy o Polsce).
iGo ma mało ulic , stąd też świetne rezultaty w liczeniu tras .
jak ja lubię czytać takie posępne pierdoły :))
No właśnie. Trasę z Poznania pod konkretny adres do jakiejś dziury pod Malagą (3160 km !!) liczy jak błyskawica. Zatem teorię o szybkości związanej z małą ilością ulic można najzwyczajniej w świecie wyrzucić na śmietnik "mitów" ]:>
Niekoniecznie - Que ma mapy lepsze od tych które są w Automapie
Czy lepsze to nie wiem, bo nie śledzę już rozwoju AutoMapy. Mam najlepszy (moim zdaniem oczywiście) soft nawigacyjny na pocketa: iGO - 2006, mam też Garminka z City Navigatorem EU 9.o + GPMapą 5.o i dlatego AM całkowicie mi "powiewa".
Jakiś rok temu GPMapa i AutoMapa to były produkty porównywalne. Jak jest dzisiaj nie wiem. Aktualnej AutoMapy nie znam w ogóle, a GPMapa w wersji 5.o jest oczywiście lepsza od GPMapy 4.o, ale czy jest to jakiś miażdżący skok ? Bo ja wiem ? Ilość miejscowości z pełną bazą adresową skoczyła z 1000 do 1250, ale np. nadal nie ma adresów w Luboniu (pod Poznaniem) czy Sanoku :(