Otwórz menu główne

Zmiany

m
drobne redakcyjne
{{Teoria grafów}}
'''Problem komiwojażera''' (TSP - ang. travelling salesman problem) jest to zagadnienie z [[teoria grafów|teorii grafów]]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.
12 070

edycji