Otwórz menu główne

Zmiany

Rozmiar się nie zmienił, 1 rok temu
m
poprawka
'''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. W przypadku symetrycznego problemu komiwojażera dla ''n'' miast liczba kombinacji wynosi <math>\frac{(n-1)!}{2}</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 36 \times 10^{16}</math>
 
Rozwinięciem problemu komiwojażera jest [[problem marszrutyzacji]].
3

edycje