« poprzedni następny »
Strony: [1]   Do dołu

Inteligentne planowanie trasy w AM

  • 14 Odpowiedzi
  • 5058 Wyświetleń

0 użytkowników i 1 Gość przegląda ten wątek.

*

Offline luksik

  • 32
  • Płeć: Mężczyzna
  • Sprzęt: HTC Wizard
Inteligentne planowanie trasy w AM
« dnia: 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.
Zapisane
*

Offline bazi22

  • ****
  • 913
  • Płeć: Mężczyzna
  • Sprzęt: Navroad NR411 | iPhone 3GS 16GB
Re: Inteligentne planowanie trasy w AM
« Odpowiedź #1 dnia: Luty 23, 2007, 18:36:06 »
Cytat: "luksik"
Czy AM potrafi zanalizowac liste tych punktow i wyliczyc najszybsza trase zawierajaca te punkty, bez mojej ingerencji w ich kolejnosc ?


Nie potrafi
Zapisane
Bartek Chyba :: bazi22
Dell X30=>HTC Wizard=>HTC Hermes=>iPhone 3GS
*

Offline klosz007

  • **
  • 194
  • Płeć: Mężczyzna
  • Sprzęt: iPhone 4 16GB + iPad 3 3G 32GB + NavRoad Vivo Plus
Re: Inteligentne planowanie trasy w AM
« Odpowiedź #2 dnia: Luty 24, 2007, 21:12:11 »
Cytat: "luksik"

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
Zapisane
*

Offline bazi22

  • ****
  • 913
  • Płeć: Mężczyzna
  • Sprzęt: Navroad NR411 | iPhone 3GS 16GB
Inteligentne planowanie trasy w AM
« Odpowiedź #3 dnia: Luty 24, 2007, 22:12:27 »
A Garmin Que znalezienie drogi najoptymalniejszej przez 10 pkt zajmuje ok. 1-3 minut
Zapisane
Bartek Chyba :: bazi22
Dell X30=>HTC Wizard=>HTC Hermes=>iPhone 3GS
*

Offline luksik

  • 32
  • Płeć: Mężczyzna
  • Sprzęt: HTC Wizard
Inteligentne planowanie trasy w AM
« Odpowiedź #4 dnia: Luty 24, 2007, 22:50:36 »
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 :>
Zapisane
*

Offline klosz007

  • **
  • 194
  • Płeć: Mężczyzna
  • Sprzęt: iPhone 4 16GB + iPad 3 3G 32GB + NavRoad Vivo Plus
Inteligentne planowanie trasy w AM
« Odpowiedź #5 dnia: Luty 24, 2007, 23:56:05 »
Cytat: "bazi22"
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
Zapisane
*

Offline kwieto

  • ******
  • 2785
Inteligentne planowanie trasy w AM
« Odpowiedź #6 dnia: Luty 25, 2007, 08:30:05 »
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...
Zapisane
Ludzie zazdroszczą ci nie tego, że coś zrobiłeś, ale tego że ci się chciało to zrobić.
*

Offline PeDeA

  • **
  • 239
  • Płeć: Mężczyzna
  • Sprzęt: LOOX 720 + GNS 5843
Inteligentne planowanie trasy w AM
« Odpowiedź #7 dnia: Luty 25, 2007, 09:21:32 »
Cytat: "kwieto"
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.
Zapisane
Pozdrawiam PeDeA
*

Offline luksik

  • 32
  • Płeć: Mężczyzna
  • Sprzęt: HTC Wizard
Inteligentne planowanie trasy w AM
« Odpowiedź #8 dnia: Luty 25, 2007, 10:01:17 »
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.
Zapisane
*

Offline Gufer-posepny

  • **
  • 195
  • Płeć: Mężczyzna
Inteligentne planowanie trasy w AM
« Odpowiedź #9 dnia: Luty 25, 2007, 10:05:09 »
iGo ma mało ulic , stąd też świetne rezultaty w liczeniu tras .
Zapisane
Navroad 350
*

Offline luksik

  • 32
  • Płeć: Mężczyzna
  • Sprzęt: HTC Wizard
Inteligentne planowanie trasy w AM
« Odpowiedź #10 dnia: Luty 25, 2007, 10:23:04 »
Ehh. A juz myslalem, ze jakis program mi ulatwi zycie :/ No coz, zostalo mi zakupic AM i uzywac przemeczonego juz mozgu :)

Dzieki za info :)
Zapisane
*

Offline kwieto

  • ******
  • 2785
Inteligentne planowanie trasy w AM
« Odpowiedź #11 dnia: Luty 25, 2007, 14:08:06 »
Cytat: "luksik"
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.
Zapisane
Ludzie zazdroszczą ci nie tego, że coś zrobiłeś, ale tego że ci się chciało to zrobić.
*

Offline krzychu1800

  • 4
Inteligentne planowanie trasy w AM
« Odpowiedź #12 dnia: Luty 25, 2007, 20:18:11 »
AutoPilot ma funkcję optymalizacji trasy. Działa całkiem dobrze i szybko.
Zapisane
*

tramp

Inteligentne planowanie trasy w AM
« Odpowiedź #13 dnia: Luty 25, 2007, 20:46:16 »
Cytat: "Gufer-posepny"
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  :)
Zapisane
*

Offline GPS maniak

  • *****
  • 1383
    • http://gpsmaniak.com
Inteligentne planowanie trasy w AM
« Odpowiedź #14 dnia: Luty 25, 2007, 21:43:02 »
Cytat: "luksik"
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.
Cytat: "luksik"
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).
Cytat: "tramp"
Cytat: "Gufer-posepny"
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"  ]:>
Cytat: "kwieto"
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  :(
Zapisane
Strony: [1]   Do góry
« poprzedni następny »