Qual è l'algoritmo di programmazione dinamica per la ricerca di un ciclo hamiltoniano in un grafo?

Question

Qual è l'algoritmo di programmazione dinamica per la ricerca di un ciclo hamiltoniano in un grafo non orientato? Ho visto da qualche parte che esiste un algoritmo con il tempo O(n.2^n) complessità.

Answer 1

V'è infatti un O (n2 ⁿ ) algoritmo di programmazione dinamica per la ricerca di cicli Hamiltoniani. L'idea, che è di carattere generale che può ridurre molti O (n!) Backtracking approcci O (n ² 2 ⁿ ) o O (n2 ⁿ ) (al costo di usare più memoria), è da considerare sottoproblemi che sono sets con "endpoint" specificati .

Qui, dal momento che si vuole un ciclo, si può iniziare in qualsiasi vertice. Quindi fissare uno, chiamare x. I sottoproblemi sarebbero: “? Per un dato S set e un v vertice in S, c'è un percorso a partire da x e da tutti i vertici di S, termina a v” Chiamare questo, diciamo, poss[S][v]

Come con la maggior parte dei problemi di programmazione dinamica, una volta che si definiscono i sottoproblemi il resto è ovvio: Loop su tutto il 2 ⁿ imposta S di vertici in qualsiasi ordine "crescente", e per ogni v in ogni tali S, è possibile calcolare poss[S][v] come:

  

poss [S] [v] = (esiste qualche u in S tale che poss [S- {v}] [u] è True ed esiste un u->v bordo)

Infine, c'è un ciclo hamiltoniano se e solo se v'è una v vertice tale che un v->x bordo esiste ed poss[S][v] è True, dove S è l'insieme di tutti i vertici (diversi x, a seconda di come è stata definita esso).

Se si desidera che il ciclo Hamiltoniano attuale invece di decidere se ne esiste o no, fanno negozio poss[S][v] la u reale che ha permesso invece di True o False; in questo modo è possibile risalire un sentiero alla fine.

Answer 2

Non riesco a strappare quel particolare algoritmo, ma c'è di più cicli hamiltoniani su La hamiltoniana pagina di quello che sarà probabilmente mai bisogno. :)

  

Questa pagina vuole essere un   elenco completo dei documenti,   codice sorgente, preprints, tecnico   relazioni, ecc, disponibili sul   Internet sul ciclo di Hamilton   e problemi di percorso di Hamilton, nonché   come alcuni problemi associati.

( URL originale, attualmente 404 ), (< a href = "http://web.archive.org/web/20100324030526/http://alife.ccp14.ac.uk/memetic/~moscato/Hamilton.html" rel = "nofollow noreferrer"> Internet Archive )