Agent Rafal M nadaje:

Moze sie ktos orientuje: czy AutoMapa ma funkcje "kuriera"?
Dzialajaca na zasadzie, ze wpisuje jej np 20 punktow przeznaczenia, i
nawigacja uklada mi dojazd do tych punktow po kolei, tak zeby wszystko
bylo "po drodze" (najkrotsza/najszybsza trasa)?

Automapa ma optymalizacje trasy. Ale programu (ani komputera) który bedzie w stanie policzyc optymalne trasy dla 19!/2 przypadków jeszcze nie wynaleziono - http://www.mini.pw.edu.pl/MiNIwyklady/grafy/prob-komiw.html

Automapa ma optymalizacje trasy. Ale programu (ani komputera) który bedzie w stanie policzyc optymalne trasy dla 19!/2 przypadków jeszcze nie wynaleziono - http://www.mini.pw.edu.pl/MiNIwyklady/grafy/prob-komiw.html

Ja i klkaset osób w polse są w stanie napisać program liczący taką (i sporo większą) ilość punktów optymalnie w kilkadziesiąt minut (no może teraz 2h).

problemy gdzie wyniki są nie optymalne zaczą sie rzędy punktów więcej...


a co do tematu, chyba ma jeśli pamiętam i nie pomyliłem tego z magellanem najtańszym 4.3' - takim za $110.

pozdrawiam!

--

On Thu, 26 Nov 2009 23:55:21 +0000 (UTC),   Michał wrote:

Automapa ma optymalizacje trasy. Ale programu (ani komputera) który bedzie w stanie policzyc optymalne trasy dla 19!/2 przypadków jeszcze nie wynaleziono - http://www.mini.pw.edu.pl/MiNIwyklady/grafy/prob-komiw.html

Ja i klkaset osób w polse są w stanie napisać program liczący taką (i sporo większą) ilość punktów optymalnie w kilkadziesiąt minut (no może teraz 2h).

Czy Ty i tych kilkaset osob zdaja sobie sprawe ze zagadnienie jest
NP-trudne. ?

J.

J.F. pisze:

Ja i klkaset osób w polse są w stanie napisać program liczący taką (i sporo większą) ilość punktów optymalnie w kilkadziesiąt minut (no może teraz 2h).

Czy Ty i tych kilkaset osob zdaja sobie sprawe ze zagadnienie jest
NP-trudne. ?

Nie, jeśli nie ma się pustki pomiędzy uszami.

A.

>> http://www.mini.pw.edu.pl/MiNIwyklady/grafy/prob-komiw.html
>> >Ja i klkaset osób w polse są w stanie napisać program liczący taką (i

sporo

>większą) ilość punktów optymalnie w kilkadziesiąt minut (no może teraz 2h).

Czy Ty i tych kilkaset osob zdaja sobie sprawe ze zagadnienie jest
NP-trudne. ?

oczywiście,

tam w tym linku masz: "Algorytmy przybliżone"
i dalej pusto bo link z PW a nie UW ;)


pozdrawiam.

--

Użytkownik " Michał" <mttj@WYTNIJ.gazeta.pl> napisał w wiadomości news:hen4h9$7tr$1inews.gazeta.pl...

Automapa ma optymalizacje trasy. Ale programu (ani komputera) który
bedzie w stanie policzyc optymalne trasy dla 19!/2 przypadków jeszcze
nie wynaleziono -
http://www.mini.pw.edu.pl/MiNIwyklady/grafy/prob-komiw.html

Ja i klkaset osób w polse są w stanie napisać program liczący taką (i sporo
większą) ilość punktów optymalnie w kilkadziesiąt minut (no może teraz 2h).

Oczywiście - program jest banalnie prosty. Problemem jest jedynie czas liczenia. Dla 3-4 punktów to pestka i są takie GPS, które to liczą. Dla 20 to trzeba by superkomputera i pewnie kilku (a może kilkuset?) dni obliczeń. Nawet metody heurystyczne niewiele pomogą...
Tomek

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:heo4v

Oczywiście - program jest banalnie prosty. Problemem jest jedynie czas liczenia. Dla 3-4 punktów to pestka i są takie GPS, które to liczą. Dla 20 to trzeba by superkomputera i pewnie kilku (a może kilkuset?) dni obliczeń.

Dla 20 też to robią.
Zapewne komiwojażerowi nie chodzi o super dokładność wymagającą kilkuset dni obliczeń, więc problem nie istnieje.

Pytanie było czy funkcja jest w sofcie czy jej nie ma, a nie o to czy jest ona optymalna w 100%.

Użytkownik "Cavallino" <cavallinoBEZ-SPAMU@konto.pl> napisał w wiadomości news:heo559$d4s$1news.onet.pl...

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:heo4v

Oczywiście - program jest banalnie prosty. Problemem jest jedynie czas liczenia. Dla 3-4 punktów to pestka i są takie GPS, które to liczą. Dla 20 to trzeba by superkomputera i pewnie kilku (a może kilkuset?) dni obliczeń.

Dla 20 też to robią.
Zapewne komiwojażerowi nie chodzi o super dokładność wymagającą kilkuset dni obliczeń, więc problem nie istnieje.

Pytanie było czy funkcja jest w sofcie czy jej nie ma, a nie o to czy jest ona optymalna w 100%.

A co to znaczy superdokładność? Nie liczymy wszystkich punktów?
W takich przypadkach stosuje się metody heurystyczne, ale te - żeby algorytm je uwzględnił - też wymagają czasu procesora. Generalnie - sprawa nie do przeskoczenia w dzisiejszych czasach dla urządzeń ręcznych i punktów coś około 8. EMapa Transport ma jako demo punktów 5. W domu ściagnę sobie ten program (jest demo do pobrania) i obejrzę, co to może (o ile w wersji demo można to sprawdzić).
T.
Ps. I jeszcze jedno - liczenie 20 punktów wydaje się rozsadne dla kuriera, a nie dla transportu dalekobieżnego (logistyki) - tu raczej w grę wchodzi łądunek do rozwiezienia do jednego lub 2-3 klientów. W przypadku kuriera dochodzi następny problem - czy interesuje nas droga najkrótsza, czy najszybsza (a tu dochodzi także czas [godzina], w którym się poruszamy). Sprawa dość prosta do oprogramowania, ale nie do rozwiązania dla komputera PC w rozsądnym czasie.
T.

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:

Zapewne komiwojażerowi nie chodzi o super dokładność wymagającą kilkuset dni obliczeń, więc problem nie istnieje.

Pytanie było czy funkcja jest w sofcie czy jej nie ma, a nie o to czy jest ona optymalna w 100%.

A co to znaczy superdokładność? Nie liczymy wszystkich punktów?

Pytaj producentów softu którzy stosują te metody i nie mają problemów które opisujesz.
Z tych które mają rozwiązany problem komiwojażera najtaniej Ci wyjdzie przetestowanie Navigo.
Sam program kosztuje coś koło 100 zł, ale jest (była) wersja demo.

Użytkownik "Cavallino" <cavallinoBEZ-SPAMU@konto.pl> napisał w wiadomości news:heo9i4$q1l$1news.onet.pl...

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:

Zapewne komiwojażerowi nie chodzi o super dokładność wymagającą kilkuset dni obliczeń, więc problem nie istnieje.

Pytanie było czy funkcja jest w sofcie czy jej nie ma, a nie o to czy jest ona optymalna w 100%.

A co to znaczy superdokładność? Nie liczymy wszystkich punktów?

Pytaj producentów softu którzy stosują te metody i nie mają problemów które opisujesz.
Z tych które mają rozwiązany problem komiwojażera najtaniej Ci wyjdzie przetestowanie Navigo.
Sam program kosztuje coś koło 100 zł, ale jest (była) wersja demo.

Jakiś rok temu testowałem Navigo. Były tam tylko 3 punkty pośrednie.
T.

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:

Jakiś rok temu testowałem Navigo.

Navigo8?

Były tam tylko 3 punkty pośrednie.

Może w demo?

Użytkownik "Cavallino" <cavallinoBEZ-SPAMU@konto.pl> napisał w wiadomości news:heoe51$7rn$1news.onet.pl...

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:

Jakiś rok temu testowałem Navigo.

Navigo8?

Były tam tylko 3 punkty pośrednie.

Może w demo?

Nie - miałem w testach egzemplarz Navigo2GO przed wypuszczeniem na rynek.
T.

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:

Były tam tylko 3 punkty pośrednie.

Może w demo?

Nie - miałem w testach egzemplarz Navigo2GO przed wypuszczeniem na rynek.

Igo nie ma takich problemów.
Aczkolwiek nie pokazał nic lepszej trasy niż algorytm w moim sofcie. ;-)

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:heo8ag$f10$1atlantis.news.neostrada.pl...

Użytkownik "Cavallino" <cavallinoBEZ-SPAMU@konto.pl> napisał w wiadomości news:heo559$d4s$1news.onet.pl...

Użytkownik "Tomek" <tentom@tlen.pl> napisał w wiadomości news:heo4v

Oczywiście - program jest banalnie prosty. Problemem jest jedynie czas liczenia. Dla 3-4 punktów to pestka i są takie GPS, które to liczą. Dla 20 to trzeba by superkomputera i pewnie kilku (a może kilkuset?) dni obliczeń.

Dla 20 też to robią.
Zapewne komiwojażerowi nie chodzi o super dokładność wymagającą kilkuset dni obliczeń, więc problem nie istnieje.

Pytanie było czy funkcja jest w sofcie czy jej nie ma, a nie o to czy jest ona optymalna w 100%.

A co to znaczy superdokładność? Nie liczymy wszystkich punktów?
W takich przypadkach stosuje się metody heurystyczne, ale te - żeby algorytm je uwzględnił - też wymagają czasu procesora. Generalnie - sprawa nie do przeskoczenia w dzisiejszych czasach dla urządzeń ręcznych i punktów coś około 8. EMapa Transport ma jako demo punktów 5. W domu ściagnę sobie ten program (jest demo do pobrania) i obejrzę, co to może (o ile w wersji demo można to sprawdzić).

Dostałem demo i wydaje się być w pełni funkcjonalnym programem, ale z mocno okrojoną mapą. Robiłem testy na tej mapie i po wprowadzeniu kilkunastu punktów optymalizacja trasy wyglądała bardzo przyzwoicie.

--
Pozdrawiam
Tomek

Oczywiście - program jest banalnie prosty. Problemem jest jedynie czas liczenia. Dla 3-4 punktów to pestka i są takie GPS, które to liczą. Dla 20 to trzeba by superkomputera i pewnie kilku (a może kilkuset?) dni obliczeń. Nawet metody heurystyczne niewiele pomogą...
Tomek

Żaden superkomuter, zegarek by to policzył ;)

Chodzi o słowo "optymalnie" ale to isttane przy większy cyfach,
najwięcej i tak pomieli żeby przeliczyć trase pomiędzy miastami, a nie żeby wybrac DOBRĄ (dla tej ilosci punktów nawet i optymalną!) kolejność.

bo już nie będzie jeździł po karcie pamięci.

pozdrawiam.

--