Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
{{Link FA|de}} |
usuwam "szare pole" (od spacji), dr |
||
| Linia 3: | Linia 3: | ||
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. |
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: |
|||
Np. |
|||
: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. |
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. |
||
| Linia 16: | Linia 16: | ||
== Linki zewnętrzne == |
== Linki zewnętrzne == |
||
* Algorytmy genetyczne, więcej o algorytmach genetycznych, zastosowanie do rozwiązywania |
* [http://panda.bg.univ.gda.pl/~sielim/genetic/gen_komi.htm Algorytmy genetyczne, więcej o algorytmach genetycznych, zastosowanie do rozwiązywania problemu komiwojażera] |
||
[[Kategoria:Teoria grafów]] |
[[Kategoria:Teoria grafów]] |
||
Wersja z 15:05, 9 lis 2006
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 zupełny.
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.