Otwórz menu główne

Zmiany

Dla symetrycznego problemu komiwojażera (n-1)!/2 dla asymetrycznego (n-1)!
 
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{{odn|Sysło|Deo|Kowalik|1995|s=282}}<ref name=":0" />.
 
Główną trudnością problemu jest duża liczba danych do analizy. Dla ''n'' miast liczba kombinacji wynosi <math>(n-1)!</math>, tak więc dla 20 miast uzyskujemy wynik <math>19! \approx 10^{16}</math><ref>{{Cytuj | autor = Jerzy Wałaszek | rozdział = Problem komiwojażera | url = http://eduinf.waw.pl/inf/alg/001_search/0140.php | tytuł = Algorytmy i struktury danych | język = pl }}</ref>
 
'''Symetryczny problem komiwojażera (STSP)''' polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W '''asymetrycznym problemie komiwojażera (ATSP)''' odległości te mogą być różne.
 
Główną trudnością problemu jest duża liczba danych do analizy. DlaW przypadku symetrycznego problemu komiwojażera dla ''n'' miast liczba kombinacji wynosi <math>\frac{(n-1)!</math>, tak więc dla 20 miast uzyskujemy wynik <math>19! \approx 10^}{162}</math><ref>{{Cytuj | autor = Jerzy Wałaszek | rozdział = Problem komiwojażera | url = http://eduinf.waw.pl/inf/alg/001_search/0140.php | tytuł = Algorytmy i struktury danych | język = pl }}</ref>, tak więc dla 20 miast uzyskujemy wynik <math>\frac{19!}{2} \approx 3 \times 10^{16}</math>
 
Rozwinięciem problemu komiwojażera jest [[problem marszrutyzacji]].
3

edycje