Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
literówka |
+szablon Teoria Grafów |
||
| Linia 1: | Linia 1: | ||
{{Teoria grafów}} |
|||
'''Problem komiwojażera''' jest to zagadnienie z [[teoria grafów|teorii grafów]], polegające na znalezieniu minimalnego [[cykl Hamiltona|cyklu Hamiltona]] w [[graf (matematyka)|grafie]]. |
'''Problem komiwojażera''' jest to zagadnienie z [[teoria grafów|teorii grafów]], polegające na znalezieniu minimalnego [[cykl Hamiltona|cyklu Hamiltona]] w [[graf (matematyka)|grafie]]. |
||
Wersja z 21:38, 14 mar 2007
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
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,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. Szablon:Link FA