Znajdowanie cyklu lub ścieżki Hamiltona


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źć cykl lub ścieżkę Hamiltona, jeśli istnieją.

 

 

Sir William Rowan Hamilton

Cykl Hamiltona:
A B H I Q P G F O T S R K J C D L M N E A

Ścieżka Hamiltona (ang. Hamiltonian path) jest taką ścieżką w grafie, która odwiedza każdy jego wierzchołek dokładnie jeden raz.

Cykl Hamiltona (ang. Hamiltonian cycle) jest cyklem, który odwiedza każdy wierzchołek grafu dokładnie jeden raz (za wyjątkiem pierwszego, od którego cykl się zaczyna i w którym się kończy).

Graf zawierający ścieżkę lub cykl Hamiltona nazywamy grafem hamiltonowskim (ang. Hamiltonian graph).

Chociaż brzmi to dosyć prosto, to jednak znalezienie cyklu lub ścieżki Hamiltona w grafie jest bardzo trudne obliczeniowo. Problem ten zalicza się to tzw. problemów NP zupełnych, co oznacza, że dla dużej liczby wierzchołków jest on praktycznie nierozwiązywalny w sensownym czasie (o ile nie masz do dyspozycji całych milionów, miliardów lub więcej lat). Jeśli udałoby ci się rozwiązać znajdowanie cykli lub ścieżek Hamiltona w czasie wielomianowym, to prawdopodobnie otrzymałbyś Nagrodę Nobla z matematyki. Rozwiązania takiego wciąż brak i prawdopodobnie nie istnieje.

Aby graf mógł posiadać cykl Hamiltona, musi być spójny – jest to oczywiste. W grafie niespójnym istnieją wierzchołki, pomiędzy którymi brak ścieżki, zatem nie można ich odwiedzić.

Można podać prosty algorytm rekurencyjny znajdowania wszystkich cykli i ścieżek Hamiltona, jednakże posiada on złożoność O(n!), co czyni go zupełnie niepraktycznym dla większych grafów (zawierających powyżej 30 wierzchołków). Jednakże dla tych małych można go stosować w celach dydaktycznych. Zasada działania naszego algorytmu jest następująca:

Za pomocą odpowiednio zmodyfikowanej procedury DFS przeglądamy graf począwszy od wierzchołka nr 0 (wybór wierzchołka nie ma znaczenia, ponieważ możliwa ścieżka lub cykl Hamiltona musi przechodzić przez wszystkie wierzchołki grafu). Przetwarzany wierzchołek umieszczamy na stosie. Następnie sprawdzamy, czy stos zawiera n wierzchołków. Jeśli tak, to otrzymaliśmy ścieżkę Hamiltona. W takim przypadku sprawdzamy, czy ostatni wierzchołek ścieżki jest połączony krawędzią z wierzchołkiem nr 0. Jeśli tak, to ścieżka tworzy cykl Hamiltona - wyprowadzamy jej zawartość ze stosu (dla cyklu dodatkowo dodajemy na końcu wierzchołek 0), usuwamy ostatni wierzchołek ze stosu i wycofujemy się na wyższy poziom rekurencji, gdzie będą rozważone inne ścieżki lub cykle Hamiltona.

Jeśli stos nie zawiera n wierzchołków, to rekurencyjnie wywołujemy procedurę DFS dla wszystkich nieodwiedzonych sąsiadów. Wierzchołek usuwamy ze stosu i kasujemy informację o jego odwiedzeniu, po czym wycofujemy się na wyższy poziom rekurencji.

 

Powyższy algorytm produkuje ścieżki i cykle Hamiltona w kierunku odwrotnym do ich przebywania przez DFS. Dla grafu nieskierowanego nie ma to znaczenia. W grafie skierowanym należy tę kolejność odwrócić. Stos można w prosty sposób zrealizować w dynamicznej tablicy n elementowej. Wtedy bez problemu da się odczytywać wierzchołki cyklu w kolejności ich przebywania.

 

Algorytm wyszukiwania ścieżek i cykli Hamiltona

Funkcja rekurencyjna DFSHamilton(n,graf,v,visited,S)
Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v  –  bieżący wierzchołek grafu, v symbol C
visited  –  n elementowa tablica odwiedzin
S  –  stos wierzchołków
Wyjście:
Wszystkie cykle i ścieżki Hamiltona w grafie
Elementy pomocnicze:
test    zmienna logiczna do testowania cyklu lub ścieżki Hamiltona
u    wierzchołek grafu, u symbol C
Lista kroków:
K01: S.push(v) ; umieszczamy v na stosie
K02: Jeśli S zawiera mniej niż n wierzchołków, to idź do K10 ; mamy ścieżkę Hamiltona?
K03: test ← false ; zakładamy brak cyklu Hamiltona
K04: Dla każdego sąsiada u wierzchołka v, wykonuj K05 ; przeglądamy sąsiadów v
K05:     Jeśli u = 0, to test ← true i idź do K06  
K06: Jeśli test = true, to pisz "Hamiltonian Cycle :"
inaczej                  pisz "Hamiltonian Path : "
 
K07: Pisz zawartość S bez usuwania danych z S  
K08: Jeśli test = true, to pisz 0 ; dla cyklu dopisujemy wierzchołek startowy
K09: Idź do K14  
K10: visited[v] ← true ; oznaczamy wierzchołek jako odwiedzony
K11: Dla każdego sąsiada u wierzchołka v, wykonuj K12 ; przeglądamy sąsiadów wierzchołka v
K12:     Jeśli visited[u] = false, to DFSHamilton(n,graf,u,visited,S) ; dla sąsiadów nieodwiedzonych wykonujemy wywołanie rekurencyjne
K13: visited[v] ← false ; wycofujemy się z wierzchołka v
K14: S.pop() ; wierzchołek v usuwamy ze stosu
K15: Zakończ  

 

Funkcję należy wywołać z pustym stosem S i wyzerowaną tablicą visited jako DFSHamilton(n,graf,0,visited,S).

 

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.

 

Program odczytuje definicję grafu nieskierowanego i wyszukuje w nim wszystkie cykle oraz ścieżki Hamiltona. Wyniki są odpowiednio wyświetlane w oknie konsoli. 

Przykładowe dane dla programu:

Graf z cyklami i ścieżkami Hamiltona

symbol

8 13
0 1 0 3 0 4
1 2 1 4 1 5
2 3 2 6
3 5 3 6
4 7
5 7
6 7

 

Lazarus
// Wyszukiwanie cykli i ścieżek Hamiltona
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program hamilton;

// Typy danych

type
  PslistEl = ^slistEl;          // Wskaźnik elementów listy
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

// Zmienne globalne

var
  m,n  : integer;               // Liczba krawędzi i wierzchołków
  graf : array of PslistEl;     // Tablica list sąsiedztwa
  S    : array of integer;      // Tablica-stos
  sptr : integer;               // Wskaźnik stosu
  visited : array of boolean;   // Tablica odwiedzin

// Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
// v - wierzchołek bieżący
//--------------------------------------------------------------
procedure DFSHamilton(v : integer);
var
  i    : integer;
  test : boolean;
  p    : PslistEl;
begin
  S[sptr] := v;                 // Wierzchołek v na stos
  inc(sptr);
  if sptr < n then              // Jest ścieżka Hamiltona?
  begin
    visited[v] := true;         // Nie ma, odwiedzamy v
    p := graf[v];
    while p <> nil do           // Przeglądamy sąsiadów v
    begin
      if not visited[p^.v] then DFSHamilton(p^.v); // Wywołanie rekurencyjne
      p := p^.next;             // Następny sąsiad
    end;
    visited[v] := false;        // Wycofujemy się z v
  end
  else                          // Jest ścieżka Hamiltona
  begin
    test := false;              // Zakładamy brak cyklu
    p := graf[v];               // Przeglądamy sąsiadów
    while p <> nil do
    begin
      if p^.v = 0 then          // Jeśli sąsiadem jest wierzchołek 0,
      begin
        test := true;           // to mamy cykl
        break;
      end;
      p := p^.next;             // Następny sąsiad
    end;
    if test then write('Hamiltonian Cycle :')
    else         write('Hamiltonian Path  :');
    for i := 0 to sptr - 1 do   // Wypisujemy ścieżkę Hamiltona
      write(S[i]:3);
    if test then write(0:3);    // Dla cyklu dopisujemy wierzchołek startowy
    writeln;
  end;
  dec(sptr);                    // Wierzchołek v usuwamy ze stosu
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i,v1,v2 : integer;
  p,r     : PslistEl;
begin
  read(n,m);                    // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength(graf,n);
  SetLength(visited,n);
  for i := 0 to n - 1 do
  begin
    graf[i]    := nil;
    visited[i] := false;
  end;
  SetLength(S,n);
  sptr := 0;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m - 1 do
  begin
    read(v1,v2);
    new(p);
    p^.v := v2;
    p^.next := graf[v1];
    graf[v1] := p;
    new(p);
    p^.v := v1;
    p^.next := graf[v2];
    graf[v2] := p;
  end;

  writeln;

  // Wyświetlamy ścieżki i cykle Hamiltona

  DFSHamilton(0);

  // Usuwamy zmienne dynamiczne

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

  for i := 0 to n - 1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(graf,0);
end.
Code::Blocks
// Wyszukiwanie cykli i ścieżek Hamiltona
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

struct slistEl
{
  slistEl * next;
  int v;
};

// Zmienne globalne

int m,n;                        // Liczba krawędzi i wierzchołków
slistEl **graf;                 // Tablica list sąsiedztwa
int *S;                         // Tablica-stos
int sptr;                       // Wskaźnik stosu
bool *visited;                  // Tablica odwiedzin

// Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
// v - wierzchołek bieżący
//--------------------------------------------------------------
void DFSHamilton(int v)
{
  int i;
  bool test;
  slistEl *p;

  S[sptr++] = v;                // Wierzchołek v na stos
  if(sptr < n)                  // Jest ścieżka Hamiltona?
  {
    visited[v] = true;          // Nie ma, odwiedzamy v
    for(p = graf[v]; p; p = p->next) // Przeglądamy sąsiadów v
      if(!visited[p->v]) DFSHamilton(p->v); // Wywołanie rekurencyjne
    visited[v] = false;         // Wycofujemy się z v
  }
  else                          // Jest ścieżka Hamiltona
  {
    test = false;               // Zakładamy brak cyklu
    for(p = graf[v]; p; p = p->next) // Przeglądamy sąsiadów
      if(!(p->v))               // Jeśli sąsiadem jest wierzchołek 0,
      {
        test = true;            // to mamy cykl
        break;
      }

    if(test) cout << "Hamiltonian Cycle :";
    else     cout << "Hamiltonian Path  :";

    for(i = 0; i < sptr; i++)   // Wypisujemy ścieżkę Hamiltona
      cout << setw(3) << S[i];
    if(test) cout << setw(3) << 0; // Dla cyklu dopisujemy wierzchołek startowy
    cout << endl;
  }
  sptr--;                       // Wierzchołek v usuwamy ze stosu
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i,v1,v2;
  slistEl *p,*r;

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

  // Tworzymy tablice dynamiczne

  graf    = new slistEl * [n];
  visited = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf[i]    = NULL;
    visited[i] = false;
  }
  S = new int [n];
  sptr = 0;

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    p = new slistEl;
    p->v = v2;
    p->next = graf[v1];
    graf[v1] = p;
    p = new slistEl;
    p->v = v1;
    p->next = graf[v2];
    graf[v2] = p;
  }

  cout << endl;

  // Wyświetlamy ścieżki i cykle Hamiltona

  DFSHamilton(0);

  // Usuwamy zmienne dynamiczne

  delete [] visited;
  delete [] S;

  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;

  return 0;
}
Free Basic
' Wyszukiwanie cykli i ścieżek Hamiltona
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy danych

Type slistEl
  Next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer m,n       ' Liczba krawędzi i wierzchołków
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim Shared As Integer Ptr S     ' Tablica-stos
Dim Shared As Integer sptr      ' Wskaźnik stosu
Dim Shared As Byte Ptr visited  ' Tablica odwiedzin

' Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
' v - wierzchołek bieżący
'--------------------------------------------------------------
Sub DFSHamilton(ByVal v As Integer)

  Dim As Integer i,test
  Dim As slistEl Ptr p

  S[sptr] = v                   ' Wierzchołek v na stos
  sptr += 1
  If sptr < n Then              ' Jest ścieżka Hamiltona?
    visited[v] = 1              ' Nie ma, odwiedzamy v
    p = graf[v]
    While p                     ' Przeglądamy sąsiadów v
      If visited[p->v] = 0 Then DFSHamilton(p->v) ' Wywołanie rekurencyjne
      p = p->Next               ' Następny sąsiad
    Wend
    visited[v] = 0              ' Wycofujemy się z v
  Else                          ' Jest ścieżka Hamiltona
    test = 0                    ' Zakładamy brak cyklu
    p = graf[v]
    While p                     ' Przeglądamy sąsiadów
      If p->v = 0 Then          ' Jeśli sąsiadem jest wierzchołek 0,
        test = 1                ' to mamy cykl
        Exit While
      End If
      p = p->Next               ' Następny sąsiad
    Wend
    
    If test = 1 then
    	Print "Hamiltonian Cycle :";
    Else
      Print "Hamiltonian Path  :";
    End If
    
    For i = 0 To sptr - 1       ' Wypisujemy ścieżkę Hamiltona
      Print Using "###";S[i];
    Next
    
    If test = 1 Then Print Using "###";0; ' Dla cyklu dopisujemy wierzchołek startowy
    Print
  End if
  sptr -= 1                     ' Wierzchołek v usuwamy ze stosu
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i,v1,v2
Dim As slistEl Ptr p,r

Open Cons For Input As #1

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

' Tworzymy tablice dynamiczne

graf    = New slistEl Ptr [n]
visited = New Byte [n]
For i = 0 To n - 1
  graf[i]    = 0
  visited[i] = 0
Next
S = New Integer [n]
sptr = 0

' Odczytujemy definicje krawędzi grafu

For i = 0 To m - 1
  Input #1,v1,v2
  p = New slistEl
  p->v = v2
  p->next = graf[v1]
  graf[v1] = p
  p = New slistEl
  p->v = v1
  p->next = graf[v2]
  graf[v2] = p
Next

Print

' Wyświetlamy ścieżki i cykle Hamiltona

DFSHamilton(0)

' Usuwamy zmienne dynamiczne

Delete [] visited
Delete [] S

For i = 0 To n - 1
  p = graf[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf

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

Hamiltonian Path  :  0  4  7  6  3  5  1  2
Hamiltonian Path  :  0  4  7  6  3  2  1  5
Hamiltonian Cycle :  0  4  7  6  2  3  5  1  0
Hamiltonian Cycle :  0  4  7  6  2  1  5  3  0
Hamiltonian Cycle :  0  4  7  5  3  6  2  1  0
Hamiltonian Cycle :  0  4  7  5  1  2  6  3  0
Hamiltonian Path  :  0  4  7  5  1  2  3  6
Hamiltonian Path  :  0  4  1  5  7  6  3  2
Hamiltonian Cycle :  0  4  1  5  7  6  2  3  0
Hamiltonian Path  :  0  4  1  5  3  2  6  7
Hamiltonian Cycle :  0  4  1  2  6  7  5  3  0
Hamiltonian Path  :  0  4  1  2  6  3  5  7
Hamiltonian Path  :  0  4  1  2  3  6  7  5
Hamiltonian Path  :  0  4  1  2  3  5  7  6
Hamiltonian Cycle :  0  3  6  2  1  5  7  4  0
Hamiltonian Path  :  0  3  6  2  1  4  7  5
Hamiltonian Cycle :  0  3  5  7  6  2  1  4  0
Hamiltonian Path  :  0  3  5  7  4  1  2  6
Hamiltonian Path  :  0  3  5  1  4  7  6  2
Hamiltonian Cycle :  0  3  5  1  2  6  7  4  0
Hamiltonian Cycle :  0  3  2  6  7  5  1  4  0
Hamiltonian Path  :  0  3  2  6  7  4  1  5
Hamiltonian Cycle :  0  1  5  3  2  6  7  4  0
Hamiltonian Path  :  0  1  4  7  6  2  3  5
Hamiltonian Path  :  0  1  4  7  5  3  6  2
Hamiltonian Path  :  0  1  4  7  5  3  2  6
Hamiltonian Cycle :  0  1  2  6  3  5  7  4  0

 

Zadania dla ambitnych

Zwróć uwagę, że dla grafu nieskierowanego liczba cykli Hamiltona jest zawsze parzysta. Połowa z nich to te same cykle, lecz przebywanie w odwrotnym kierunku. Np:

 

0  4  7  6  2  3  5  1  0
0  1  5  3  2  6  7  4  0

 

W grafie nieskierowanym cykle takie są traktowane jako ten sam cykl Hamiltona. Zatem w naszym przykładowym grafie jest tylko 6 różnych cyklów Hamiltona. Zastanów się, czy można tak zmodyfikować nasz algorytm, aby nie pokazywał cykli lustrzanych.

 

Zastanów się, jak zmodyfikować algorytm, aby wyszukiwał tylko pierwszy cykl Hamiltona.

 



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.