Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
m →Linki zewnętrzne: - martwy link |
Nie podano opisu zmian |
||
| Linia 10: | Linia 10: | ||
Należy znaleźć najkrótszą trasę wychodzącą np. z Kutna i przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna. |
Należy znaleźć najkrótszą trasę wychodzącą np. z Kutna i przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna. |
||
Problem ten jest [[Problem NP |
Problem ten jest [[Problem NP trudny|NP trudny]]. |
||
'''Symetryczny problem komiwojażera (STSP)''' polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. |
'''Symetryczny problem komiwojażera (STSP)''' polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. |
||
Wersja z 15:47, 12 lut 2007
Problem komiwojażera jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w grafie.
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ść pomiędzy każdą parą miast.
Przykład:
- Miasta={Kutno,Warszawa,Poznań,Kraków},
- Odległości={ {Kutno,Kraków}=300, {Kutno,Warszawa}=130, {Kutno,Pozań}=180,
- {Warszawa,Poznań}=320, {Warszawa,Kraków}=350, {Poznań,Kraków}=360}
Należy znaleźć najkrótszą trasę wychodzącą np. z Kutna i przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.
Problem ten jest NP trudny.
Symetryczny problem komiwojażera (STSP) polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. W asymetrycznym problemie komiwojażera (ATSP) odległość od miasta A do miasta B może być inna, niż odległość od miasta B do miasta A. Szablon:Link FA