Tengo un problema en el que tengo un gráfico simétrico y quiero encontrar la ruta más corta que visite cada nodo al menos una vez (no exactamente una vez).
Para resolver este problema, he descubierto que podemos calcular los caminos y pesos más cortos ( , ) entre todos los pares de nodos en el gráfico y luego construya un nuevo gráfico que tenga un borde entre el nodo i y j con peso y etiqueta . Luego podemos ejecutar un solucionador de TSP normal en este gráfico y obtener la ruta. Finalmente, esta ruta se expande usando el etiquetas en los bordes.
Tengo dos preguntas. 1) Al encontrar los caminos más cortos entre todos los pares de nodos, es posible que existan dos caminos entre los nodos i y j dando el mismo peso mínimo. Al volver a expandir la solución del solucionador TSP, debemos elegir cuál es la correcta. ¿Significa esto que debo minimizar todas las combinaciones posibles de estos caminos? Por ejemplo, si tengo 2 caminos entre AB y 3 caminos entre CD, ¿necesito probar las 6 combinaciones posibles?
2) Si asumimos un gráfico asimétrico en lugar de uno simétrico, ¿se puede resolver este problema siguiendo las técnicas de conversión que se dan aquí https://en.wikipedia.org/wiki/Travelling_salesman_problem#Asymmetric_TSP ? ¿Hay mejores métodos para hacer esto (ya que ahora tenemos que resolver un problema de 2N nodos frente al problema original de N nodos)?
La discusión adicional con otra persona sobre esto me hace sentir que la Pregunta 1 está resuelta. De hecho, puedo elegir cualquiera de los caminos, ya que todos tendrán el mismo peso y no afectarán la respuesta. Me preocupaba que una ruta no condujera a visitar todos los nodos mientras que otra lo haría, sin embargo, esta posibilidad se elimina porque ya ejecutamos TSP en el gráfico modificado; por ejemplo, todos los nodos en el gráfico ya están en la ruta.
Todavía estoy interesado en la segunda pregunta.
matemáticas duras