Problem komiwojażera


Tematy pokrewne  
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
 

Problem

W danym grafie znaleźć ścieżkę o najmniejszej sumie wag krawędzi, która przechodzi dokładnie jeden raz przez każdy wierzchołek i wraca do wierzchołka startowego.

 

 

Wyobraźmy sobie komiwojażera, który podróżuje od miasta do miasta, sprzedając 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, który wyznacza wszystkie cykle Hamiltona, liczy sumę wag krawędzi i zwraca cykl o najmniejszej sumie wag. 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.

 

Algorytm rozwiązujący problem komiwojażera dla małych grafów

Rekurencyjna procedura TSP(n,graf,v,vo,d,dH,S,SH,visited)
Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Definicja grafu powinna udostępniać wagi krawędzi.
v  –  wierzchołek bieżący, v symbol C
v0  –  wierzchołek startowy, v0 symbol C
d  –  suma wag krawędzi cyklu Hamiltona, d symbol C
dH  –  pomocnicza suma wag krawędzi, dH symbol C
S  –  stos wierzchołków
SH  –  pomocniczy stos wierzchołków
visited  –  n elementowa tablica logiczna odwiedzin.
Wyjście:
S  –  stos zawierający numery kolejnych wierzchołków cyklu Hamiltona o najmniejszej sumie wag krawędzi lub stos pusty w przypadku braku cyklu Hamiltona w grafie.
d  –  suma wag krawędzi cyklu Hamiltona
Elementy pomocnicze:
u  –  wierzchołek, u symbol C
Lista kroków:
K01: SH.push(v) ; Odwiedzony wierzchołek dopisujemy do ścieżki
K02: Jeśli SH nie zawiera n wierzchołków, to idź do K10 ; Jeśli brak ścieżki Hamiltona, przechodzimy do wyszukiwania
K03: Jeśli nie istnieje krawędź z v do v0, to idź do K17 ; Jeśli ścieżka Hamiltona nie jest cyklem, odrzucamy ją
K04: dHdH + waga krawędzi z v do v0 ; Uwzględniamy w sumie wagę ostatniej krawędzi cyklu
K05: Jeśli dHd, idź do K08 ; Jeśli znaleziony cykl jest gorszy od bieżącego, odrzucamy go
K06: ddH ; Zapamiętujemy sumę wag cyklu
K07: Skopiuj stos SH do stosu S ; oraz sam cykl Hamiltona
K08: dHdH - waga krawędzi z v do v0 ; Usuwamy wagę ostatniej krawędzi z sumy
K09: Idź do K17  
K10: visited[v] ← true ; Wierzchołek zaznaczamy jako odwiedzony, aby nie był ponownie wybierany przez DFS
K11: Dla każdego sąsiada u wierzchołka v wykonuj K12...K15 ; Przechodzimy przez listę sąsiedztwa
K12:     Jeśli visited[u] = true, to następny obieg pętli K11 ; Omijamy wierzchołki odwiedzone
K13:     dHdH + waga krawędzi z v do u ; Obliczamy nową sumę wag krawędzi ścieżki
K14:     TSP(n,graf,u,vo,d,dH,S,SH,visited) ; Wywołujemy rekurencyjnie poszukiwanie cyklu
K15:     dHdH - waga krawędzi z v do u ; Usuwamy wagę krawędzi z sumy
K16: visited[v] ← false ; Zwalniamy bieżący wierzchołek
K17: SH.pop() ; Usuwamy bieżący wierzchołek ze ścieżki
K18: Zakończ  
Lista kroków algorytmu głównego
K01: Utwórz i wyzeruj visited, S i SH  
K02: d∞;  dH ← 0 ; Początkową sumę ustawiamy jako największą z możliwych
K03: TSP(v0) ; Wyszukiwanie cyklu Hamiltona rozpoczynamy od wierzchołka startowego
K04: Jeśli S.empty() = false, to pisz S oraz d
inaczej pisz "NO HAMILTONIAN CYCLE"
; Sprawdzamy, czy algorytm znalazł cykl Hamiltona. Jeśli tak, to wypisujemy go.
K05: Zakończ  

Uwaga: większość parametrów wejściowych może być zrealizowana jako zmienne globalne, co znacznie uprości wywołania rekurencyjne.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Poniższy program jest przykładową realizacją algorytmu rozwiązywania problemu komiwojażera. Z uwagi na wykładniczą klasę złożoności obliczeniowej program potrafi w rozsądnym czasie znaleźć rozwiązanie tylko dla grafów o niewielkiej liczbie węzłów (powiedzmy, do 20). Definicja danych wejściowych jest następująca:

 

W pierwszym wierszu program odczytuje kolejno liczbę wierzchołków n oraz liczbę krawędzi m. W m kolejnych wierszach znajdują się definicje krawędzi. Każda definicja składa się z trzech liczb x y w. Pierwsza i druga liczba określa wierzchołki grafu, które są ze sobą połączone tą krawędzią. Trzecia liczba jest wagą krawędzi w.

Jako wierzchołek startowy program przyjmuje wierzchołek o numerze 0.

Na wyjściu zostaje wypisany cykl Hamiltona o najmniejszej sumie wag krawędzi oraz wartość tej sumy. Jeśli graf nie zawiera cyklu Hamiltona, to pojawi się napis:

NO HAMILTONIAN CYCLE.

 

Przykładowe dane:

8 16
0 1 2 0 2 2 0 3 4 0 4 3
1 2 2 1 5 1 1 6 1
2 4 2 2 5 1
3 5 2 3 7 3
4 6 4 4 7 5
5 6 2 5 7 2
6 7 2
 
Lazarus
// Problem komiwojażera
// Data: 22.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program TSProblem;

// Typy dla dynamicznej macierzy sąsiedztwa
type
  nptr = array of boolean;        // Wiersz tablicy sąsiedztwa
  wnptr = array of integer;       // Wiersz macierzy wag krawędzi

// Zmienne globalne
var
  n,m,v0,d,dh,sptr,shptr : integer;
  A       : array of nptr;        // Macierz sąsiedztwa
  W       : array of wnptr;       // Macierz wag krawędzi
  S,Sh    : array of integer;     // Stosy w tablicy
  visited : array of boolean;     // Tablica odwiedzin

// Rekurencyjna procedura poszukiwania cyklu Hamiltona
// o najmniejszej sumie wag krawędzi
// v - wierzchołek bieżący
//----------------------------------------------------
procedure TSP(v : integer);
var
  u : integer;
begin
  Sh[shptr] := v;                 // zapamiętujemy na stosie bieżący wierzchołek
  inc(shptr);

  if shptr < n then               // jeśli brak ścieżki Hamiltona, to jej szukamy
  begin
    visited[v] := true;           // Oznaczamy bieżący wierzchołek jako odwiedzony
    for u := 0 to n - 1 do        // Przeglądamy sąsiadów wierzchołka v
      if A[v][u] and not visited[u] then  // Szukamy nieodwiedzonego jeszcze sąsiada
      begin
        inc(dh,W[v][u]);          // Dodajemy wagę krawędzi v-u do sumy
        TSP(u);                   // Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
        dec(dh,W[v][u]);          // Usuwamy wagę krawędzi z sumy
      end;
    visited[v] := false;          // Zwalniamy bieżący wierzchołek
  end
  else if A[v0][v] then           // Jeśli znaleziona ścieżka jest cyklem Hamiltona
  begin
    inc(dh,W[v][v0]);             // to sprawdzamy, czy ma najmniejszą sumę wag
    if dh < d then                // Jeśli tak,
    begin
      d := dh;                    // To zapamiętujemy tę sumę
      for u := 0 to shptr - 1 do  // oraz kopiujemy stos Sh do S
        S[u] := Sh[u];
      sptr := shptr;
    end;
    dec(dh,W[v][v0]);             // Usuwamy wagę krawędzi v-v0 z sumy
  end;
  dec(shptr);                     // Usuwamy bieżący wierzchołek ze ścieżki
end;

//**********************
//*** Program główny ***
//**********************

var
  i,j,x,y,z : integer;
begin
  read(n,m);                      // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy struktury dynamiczne i inicjujemy je

  SetLength(S,n);
  SetLength(Sh,n);
  SetLength(visited,n);
  SetLength(A,n);
  SetLength(W,n);
  for i := 0 to n - 1 do
  begin
    SetLength(A[i],n);
    SetLength(W[i],n);
    for j := 0 to n - 1 do
    begin
      A[i][j] := false;
      W[i][j] := 0;
    end;
    visited[i] := false;
  end;
  sptr := 0;
  shptr := 0;

  // Odczytujemy dane wejściowe

  for i := 0 to m - 1 do
  begin
    read(x,y,z);
    A[x][y] := true;              // Krawędź x-y
    A[y][x] := true;
    W[x][y] := z;                 // Waga krawędzi x-y
    W[y][x] := z;
  end;

  writeln;

  // Rozpoczynamy algorytm

  d  := MAXINT;
  dh := 0;
  v0 := 0;
  TSP(v0);
  if sptr > 0 then
  begin
    for i := 0 to sptr - 1 do write(S[i],' ');
    writeln(v0);
    writeln('d = ',d);
  end
  else writeln('NO HAMILTONIAN CYCLE');

  writeln;

  // Usuwamy tablice dynamiczne

  SetLength(S,0);
  SetLength(Sh,0);
  SetLength(visited,0);

  for i := 0 to n - 1 do
  begin
    SetLength(A[i],0);
    SetLength(W[i],0);
  end;

  SetLength(A,0);
  SetLength(W,0);

end.
Code::Blocks
// Problem komiwojażera
// Data: 22.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Zmienne globalne

int n,m,v0,d,dh,sptr,shptr;
bool **A;                         // Macierz sąsiedztwa
int **W;                          // Macierz wag krawędzi
int *S,*Sh;                       // Stosy w tablicy
bool *visited;                    // Tablica odwiedzin

// Rekurencyjna procedura poszukiwania cyklu Hamiltona
// o najmniejszej sumie wag krawędzi
// v - wierzchołek bieżący
//----------------------------------------------------
void TSP(int v)
{
  int u;

  Sh[shptr++] = v;                // zapamiętujemy na stosie bieżący wierzchołek

  if(shptr < n)                   // jeśli brak ścieżki Hamiltona, to jej szukamy
  {
    visited[v] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
    for(u = 0; u < n; u++)        // Przeglądamy sąsiadów wierzchołka v
      if(A[v][u] && !visited[u])  // Szukamy nieodwiedzonego jeszcze sąsiada
      {
        dh += W[v][u];            // Dodajemy wagę krawędzi v-u do sumy
        TSP(u);                   // Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
        dh -= W[v][u];            // Usuwamy wagę krawędzi z sumy
      }
    visited[v] = false;           // Zwalniamy bieżący wierzchołek
  }
  else if(A[v0][v])               // Jeśli znaleziona ścieżka jest cyklem Hamiltona
  {
    dh += W[v][v0];               // to sprawdzamy, czy ma najmniejszą sumę wag
    if(dh < d)                    // Jeśli tak,
    {
      d = dh;                     // To zapamiętujemy tę sumę
      for(u = 0; u < shptr; u++)  // oraz kopiujemy stos Sh do S
        S[u] = Sh[u];
      sptr = shptr;
    }
    dh -= W[v][v0];               // Usuwamy wagę krawędzi v-v0 z sumy
  }
  shptr--;                        // Usuwamy bieżący wierzchołek ze ścieżki
}

//**********************
//*** Program główny ***
//**********************

int main()
{
  int i,j,x,y,z;

  cin >> n >> m;                  // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy struktury dynamiczne i inicjujemy je

  S       = new int [n];
  Sh      = new int [n];
  visited = new bool [n];
  A       = new bool * [n];
  W       = new int * [n];
  for(i = 0; i < n; i++)
  {
    A[i] = new bool [n];
    W[i] = new int [n];
    for(j = 0; j < n; j++)
    {
      A[i][j] = false;
      W[i][j] = 0;
    }
    visited[i] = false;
  }
  sptr = shptr = 0;

  // Odczytujemy dane wejściowe

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> z;
    A[x][y] = A[y][x] = true;     // Krawędź x-y
    W[x][y] = W[y][x] = z;        // Waga krawędzi x-y
  }

  cout << endl;

  // Rozpoczynamy algorytm

  d  = MAXINT;
  dh = v0 = 0;
  TSP(v0);
  if(sptr)
  {
    for(i = 0; i < sptr; i++) cout << S[i] << " ";
    cout << v0 << endl;
    cout << "d = " << d << endl;
  }
  else cout << "NO HAMILTONIAN CYCLE" << endl;

  cout << endl;

  // Usuwamy tablice dynamiczne

  delete [] S;
  delete [] Sh;
  delete [] visited;

  for(i = 0; i < n; i++)
  {
    delete [] A[i];
    delete [] W[i];
  }

  delete [] A;
  delete [] W;

  return 0;
}
Free Basic
' Problem komiwojażera
' Data: 22.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Zmienne globalne

Dim Shared As Integer n,m,v0,d,dh,sptr,shptr
Dim Shared As Byte Ptr Ptr A     ' Macierz sąsiedztwa
Dim Shared As Integer Ptr Ptr W  ' Macierz wag krawędzi
Dim Shared As Integer Ptr S,Sh   ' Stosy w tablicy
Dim Shared As Byte Ptr visited   ' Tablica odwiedzin

' Rekurencyjna procedura poszukiwania cyklu Hamiltona
' o najmniejszej sumie wag krawędzi
' v - wierzchołek bieżący
'----------------------------------------------------
Sub TSP(ByVal v As Integer)

  Dim As Integer u

  Sh[shptr] = v                   ' zapamiętujemy na stosie bieżący wierzchołek
  shptr += 1
  
  If shptr < n Then               ' jeśli brak ścieżki Hamiltona, to jej szukamy
    visited[v] = 1                ' Oznaczamy bieżący wierzchołek jako odwiedzony
    For u = 0 To n - 1            ' Przeglądamy sąsiadów wierzchołka v
      If (A[v][u] = 1) AndAlso (visited[u] = 0) Then  ' Szukamy nieodwiedzonego jeszcze sąsiada
        dh += W[v][u]             ' Dodajemy wagę krawędzi v-u do sumy
        TSP(u)                    ' Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
        dh -= W[v][u]             ' Usuwamy wagę krawędzi z sumy
      End If
    Next
    visited[v] = 0                ' Zwalniamy bieżący wierzchołek
  ElseIf A[v0][v] = 1 Then        ' Jeśli znaleziona ścieżka jest cyklem Hamiltona
    dh += W[v][v0]                ' to sprawdzamy, czy ma najmniejszą sumę wag
    If dh < d Then                ' Jeśli tak,
      d = dh                      ' To zapamiętujemy tę sumę
      For u = 0 To shptr - 1      ' oraz kopiujemy stos Sh do S
        S[u] = Sh[u]
      Next
      sptr = shptr
    End If
    dh -= W[v][v0]                ' Usuwamy wagę krawędzi v-v0 z sumy
  End If
  shptr -= 1                      ' Usuwamy bieżący wierzchołek ze ścieżki
End Sub

'**********************
'*** Program główny ***
'**********************

Dim as Integer i,j,x,y,z

Open Cons For Input As #1

Input #1,n,m                      ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy struktury dynamiczne i inicjujemy je

S       = New Integer [n]
Sh      = New Integer [n]
visited = New Byte [n]
A       = New Byte Ptr [n]
W       = New Integer Ptr [n]
For i = 0 To n - 1
  A[i] = New Byte [n]
  W[i] = New Integer [n]
  For j = 0 To n - 1
    A[i][j] = 0
    W[i][j] = 0
  Next
  visited[i] = false
Next
sptr  = 0
shptr = 0

' Odczytujemy dane wejściowe

For i = 0 To m - 1
  Input #1,x,y,z
  A[x][y] = 1                     ' Krawędź x-y
  A[y][x] = 1
  W[x][y] = z                     ' Waga krawędzi x-y
  W[y][x] = z
Next

Close #1

Print

' Rozpoczynamy algorytm

d  = MAXINT
dh = 0
v0 = 0
TSP(v0)
If sptr > 0 Then
  For i = 0 To sptr - 1
  	 Print S[i];
  Next
  Print v0
  Print " d =";d
Else
  Print "NO HAMILTONIAN CYCLE"
End If

Print

' Usuwamy tablice dynamiczne

Delete [] S
Delete [] Sh
Delete [] visited

For i = 0 To n - 1
  Delete [] A[i]
  Delete [] W[i]
Next

Delete [] A
Delete [] W

End
Wynik
8 16
0 1 2 0 2 2 0 3 4 0 4 3
1 2 2 1 5 1 1 6 1
2 4 2 2 5 1
3 5 2 3 7 3
4 6 4 4 7 5
5 6 2 5 7 2
6 7 2

0 1 6 7 3 5 2 4 0
d = 16

 



List do administratora Serwisu Edukacyjnego Nauczycieli 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

©2017 mgr Jerzy Wałaszek

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