Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
m lit. |
m drobne redakcyjne |
||
| Linia 4: | Linia 4: | ||
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. |
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. |
||
'''Symetryczny problem komiwojażera (STSP)''' polega na tym, że |
'''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. |
||
Rozwinięciem problemu komiwojażera jest [[problem marszrutyzacji]]. |
Rozwinięciem problemu komiwojażera jest [[problem marszrutyzacji]]. |
||
Wersja z 14:36, 6 paź 2012
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
Problem komiwojażera (TSP - ang. travelling 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ść/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.
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.
Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
Przykład
Miasta: Kutno,Warszawa,Poznań,Kraków
Odległości:
Kutno Warszawa Poznań Kraków Kutno 0 130 180 300 Warszawa 130 0 320 350 Poznań 180 320 0 360 Kraków 300 350 360 0
Należy znaleźć najkrótszą trasę zaczynającą się np. z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.
Problem ten jest NP-trudny.
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.