Problem ścieżki hamiltonowskiej

Istnieje n! różnych sekwencji wierzchołków, które mogą być ścieżkami hamiltonowskimi w danym grafie n-werteksowym (i są, w grafie pełnym), więc algorytm wyszukiwania brute force, który testuje wszystkie możliwe sekwencje byłby bardzo wolny.Wczesnym dokładnym algorytmem znajdowania cyklu hamiltonowskiego na grafie skierowanym był enumeratywny algorytm Martello. Procedura wyszukiwania Franka Rubina dzieli krawędzie grafu na trzy klasy: te, które muszą być na ścieżce, te, które nie mogą być na ścieżce i niezdecydowane. W trakcie przeszukiwania, zestaw reguł decyzyjnych klasyfikuje niezdecydowane krawędzie i decyduje o tym, czy zatrzymać czy kontynuować przeszukiwanie. Algorytm dzieli graf na elementy, które mogą być rozwiązywane oddzielnie. Do rozwiązania problemu w czasie O(n2 2n) można również wykorzystać algorytm programowania dynamicznego Bellmana, Helda i Karpa. W tej metodzie, dla każdego zbioru S wierzchołków i każdego wierzchołka v w S, określamy, czy istnieje ścieżka, która pokrywa dokładnie wierzchołki w S i kończy się w v. Dla każdego wyboru S i v, ścieżka istnieje dla (S,v) wtedy i tylko wtedy, gdy v ma sąsiada w takiego, że istnieje ścieżka dla (S – v,w), która może być wyszukana z już obliczonych informacji w programie dynamicznym.

Andreas Björklund przedstawił alternatywne podejście wykorzystujące zasadę inkluzji-ekskluzji do zredukowania problemu liczenia liczby cykli Hamiltona do prostszego problemu liczenia pokryć cykli, który może być rozwiązany przez obliczenie pewnych wyznaczników macierzowych. Używając tej metody, pokazał jak rozwiązać problem cykli Hamiltona w dowolnych grafach n-werteksowych za pomocą algorytmu Monte Carlo w czasie O(1.657n); dla grafów dwudzielnych algorytm ten może być dalej ulepszony do czasu O(1.415n).

Dla grafów maksymalnego stopnia trzeciego, ostrożne przeszukiwanie backtrackingowe może znaleźć cykl Hamiltona (jeśli taki istnieje) w czasie O(1.251n).

Ścieżki i cykle hamiltonowskie mogą być znalezione przy użyciu SAT solver.

Z powodu trudności w rozwiązywaniu problemów ścieżek i cykli hamiltonowskich na konwencjonalnych komputerach, były one również badane w niekonwencjonalnych modelach obliczeń. Na przykład, Leonard Adleman pokazał, że problem ścieżki Hamiltona może być rozwiązany przy użyciu komputera DNA. Wykorzystując paralelizm właściwy reakcjom chemicznym, problem może być rozwiązany przy użyciu liczby kroków reakcji chemicznej liniowej w stosunku do liczby wierzchołków grafu; wymaga to jednak czynnikowej liczby cząsteczek DNA biorących udział w reakcji.

Zaproponowano również optyczne rozwiązanie problemu Hamiltona. Pomysł polega na stworzeniu grafopodobnej struktury z kabli optycznych i rozdzielaczy wiązek, które są przemierzane przez światło w celu skonstruowania rozwiązania problemu. Słabym punktem tego podejścia jest wymagana ilość energii, która jest wykładnicza w liczbie węzłów.