Do rozpatrzenia tego doniosłego pytania skłoniło mnie ogłoszenie na forum (dział praca). Skonsultowałem się z googlem i "dyskretnymi" kolegami w pracy, zdania są podzielone pół na pół. Moim zdaniem komiwojażerowi wszystko jedno czy będzie w każdym mieście raz, czy wiele razy. Ważne by się nie najeździł i każde miasto odwiedził.
0
0
ma odwiedzić każdy punkt i zrobić jak najmniej km
0
W problemie komiwojażera chodzi o znalezienie cyklu Hamiltona o najmniejszej wadze.
0
Wygląda, że istnieją (co najmniej) trzy określenia problemu komiwojażera:
- (potoczne), każde miasto co najmniej raz,
- (teoria grafów), szukanie "minimalnego" cyklu Hamiltona, tzn. każde miasto dokładnie raz, nie ma wtedy znaczenia gdzie zaczynamy podróż,
- (teoria grafów), szukanie "minimalnego" cyklu Hamiltona w grafie zupełnym.
0
no i oczywiście komiwojażer wraca do miejsca startu.
0
Skoro mamy cykl Hamiltona, to startując z dowolnego punktu do niego wrócimy. Gdzie niby jest opisana wersja z odwiedzaniem każdego miasta przynajmniej raz? Macie w ogóle gdzieś dowód, że wersja z odwiedzaniem każdego miasta co najmniej raz (a nie dokładnie raz) jest NP zupełna?
0
@Wibowit, rozumienie potoczne, a ściśle sformułowany problem z teorii grafów to dwie różne rzeczy. Nie Ty jeden popełniasz pomyłkę. Spójrz np. tu http://www.mini.pw.edu.pl/MiNIwyklady/grafy/prob-komiw.html. Wpierw jest opisany problem komiwojażera (bez warunku dokładnie raz), potem, bez żadnej uwagi, że dokłada dodatkowy warunek, autor przechodzi do szukania cyklu Hamiltona.
Poinformuj komiwojażera, który znajduje się w miasteczku u podnóża łańcucha górskiego i chce odwiedzić leżące w dolinach wioski między którymi nie ma bezpośrednich połączeń, że nie istnieje odpowiednia marszruta. Raczej Ci nie uwierzy.
0
A co to za różnica czy problem nazywa się problem komiwojażera czy może problem Majkela Dżeksona? Komiwojażer mając do odwiedzenia 500 miasteczek raczej nie czekałby 500 lat, aż mu coś algorytm policzy. Nazwa problemu to i tak abstrakcja.
Mam wrażenie, że ta wersja niby-potoczna jest typu P, a nie NP.
0
Wszystko jedno, co to jest „problem komiwojażera”. W ogłoszeniu o pracę czy na rozmowie warunki zadania powinny być konkretnie określone, a nie tylko: „rozwiązać problem komiwojażera”.