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ś
się tym zajmowałem, robiłem jakieś próby jeszcze na komputerach PC XT,
ale się praktycznie nie dawało. 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).
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.
T.