Utilizzando commesso viaggiatore Risolutore per decidere hamiltoniana Path

Question

Questo è per un progetto in cui mi viene chiesto di attuare un'euristica per il viaggiare problema di ottimizzazione commesso e anche l'Hamiltoniana percorso o la decisione ciclo problema. Non ho bisogno di aiuto con l'attuazione in sé, ma hanno una domanda sulla direzione sto andando in.

Ho già un euristica TSP sulla base di un algoritmo genetico: assume un grafico completo, inizia con una serie di soluzioni casuali come una popolazione, e lavora per migliorare la popolazione per un certo numero di generazioni. Posso anche usare per risolvere i problemi di percorso o di ciclo hamiltoniano? Invece di ottimizzare per ottenere il percorso più breve, voglio solo verificare se v'è un percorso.

Ora, qualsiasi grafico completo avrà un percorso hamiltoniano in esso, in modo che l'euristica TSP dovrebbe essere esteso a tutti i grafici. Ciò potrebbe essere fatto impostando i bordi per un valore infinito, se non v'è alcun percorso tra due città, e restituendo il primo percorso che è un percorso hamiltoniano valido.

E 'questo il modo giusto per affrontarla? O devo usare un'euristica diversa per il percorso hamiltoniano? La mia preoccupazione principale è che si tratti di un approccio praticabile dato che posso essere un po 'in modo che l'ottimizzazione TSP funziona (perché si inizia con le soluzioni e migliorare loro), ma non se un percorso decisore hamiltoniano potrebbe trovare qualsiasi percorso in un numero fisso di generazioni.

Suppongo che l'approccio migliore sarebbe quello di provare io stesso, ma sono costretto dal tempo e ho pensato di chiedere prima di andare su questa strada ... (ho potuto trovare un euristica diversa per il percorso hamiltoniano invece)

Answer 1

Non so se avete mai avuto una risposta a questa. Il semplice trucco è quello di aggiungere un punto fittizio che ha una distanza di zero a tutti gli altri punti. Risolvere il TSP e sbarazzarsi del punto manichino - ciò che rimane è il cammino hamiltoniano. Semplice!

Answer 2

Entrambi sono problemi NP completi, quindi, per definizione, è possibile convertire l'input e utilizzare lo stesso algoritmo; -)

Ma l'idea di base dovrebbe funzionare. Naturalmente potrebbe essere necessario cambiare la generazione di nuovi percorsi e dei criteri di successo.

EDIT: BTW: C'è un suggerimento per un algoritmo randomizzato: http://en.wikipedia.org/wiki/Hamiltonian_path_problem