Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
m robot dodaje: fa:مسئله فروشنده دورهگرد |
m Robot zmienia szablon: matematyka stub |
||
| Linia 21: | Linia 21: | ||
Tak sformułowany problem jest [[problem NP-zupełny|NP-zupełny]]. |
Tak sformułowany problem jest [[problem NP-zupełny|NP-zupełny]]. |
||
{{ |
{{stub}} |
||
[[Kategoria:Teoria grafów]] |
[[Kategoria:Teoria grafów]] |
||
Wersja z 20:25, 22 sie 2008
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
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,Poznań}=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 trudnym.
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.
Wersja decyzyjna
W wersji decyzyjnej problemu, danymi są graf i pewna liczba n, należy odpowiedzieć czy istnieje trasa komiwojażera krótsza od n.
Tak sformułowany problem jest NP-zupełny.