Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Problem komiwojażera

SPIS TREŚCI

Problem

W danym grafie należy 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.

Rozwiązanie

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.

obrazek

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ą:

L H  = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 9! = 362880

Dla n  wierzchołków:

L H  = ( 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. ):

obrazek

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:
L H  = 4 • 3 99 ≈ 3 100 ≈ 5, 15 • 10 47

Zatem dla grafu posiadającego n  wierzchołków o stopniu s  otrzymamy

L H  ≈ ( 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, v o, d, d H, S, S H, visited )

Wejście:

n  –  liczba wierzchołków w grafie, n  ∈ 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  ∈ C.
v 0  –  wierzchołek startowy, v 0  ∈ C.
d  –  suma wag krawędzi cyklu Hamiltona, d  ∈ C.
d H  –  pomocnicza suma wag krawędzi, d H  ∈ C.
S  –  stos wierzchołków.
S H  –  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.
Zmienne pomocnicze:
u  –  wierzchołek, u  ∈ C.

Lista kroków:

K01: S H.push ( v  ) Odwiedzony wierzchołek dopisujemy do ścieżki
K02: Jeśli S H  nie zawiera n  wierzchołków,
to idź do kroku K10
Jeśli brak ścieżki Hamiltona, przechodzimy do wyszukiwania
K03: Jeśli nie istnieje krawędź z v  do v 0,
to idź do kroku K17
Jeśli ścieżka Hamiltona nie jest cyklem, odrzucamy ją
K04: d H  ← d H  + waga krawędzi z v  do v 0 Uwzględniamy w sumie wagę ostatniej krawędzi cyklu
K05: Jeśli d H  ≥ d,
to idź do kroku K08
Jeśli znaleziony cykl jest gorszy od bieżącego, odrzucamy go
K06: d  ← d H Zapamiętujemy sumę wag cyklu
K07: Skopiuj stos S H do stosu S oraz sam cykl Hamiltona
K08: d H  ← d H  - waga krawędzi z v  do v 0 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 sąsiada u  wierzchołka v :
wykonuj
kroki 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:     d H  ←  d H + waga krawędzi z v  do u Obliczamy nową sumę wag krawędzi ścieżki
K14:     TSP ( n, graf, u, v o, d, d H, S, S H, visited  ) Wywołujemy rekurencyjnie poszukiwanie cyklu
K15:     d H  ←  d H  - waga krawędzi z v  do u Usuwamy wagę krawędzi z sumy
K16: visited [ v  ] ← false Zwalniamy bieżący wierzchołek
K17: S H.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 S H  
K02: d  ← ∞;  d H  ← 0 Początkową sumę ustawiamy jako największą z możliwych
K03: TSP ( v 0  ) 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.


Przykładowe programy

Uwaga:

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.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):
obrazek 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
Pascal
// 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.
C++
// 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;
}
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:
    obrazek
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
  
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.