Problem komiwojażera jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w grafie.
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast.
Np.
Miasta={Kutno,Warszawa,Poznań,Kraków},

Odległości={ {Kutno,Kraków}=300, {Kutno,Warszawa}=130, {Kutno,Pozań}=180,

             {Warszawa,Poznań}=320, {Warszawa,Kraków}=350, {Poznań,Kraków}=360}


Należy znaleźć najkrótszą trasę wychodzącą np. z Kutna i przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.
Problem ten jest NP zupełny.
Nie są znane algorytmy dające dokładne rozwiązanie problemu w czasie wielomianowym. W praktyce najefektywniejszymi sposobami jego rozwiązania są algorytmy genetyczne, często wykorzystywane w połączeniu z heurystycznymi (np. heurystyka najbliższego sąsiada). Są to jednak metody dające w większości jedynie rozwiązania bliskie optymalnemu. Niekiedy tylko zdarza się, że otrzymane rozwiązanie jest optymalne. Zależy to głównie od ilości punktów oraz czasem szczęścia (generacja populacji początkowej, krzyżowanie oraz mutacja w algorytmach genetycznych zawierają element losowy).
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.