ALG - Cykl Hamiltona

by NOWIESZ

Trochę o:

Cykl Hamiltona, to taki cykl w grafie, który zawiera wszystkie wierzchołki grafu, przy czym każdy dokładnie raz.
Problem znajdowania cyklu Hamiltona jest jednak znacznie trudniejszy niż w znajdowania cyklu Eulera. Nie istnieje algorytm działający w sensownym czasie, który potrafi znaleźć cykl Hamiltona w dowolnym grafie.

Opis algorytmu:

Żeby znaleźć cykl Hamiltona w grafie należy zapuścić rekurencję z nawrotami do znajdowania wszystkich cykli (bez powtarzających się wierzchołków), a po znalezieniu jakiegoś cyklu sprawdzamy czy zawiera wszystkie wierzchołki. Niektórym to już mówi wszystko, a tym którym nie mówi to tłumaczę dalej.
Zaczynamy szukać drogę w jakimkolwiek wierzchołku, nazwijmy go s. Załóżmy, że w pewnym momencie wykonywania algorytmu doszliśmy do wierzchołka v. Mamy zapamiętane wierzchołki "użyte" do przejścia drogą z s do v, z oboma tymi wierzchołkami włącznie (uwaga: możliwe, że w v znajdziemy się kilkakrotnie i za każdym razem dojdziemy tam inną drogą z s). Dalej przechodzimy z v rekurencyjnie do jego następników (albo sąsiadów w przypadku grafów nieskierowanych), ale tylko tych nieużytych (zaznaczając je jako już użyte). Gdy obejrzymy wszystkie następniki v i nic nam to nie da, to musimy wrócić (rekurencyjnie) oraz !odznaczyć! wierzchołek v, żeby w przyszłości można było ponownie przez niego przejść. Jeżeli w pewnym momencie z jakiegoś wierzchołka będie można przejść bezpośrednio do s to znaleźliśmy pewien cykl i musimy sprawdzić czy odwiedziliśmy wszystkie wierzchołki; jeśli tak to cykl jest hamiltonowski i możemy go wypisać, a jeśli nie to z powrotem i szukamy dalej.
Żeby móc sprawdzić czy znaleziony cykl jest hamiltonowskim wystarczy jedynie zliczać odwiedzone wierzchołki. Należy przy każdym zagłębieniu rekurencji zwiększyć jakiś licznik o 1, a przy powrocie zmniejszyć go o 1. Jeśli zrobimy cykl od s do s to jest on cyklem Hamiltona gdy licznik ma wartość równą liczbie wierzchołków w grafie (bo wtedy odwiedzone zostały wszystkie wierzchołki).

No to (pseudo)kod. Funkcja HamiltonCycle zwróci True jeżeli cykl Hamiltona zostanie znaleziony oraz w tablicy H znajdą się kolejne wierzchołki tego cyklu; w przeciwnym wypadku funkcja zwróci False.

  {
  N - liczba wierzcholkow
  D[1..N] - tablica logiczna odwiedzin wierzcholkow
  H[1..N] - tablica kolejnych wierzcholkow cyklu Hamiltona
  }

  function PathRec(v: Integer): Boolean;
  {fun. rekurencyjnego znajdowania cykli od s do s}
  begin
    D[v]:=True;   {zaznczanie wierzcholka jako uzyty}
    Inc(used);    {zwiekszenie liczby uzytych wierzcholkow}

    PathRec:=True;
    for i:=Successor(v) do    {petla po nastepnikach wierzch. v}
    begin
      if i=s then    {jesli zrobilismy cykl ...}
        if used=N then   {jesli do tego wszystkie wierzcholki uzyte}
        begin
          H[1]:=v;
          Exit;                        {wtedy wychodzi z wartoscia True}
        end;
      if not D[i] then   {jesli wierzch. i jest nieuzyty ...}
        if PathRec(i) then
        {przechodzimy rek. do wierzcholka i jesli znalezlismy tam cykl H. ...}
        begin
          H[No]:=v;        {wstawiamy kolejny wierzcholek do tablicy H}
          Inc(No);
          Exit;         {wychodzi z wartoscia True}
        end;
    end;

    PathRec:=False;   {nie tedy droga, trza zwrocic False}
    D[v]:=False;  {zaznczanie wierzcholka jako nieuzyty}
    Dec(used);    {zmniejszenie liczby uzytych wierzcholkow}
  end;

  function HamiltonCycle: Boolean;
  begin
    for i:=1 to N do
      D[i]:=False;    {oznaczamy wszystkie wierzcholki jako nieuzyte}

    used:=0;    {zmienna potrzebna do liczenia przebytych wierzcholkow}
    No:=2;    {zmienna potrzebna do wpisywania wierzcholkow cyklu do tablicy H}

    s:=1;   {wierzcholek startowy - calkowicie dowolny z przedzialu 1..N}
    HamiltonCycle:=PathRec(s);
  end;

Złożoność czasowa:

A tutaj niespodzianka. Algorytm by najmniej nie działa w czasie O(E).
Problem znajdowania cyklu Hamiltona w grafie jest NP-zupełny (w dodatku silnie NP-zupełny), co oznacza tyle, że nie istnieje algorytm rozwiązujący ten problem działający w czasie wielomianowym. I rzeczywiście - algorytm, który podałem działa pesymistycznie w czasie O(V!), co zalicza się do czasów wykładniczych (możliwe, że dla przeciętnych grafów działa to lepiej). Skutek tego jest straszny: dla grafów dwudziestoparowierzchołkowych (no, może trochę więcej - nie wiem) algorytm zacznie wymiękać czasowo.