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

Przejdź do nawigacji Przejdź do wyszukiwania
Rozmiar się nie zmienił ,  2 lata temu
m
poprawka
(Dla symetrycznego problemu komiwojażera (n-1)!/2 dla asymetrycznego (n-1)!)
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

Menu nawigacyjne