Problem komiwojażera: Różnice pomiędzy wersjami

[wersja nieprzejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 23:26, 15 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,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

@@ Linia 5: / Linia 5: @@
 Przykład:
 :Miasta={Kutno,Warszawa,Poznań,Kraków},
-:Odległości={ {Kutno,Kraków}=300, {Kutno,Warszawa}=130, {Kutno,Pozań}=180,
+:Odległości={ {Kutno,Kraków}=300, {Kutno,Warszawa}=130, {Kutno,Poznań}=180,
 ::::{Warszawa,Poznań}=320, {Warszawa,Kraków}=350, {Poznań,Kraków}=360}