Problem komiwojażera: Różnice pomiędzy wersjami

drobne redakcyjne
m (Removing Link FA template (handled by wikidata))
(drobne redakcyjne)
{{Teoria grafów}}
'''Problem komiwojażera''' (TSP - {{ang. |travelling salesman problem, TSP}}) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego [[cykl Hamiltona|cyklu Hamiltona]] w [[graf (matematyka)|pełnym grafie ważonym]].
 
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ść/cena podróży/czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej/najtańszej/najszybszej drogi łączącej wszystkie miasta zaczynającej się i kończącej się w określonym punkcie.
96 429

edycji