Otwórz menu główne

Zmiany

Rozmiar się nie zmienił, 6 lat temu
m
drobne redakcyjne
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.
 
'''Symetryczny problem komiwojażera (STSP)''' polega na tym, że odległośćdla pomiędzydowolnych miastamimiast A i B jestodległość z A do zawszeB jest taka sama jak z B do A. W '''asymetrycznym problemie komiwojażera (ATSP)''' odległośćodległości odte miasta A do miasta B możemogą być inna, niż odległość od miasta B do miasta Aróżne.
 
Rozwinięciem problemu komiwojażera jest [[problem marszrutyzacji]].
12 070

edycji