Dato un grafo G = (V, E) dobbiamo trovare il circuito hamiltoniano usando l’approccio Backtracking. Iniziamo la nostra ricerca da un qualsiasi vertice arbitrario, diciamo “a”. Questo vertice ‘a’ diventa la radice del nostro albero implicito. Il primo elemento della nostra soluzione parziale è il primo vertice intermedio del Ciclo Hamiltoniano che deve essere costruito. Il prossimo vertice adiacente è selezionato per ordine alfabetico. Se in qualsiasi fase qualsiasi vertice arbitrario fa un ciclo con qualsiasi altro vertice diverso dal vertice ‘a’, allora diciamo che è stato raggiunto un vicolo cieco. In questo caso, si fa un passo indietro, e di nuovo la ricerca inizia selezionando un altro vertice e facendo il backtracking dell’elemento dal parziale; la soluzione deve essere rimossa. La ricerca con backtracking ha successo se si ottiene un ciclo hamiltoniano.
Esempio: Consideriamo un grafo G = (V, E) mostrato in fig. dobbiamo trovare un circuito hamiltoniano usando il metodo Backtracking.
Soluzione: In primo luogo, iniziamo la nostra ricerca con il vertice ‘a’. Questo vertice ‘a’ diventa la radice del nostro albero implicito.
In seguito, scegliamo il vertice ‘b’ adiacente ad ‘a’ perché viene prima in ordine lessicografico (b, c, d).
Poi scegliamo il vertice ‘c’ adiacente a ‘b.’
Poi scegliamo ‘d’ adiacente a ‘c.’
Prossimo, selezioniamo ‘e’ adiacente a ‘d.’
Prossimo, selezioniamo il vertice ‘f’ adiacente a ‘e. Il vertice adiacente a ‘f’ è d ed e, ma hanno già visitato. Così, otteniamo il vicolo cieco, e facciamo un passo indietro e rimuoviamo il vertice ‘f’ dalla soluzione parziale.
Dal backtracking, il vertice adiacente a ‘e’ è b, c, d, e f da cui il vertice ‘f’ è già stato controllato, e b, c, d hanno già visitato. Quindi, di nuovo facciamo un passo indietro. Ora, i vertici adiacenti a d sono e, f da cui e è già stato controllato, e adiacenti a ‘f’ sono d ed e. Se il vertice ‘e’, rivisitato li otteniamo uno stato morto. Quindi di nuovo facciamo un passo indietro.
Ora, adiacente a c è ‘e’ e adiacente a ‘e’ è ‘f’ e adiacente a ‘f’ è ‘d’ e adiacente a ‘d’ è ‘a’. Qui, otteniamo il Ciclo Hamiltoniano in quanto tutti i vertici diversi dal vertice iniziale ‘a’ sono visitati solo una volta. (a – b – c – e – f -d – a).
Di nuovo a ritroso
qui abbiamo generato un circuito hamiltoniano, ma un altro circuito hamiltoniano può essere ottenuto anche considerando un altro vertice.