El uso de viajante de comercio Solver para decidir Camino hamiltoniano

Question

Esto es para un proyecto en el que se me pide que aplicar una heurística para el problema de optimización viajar vendedor y también el camino o decisión ciclo de Hamilton problema. No necesito ayuda con la aplicación en sí, pero tiene alguna duda sobre la dirección Voy a entrar.

Ya tengo una heurística TSP basado en un algoritmo genético: asume una gráfica completa, comienza con un conjunto de soluciones al azar como una población y trabaja para mejorar la población por varias generaciones. ¿Puedo usarlo para resolver los problemas de ruta o ciclo de Hamilton? En lugar de optimización para obtener la ruta más corta, sólo quiero comprobar si hay un camino.

Ahora, cualquier grafo completo tendrá un camino de Hamilton en el mismo, por lo que la heurística TSP tendría que extenderse a cualquier gráfico. Esto podría hacerse mediante el establecimiento de los bordes a un valor infinito si no hay un camino entre dos ciudades, y devolver el primer camino que es un camino de Hamilton válida.

Es que la forma correcta de acercarse a ella? O debería utilizar una heurística para el camino de Hamilton diferente? Mi principal preocupación es si se trata de un enfoque viable ya que puedo ser algo seguro de que la TSP optimización funciona (porque se empieza con soluciones y mejorar ellos) pero no si un partido decisivo camino de Hamilton encontraría cualquier ruta en un número fijo de generaciones.

Asumo que el mejor enfoque sería probar yo mismo, pero estoy limitado por el tiempo y pensé en preguntar antes de ir por este camino ... (que pude encontrar una heurística diferente para camino de Hamilton en su lugar)

Answer 1

No sé si alguna vez tiene una respuesta a esto. El truco sencillo es añadir un punto ficticio que tiene una distancia de cero a todos los demás puntos. Resolver el TSP y deshacerse del punto ficticio - lo que queda es el camino hamiltoniano. Simple!

Answer 2

Ambos son problemas NP completos, por lo que por definición se puede convertir la entrada y utilizar el mismo algoritmo; -)

Pero la idea básica debería funcionar. Por supuesto, es posible que necesite cambiar la generación de nuevos caminos y los criterios de éxito.

EDIT: Por cierto: Hay una sugerencia para un algoritmo aleatorio: http://en.wikipedia.org/wiki/Hamiltonian_path_problem