Problema del percorso hamiltoniano
Ci sono n! diverse sequenze di vertici che potrebbero essere percorsi hamiltoniani in un dato grafo a n vertici (e lo sono, in un grafo completo), quindi un algoritmo di ricerca a forza bruta che verifica tutte le possibili sequenze sarebbe molto lento.Un primo algoritmo esatto per trovare un ciclo hamiltoniano su un grafico diretto era l’algoritmo enumerativo di Martello. Una procedura di ricerca di Frank Rubin divide i bordi del grafo in tre classi: quelli che devono essere nel percorso, quelli che non possono essere nel percorso e gli indecisi. Mentre la ricerca procede, un insieme di regole decisionali classifica i bordi indecisi, e determina se fermarsi o continuare la ricerca. L’algoritmo divide il grafico in componenti che possono essere risolti separatamente. Inoltre, un algoritmo di programmazione dinamica di Bellman, Held e Karp può essere usato per risolvere il problema in tempo O(n2 2n). In questo metodo, si determina, per ogni insieme S di vertici e ogni vertice v in S, se esiste un percorso che copre esattamente i vertici in S e termina a v. Per ogni scelta di S e v, un percorso esiste per (S,v) se e solo se v ha un vicino w tale che esiste un percorso per (S – v,w), che può essere cercato dalle informazioni già calcolate nel programma dinamico.
Andreas Björklund ha fornito un approccio alternativo utilizzando il principio di inclusione-esclusione per ridurre il problema del conteggio del numero di cicli hamiltoniani a un problema di conteggio più semplice, quello del conteggio delle coperture dei cicli, che può essere risolto calcolando alcuni determinanti di matrice. Usando questo metodo, ha mostrato come risolvere il problema dei cicli hamiltoniani in grafi arbitrari a n vertici con un algoritmo Monte Carlo in tempo O(1.657n); per i grafi bipartiti questo algoritmo può essere ulteriormente migliorato fino a tempo o(1.415n).
Per i grafi di massimo grado tre, un’attenta ricerca backtracking può trovare un ciclo hamiltoniano (se esiste) in tempo O(1. 251n).251n).
I percorsi e i cicli hamiltoniani possono essere trovati usando un risolutore SAT.
A causa della difficoltà di risolvere i problemi dei percorsi e dei cicli hamiltoniani sui computer convenzionali, essi sono stati studiati anche in modelli di calcolo non convenzionali. Per esempio, Leonard Adleman ha dimostrato che il problema del percorso hamiltoniano può essere risolto usando un computer DNA. Sfruttando il parallelismo inerente alle reazioni chimiche, il problema può essere risolto usando un numero di passi di reazione chimica lineare nel numero di vertici del grafico; tuttavia, richiede un numero fattoriale di molecole di DNA per partecipare alla reazione.
È stata proposta anche una soluzione ottica al problema hamiltoniano. L’idea è quella di creare una struttura simile a un grafo fatta di cavi ottici e divisori di fascio che vengono attraversati dalla luce per costruire una soluzione al problema. Il punto debole di questo approccio è la quantità di energia richiesta che è esponenziale nel numero di nodi.