Utilizzo del Risolutore del commesso viaggiatore per decidere il percorso hamiltoniano

Question

Questo è per un progetto in cui mi viene chiesto di implementare un'euristica per il problema dell'ottimizzazione del commesso viaggiatore e anche per il problema dell'iter hamiltoniano o del ciclo. Non ho bisogno di aiuto per l'implementazione stessa, ma ho una domanda sulla direzione in cui sto andando.

Ho già un euristico TSP basato su un algoritmo genetico: assume un grafico completo, inizia con un set di soluzioni casuali come popolazione e lavora per migliorare la popolazione per un numero di generazioni. Posso usarlo anche per risolvere il percorso hamiltoniano oi problemi del ciclo? Invece di ottimizzare per ottenere il percorso più breve, voglio solo verificare se c'è un percorso.

Ora qualsiasi grafico completo avrà un percorso hamiltoniano, quindi l'euristica TSP dovrebbe essere estesa a qualsiasi grafico. Questo può essere fatto impostando i bordi su un valore infinito se non c'è alcun percorso tra due città e restituendo il primo percorso che è un percorso hamiltoniano valido.

È il modo giusto per avvicinarsi? O dovrei usare un'euristica diversa per il percorso hamiltoniano? La mia preoccupazione principale è se sia un approccio praticabile poiché posso essere un po 'sicuro che l'ottimizzazione del TSP funzioni (perché si iniziano con le soluzioni e le si migliorano), ma non se un decisore di percorso Hamiltoniano troverà un percorso in un numero fisso di generazioni.

Suppongo che l'approccio migliore sarebbe quello di testarlo da solo, ma sono limitato dal tempo e ho pensato di chiedere prima di percorrere questa rotta ... (Potrei trovare un'altra euristica per il percorso Hamiltoniano)

Answer 1

Non so se avete mai avuto una risposta a questa. Il semplice trucco consiste nell'aggiungere un punto fittizio che ha una distanza pari a zero per tutti gli altri punti. Risolvi il TSP e sbarazzati del punto fittizio: ciò che rimane è il Sentiero 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 modificare la generazione di nuovi percorsi e i criteri di successo.

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