Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Dla symetrycznego problemu komiwojażera (n-1)!/2 dla asymetrycznego (n-1)! |
m poprawka |
||
Linia 7:
'''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
Rozwinięciem problemu komiwojażera jest [[problem marszrutyzacji]].
| |||