Użytkownik "T." napisał w wiadomości grup
dyskusyjnych:5d5cffad$0$508$6...@n...neostrada.
pl...
W dniu 2019-08-21 o 09:49, Liwiusz pisze:
> W dniu 2019-08-21 o 09:43, T. pisze:
>>> Według mnie problemu komiwojażera żadna inna nawigacja nie
>>> rozwiązuje, choć dla przeciętnego turysty problem jest wydumany.
>
>> Mnie na studiach uczono, że problem komiwojażera nie jest
>> rozwiązywalny w skończonym dla człowieka czasie, więc podejrzewam,
>> że mówimy o czymś innym.
>
>Da się policzyć dla kilku punktów (w praktyce - 5-7, może do 10).
>Kiedyś

rosnie gwaltownie, bo w trzeba wszystkie permutacje przeliczyc.

>się tym zajmowałem, robiłem jakieś próby jeszcze na komputerach PC
>XT, ale się praktycznie nie dawało.

Jak to nie - kwestia ilosci punktow przeciez.
Pamietam jakis program Microsoftu do nawigacji/planowania trasy na
Windows
(Autoroute ?), to jemu 10 punktow zajmowalo pol godziny.
Procesory w urzadzeniach z WinCE chyba podobnej klasy jak wtedy w
pecetach, a AM to robi wzglednie szybko.

>Jeśli się włączy do tego metody heurystyczne (pisząc w dużym
>uproszczeniu - odrzucając z góry drogi absurdalne na tzw. pierwszy
>rzut oka) można mocno skrócić obliczenia.
>W sumie to nie jestem pewien, czy z metod heurystycznych nie
>korzystają wszystkie nawigacje (np. trudno sobie wyobrazić
>przeliczanie wszystkich dróg w Polsce przy wyszukiwaniu drogi z A do
>B - to absurdalne).

Kiedys sie bawilem w wyszukiwanie najkrotszych drog w grafach i szlo
to zadziwiajaco szybko ... ale grafy byly malutkie.
Czasem mnie nachodzi zeby to zrobic na mapie Polski ... ale trzeba by
najpierw dane rozpoznac, np OSM..

Uwzglednienie miejskich ulic znacznie rozbudowuje graf ... i tu bym
pomyslal zeby zastapic te miasta jakims uproszczonym schematem drog
tranzytowych.
Tylko jak mamy korki, to znow sie moze okazac, ze najszybciej to
zjechac z obwodnicy i jakimis oplotkami ...

>Problem komiwojażera można nawet liczyć nieco na piechotę korzystając
>z programowania matematycznego, a najlepsze wyniki daje łącząc obie
>te metody i wykorzystując komputery.

Tylko ze w praktyce to musisz zaczac od policzenia tras miedzy
wszystkimi punktami.
I tu juz sie komputer przydaje.

A potem dodatek praktyczny - korki sie tworza w roznych godzinach,
zalozmy ze w miare systematycznie.
Obliczyc najszybsza trase uwzgledniajac korki, ktore beda w
spodziewanym czasie dojazdu do nich ...


J.