Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
→Historia: styl |
Błąd wyznaczający liczbę kombinacji dla n miast. Jeśli wzór jest n!/2 to dla 20 miast powinno być 20!/2, ale wg podanej przeze mnie strony wzór to raczej (n-1)! dlatego poprawiłem odpowiednio. |
||
Linia 5:
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>
'''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.
| |||