Problem komiwojażera

Wymagane jest zapoznanie się z następującymi podrozdziałami:

    OL008 - Podstawowe informacje o grafach i sposobach ich reprezentacji w pamięci komputera.
    OL017 - Pojęcia podstawowe z teorii grafów
    OL025 - Cykl Hamiltona


Wyobraźmy sobie komiwojażera, który podróżuje od miasta do miasta, sprzedając tam swoje produkty lub zawierając różne oferty handlowe. Wyrusza z miasta rodzinnego, po czym jego trasa przebiega dokładnie jeden raz przez każde z miast. Na koniec komiwojażer powraca do swojego miasta rodzinnego. Z oczywistych powodów chce, aby trasa podróży była najkrótszą ze wszystkich możliwych tras. W ten sposób powstaje problem wędrującego komiwojażera (ang. TSP - Travelling Salesman Problem).

W terminologii grafów miasta są wierzchołkami grafu, a trasy pomiędzy nimi to krawędzie z wagami. Waga krawędzi może odpowiadać odległości pomiędzy miastami połączonymi tą krawędzią, czasowi podróży lub kosztom przejazdu - zależy, co chcemy w podróżny komiwojażera zminimalizować. Trasa komiwojażera jest cyklem przechodzącym przez każdy wierzchołek grafu dokładnie jeden raz - jest to zatem cykl Hamiltona.

Znalezienie właściwego cyklu Hamiltona jest zadaniem bardzo trudnym obliczeniowo. Wyobraźmy sobie graf zupełny (ang. complete graph - graf, w którym każdy wierzchołek jest połączony z każdym) o 10 wierzchołkach.

Ile różnych cykli Hamiltona zawiera taki graf? Otóż pierwszą krawędź cyklu można wybrać na 9 różnych sposobów, ponieważ każdy wierzchołek grafu jest połączony krawędzią z pozostałymi dziewięcioma. Po wyborze pierwszej krawędzi pozostaje nam 8 możliwych wyborów, później 7, 6 5 ... 1. W efekcie otrzymujemy liczbę cykli Hamiltona równą:

LH = 9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 9! = 362880

Dla n wierzchołków:

LH = (n - 1) • (n - 2) • ... • 3 • 2 • 1 = (n - 1)!

Wynik jest bardzo niekorzystny, ponieważ prowadzi do wykładniczej klasy złożoności obliczeniowej O(n!). Dla każdego znalezionego cyklu Hamiltona liczymy sumę wag krawędzi i zapamiętujemy cykl o najmniejszej sumie wag. Na przykład w naszym grafie może to być następujący cykl (nie sugeruj się długością krawędzi na rysunku - ważne są wagi, a nie długość kreski - czasami miasta mało odległe w linii prostej mogą być połączone długą trasą ze względu na warunki terenowe: góry, jeziora, bagna itp.):

Grafy odwzorowujące rzeczywiste sieci połączeń zwykle nie są zupełne - ekonomicznie nieuzasadnione byłoby budowanie osobnych dróg pomiędzy każdą parą miast. Zwykle drogi przebiegają od jednego miasta do drugiego, a w niektórych się rozchodzą. Dlatego opisany powyżej przypadek jest przypadkiem pesymistycznym. Jednakże problem dalej posiada wykładniczą klasę złożoności obliczeniowej. Rozważmy dla przykładu graf posiadający 100 wierzchołków. Załóżmy, iż każdy wierzchołek łączy się z czterema innymi wierzchołkami grafu. Zatem ich stopień wynosi 4. W pesymistycznym przypadku ilość cykli Hamiltona do przebadania może wynosić:

Z pierwszego wierzchołka możemy pójść na 4 różne sposoby, z drugiego na 3, z trzeciego na 3, ..., i z 99 na trzy. Otrzymujemy zatem:

LH = 4 • 399 ≈ 3100 ≈ 5,15 • 1047

Zatem dla grafu posiadającego n wierzchołków o stopniu s otrzymamy
LH ≈ (s - 1)n

Czyli liczba cykli lub ścieżek do przebadania rośnie wykładniczo. Nawet na szybkim komputerze wyznaczenie rozwiązania może przekroczyć stulecia. Problemy algorytmiczne o złożoności wykładniczej są traktowane jako nierozwiązywalne dla dużych n.

Istnieją algorytmy znajdujące przybliżone rozwiązania problemu wędrującego komiwojażera w czasie wielomianowym, lecz są one bardzo zaawansowane i trudne w implementacji. Jeśli liczba wierzchołków w grafie nie jest duża (np. do 20) i graf nie jest grafem zupełnym (złożoność O(n!)), to rozwiązanie problemu komiwojażera możemy uzyskać prostym algorytmem brute force, który wyznacza wszystkie cykle Hamiltona, liczy ich długość i zwraca najkrótszy cykl. Rozwiązanie to jest o tyle dobre, iż zawsze zwróci cykl optymalny, a nie przybliżony. Również jest łatwe do zrozumienia i implementacji. Podstawowa wada to wykładnicza złożoność obliczeniowa, która uniemożliwia analizę większych grafów.

Dane wejściowe

n - liczba wierzchołków w grafie
L[ ] - n elementowa tablica list sąsiedztwa. Każdy element tablicy jest listą wierzchołków oraz wag krawędzi prowadzących do tych wierzchołków: {v, d}. Wagi krawędzie są większe od zera.
v - numer wierzchołka grafu

Dane wyjściowe

q - lista zawierająca numery kolejnych wierzchołków cyklu Hamiltona o najmniejszej sumie wag krawędzi lub lista pusta w przypadku braku cyklu Hamiltona w grafie.
d - wartość sumy wag krawędzi dla wyznaczonego cyklu Hamiltona.

Dane pomocnicze

visited[ ] - tablica logiczna zapamiętująca odwiedzane wierzchołki
qH - lista robocza do wyszukiwania cykli Hamiltona
dH - zawiera bieżącą sumę wag krawędzi dla tworzonej ścieżki w grafie
x - element listy sąsiedztwa:
x.v - numer sąsiedniego wierzchołka
x.d - waga krawędzi prowadzącej do wierzchołka x.w

Lista kroków rekurencyjnej procedury TSP(v)

K01: Dopisz v na koniec kolejki qH Odwiedzony wierzchołek dopisujemy do ścieżki
K02: Jeśli qH nie zawiera n wierzchołków, idź do kroku K10 Jeśli brak ścieżki Hamiltona, przechodzimy do wyszukiwania
K03: Jeśli nie istnieje krawędź z v do 1, idź do kroku K17 Jeśli ścieżka Hamiltona nie jest cyklem, odrzucamy ją
K04: dH ← dH + waga krawędzi z v do 1 Uwzględniamy w sumie wagę ostatniej krawędzi cyklu
K05: Jeśli dH ≥ d, idź do kroku K08 Jeśli znaleziony cykl jest gorszy od bieżącego, odrzucamy go
K06: d ← dH Zapamiętujemy sumę wag cyklu
K07: q ← qH Oraz sam cykl Hamiltona
K08: dH ← dH - waga krawędzi z v do 1 Usuwamy wagę ostatniej krawędzi z sumy
K09: Idź do kroku K17  
K10: visited[v] ← true Wierzchołek zaznaczamy jako odwiedzony, aby nie był ponownie wybierany przez DFS
K11: Dla każdego x z L[v] wykonuj kroki K12...K15 Przechodzimy przez listę sąsiedztwa
K12:     Jeśli visited[x.v] = true, wykonaj następny obieg pętli K11 Omijamy wierzchołki odwiedzone
K13:     dH ← dH + x.d Obliczamy nową sumę wag krawędzi ścieżki
K14:     TSP(x.v) Wywołujemy rekurencyjnie poszukiwanie cyklu
K15:     dH ← dH - x.d Usuwamy wagę krawędzi z sumy
K16: visited[v] ← false Zwalniamy bieżący wierzchołek
K17: Usuń v z końca kolejki qH Usuwamy bieżący wierzchołek ze ścieżki
K18: Zakończ algorytm  

Lista kroków algorytmu głównego

K01: Wyzeruj visited[], kolejki q i qH  
K02: d ← ∞;  dH ← 0 Początkową sumę ustawiamy jako największą z możliwych
K03: TSP(1) Wyszukiwanie cyklu Hamiltona rozpoczynamy od wierzchołka 1
K04: Jeśli q zawiera cykl, pisz zawartość q oraz d
inaczej pisz "GRAF NIE ZAWIERA CYKLU HAMILTONA"
Sprawdzamy, czy algorytm znalazł cykl Hamiltona. Jeśli tak, to wypisujemy go.
K05: Zakończ algorytm  

Na podstawie algorytmu napiszemy na zajęciach koła informatycznego program w języku C++ rozwiązujący problem podróżującego komiwojażera dla małych grafów (do 20...30 wierzchołków). Dane wejściowe posiadają następującą specyfikację:

Pierwsza liczba oznacza liczbę wierzchołków w grafie nieskierowanym - n.
Druga liczba oznacza oznacza liczbę krawędzi - m
Kolejno podajemy m definicji krawędzi. Każda definicja składa się z trzech liczb:
    dwie pierwsze liczby oznaczają numery wierzchołków połączonych krawędzią
    trzecia liczba jest wagą krawędzi

Poniżej mamy testowy graf z cyklami Hamiltona dla programu.

8 16
1 2 4 1 3 2 1 4 2 1 5 3
2 6 2 2 8 3
3 4 2 3 6 1 3 7 1
4 5 2 4 6 1
5 7 4 5 8 5
6 7 2 6 8 2
7 8 2
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P027 Problem wędrującego komiwojażera

#include <iostream>
#include <list>

using namespace std;

const int MAXV   = 50;         // maksymalna liczba wierzchołków
const int MAXINT = 2147483647; // maksymalna, dodatnia liczba całkowita

// Struktura krawędzi z wagą

struct edge
{
  int v,d;
};

// Zmienne globalne

int  n,m,d,dh;  // liczba wierzchołków i krawędzi w grafie
list <edge> L[MAXV + 1];
list <int> q,qh;
bool visited[MAXV + 1];

// Rekurencyjna funkcja DFS wyszukująca cykl Hamiltona
// o minimalnej sumie wag krawędzi

void TSP(int v)
{
  qh.push_back(v);
  if(qh.size() == n)
  {
     for(list<edge>::iterator i = L[v].begin(); i != L[v].end(); i++)
       if(i->v == 1)
       {
         dh += i->d;
         if(dh < d)
         {
           d = dh;
           q.assign(qh.begin(), qh.end());
           q.push_back(1);   // zamykamy cykl
         }
         dh -= i->d;
         break;        
       }
  }
  else
  {
     visited[v] = true;
     for(list<edge>::iterator i = L[v].begin(); i != L[v].end(); i++)
       if(!visited[i->v])
       {
         dh += i->d;
         TSP(i->v);
         dh -= i->d;
       }
     visited[v] = false;
  }
  qh.pop_back();
}
     
main()
{

// Odczytujemy definicję grafu ze standardowego wejścia

  cin >> n >> m;

  for(int i = 1; i <= m; i++)
  {
    int v,w,dx; cin >> v >> w >> dx;
    edge x;
    x.v = w; x.d = dx; L[v].push_back(x);
    x.v = v;           L[w].push_back(x);        
  }

  cout << endl;

// Rozpoczynamy wyszukiwanie cyklu Hamiltona
// o najmniejszej sumie wag krawędzi

  for(int i = 1; i <= n; i++) visited[i] = false;
  q.clear(); qh.clear();
  d = MAXINT; dh = 0;
  TSP(1);
  
// Wypisanie wyników

  if(q.size())
  {
    cout << "CYKL HAMILTONA  : ";
    for(list<int>::iterator i = q.begin(); i != q.end(); i++)
      cout << (* i) << " ";
    cout << "\nSUMA WAG WYNOSI : " << d << endl;
  }
  else cout << "GRAF NIE POSIADA CYKLU HAMILTONA\n";

  cout << endl;  
  system("PAUSE");
}
8 16
1 2 4 1 3 2 1 4 2 1 5 3
2 6 2 2 8 3
3 4 2 3 6 1 3 7 1
4 5 2 4 6 1
5 7 4 5 8 5
6 7 2 6 8 2
7 8 2

CYKL HAMILTONA  : 1 3 7 8 2 6 4 5 1
SUMA WAG WYNOSI : 16

Sprawdź, czy znaleziony przez program cykl Hamiltona jest faktycznie cyklem o najmniejszej sumie wag krawędzi.



List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.