[Algorytmy] Cykle hamiltona w grafie skierowanym

MathNoob · Post autor: **MathNoob** » 18 maja 2012, o 22:36

Witam,
potrzebuję algorytmu o złożoności \(\displaystyle{ n!}\) (więc najprostsza wersja) do wyszukiwania cykli Hamiltona w grafie skierowanym. Najlepiej w postaci pseudokodu. Pomoże ktoś ?

bartek118 · Post autor: **bartek118** » 19 maja 2012, o 08:30

Po prostu robisz wszystkie permutacje wierzchołków i sprawdzasz, czy któraś nie jest cyklem Hamiltona

MathNoob · Post autor: **MathNoob** » 19 maja 2012, o 15:16

Tyle wiem, tylko jak to zapisać ; )

Katana1 · Post autor: **Katana1** » 26 maja 2015, o 16:15

Odświeżam. Może ktoś podrzuci jakiś uproszczony pseudokod chociaż?

Pozdrawiam

bartek118 · Post autor: **bartek118** » 26 maja 2015, o 16:20

W czym problem? Permutacje generuje się rekurencyjnie:

Kod: Zaznacz cały

perm(k)
   if k==1
      print P
   else
      for i=1 to k do
         swap (P[i], P[k])
         perm(k-1)
         swap (P[i], P[k])

Wywołanie perm(n) wypisze wszystkie \(\displaystyle{ n}\)-elementowe permutacje.

Teraz sprawdzamy każdą, czy jest po kolei czy jest cyklem Hamiltona; trywialny hint: wystarczy sprawdzić, że kolejne wygenerowane krawędzie istnieją.