algorithm - viajante - ¿Cuál es el nombre del problema para el problema del vendedor viajero(TSP) sin considerar volver al punto de partida?
problema del viajante backtracking (2)
Me gustaría saber cuál es el nombre del problema para TSP sin considerar la forma de volver al punto de partida y cuál es el algoritmo para resolver esto.
Busqué el problema del camino más corto, pero eso no es lo que estoy buscando, el problema solo encuentra el camino más corto desde los 2 puntos asignados. Pero lo que busco es el problema que damos n puntos e ingresamos solo 1 punto de partida. Luego, encuentra el camino más corto recorriendo todos los puntos exactamente una vez. (el punto final puede ser cualquier punto).
También examiné el problema de la ruta hamiltoniana, pero no parece resolver el problema definido, sino más bien encontrar si hay una ruta hamiltoniana o no.
Por favor sugiéreme, gracias!
He encontrado la respuesta a mi pregunta en este libro . Es lo mismo con el problema de cableado de la computadora que ocurre repetidamente en el diseño de las computadoras y otros sistemas digitales. El propósito es minimizar la longitud total del cable. Por lo tanto, es de hecho un camino de Hamilton de longitud mínima
Lo que sugiere el libro es crear un punto ficticio cuyas distancias a todos los demás puntos es 0. Por lo tanto, el problema se convierte en un TSP simétrico de la ciudad (n + 1). Después de resolver, simplemente elimine el punto ficticio y luego se resuelve la ruta Hamiltoniana de longitud mínima y podemos obtener la ruta TSP sin devolver el punto de inicio.
Si comprendo correctamente, desea encontrar la ruta más corta (que comienza desde algunos vértices) y atraviesa todos los nodos del gráfico sin visitar el mismo nodo dos veces. Un problema más simple, es el problema de la ruta hamiltoniana. Pregunta, como dijiste, si existe un camino así o no. Dado que el problema es NP-hard y es más fácil que su problema, resolver su problema es al menos NP-Hard. Bueno, eso no es cierto porque su problema no es un problema de decisión . Pero lo que sí dice es que casi podemos estar seguros de que no existe un algoritmo polinómico para su problema.
Se puede recurrir a la aproximación. Hay una aproximación bastante buena para la métrica TSP aquí: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP .