algorytm.org

Cykl Hamiltona

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Cykl Hamiltona
Ocena użytkowników:***** / 25
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 16 sierpnia 2005 19:38

Graf posiada cykl Hamiltona, jeśli istnieje w nim cykl (droga, która zaczyna się i kończy w tym samym wierzchołku), który zawiera każdy wierzchołek dokładnie raz. Algorytm znajdujący cykl Hamiltona w grafie jest znacznie bardziej skomplikowany, niż w przypadku cyklu Eulera. Nie istnieje żaden algorytm rozwiązujący ten problem w czasie wielomianowym, algorytm należy więc do klasy NP-zupełnych.
Graf z cyklem Hamiltona
Przykładowy cykl: 1,2,6,5,3,4,1 lub 1,5,6,2,4,3,1

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 sierpnia 2012 20:43
Komentarze
photo
+7 # Krzysiek K 2012-06-15 08:34
"Nie istnieje żaden algorytm rozwiązujący ten problem w czasie wielomianowym, algorytm należy więc do klasy NP-zupełnych". Nie jest to prawdą, ponieważ nie wiemy czy P=NP. To, że jest NP-zupełny wynika z tego, iż możemy znaleźć świadka dla tego problemu obliczalnego w czasie wykładniczym, oraz że ten problem redukuje się do dowolnego problemu NP-zupełnego ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz