Dado que se ha dedicado tanto tiempo y esfuerzo a optimizar los solucionadores de TSP, el camino de menor resistencia probablemente sea tratar de convertir su problema en una instancia de TSP. Una forma de hacerlo es configurarlo como una instancia TSP dirigida con todos los nodos, excepto los nodos iniciales y finales conectados a los otros nodos con sus distancias reales, y el nodo inicial conectado a todos los nodos en la dirección hacia adelante, el nodo final conectado a todos los nodos en la dirección inversa, y el nodo final conectado al nodo inicial en la dirección hacia adelante, y luego convierta este problema en una instancia del TSP no dirigido y resuélvalo con una herramienta como Concorde:
Concorde Home
La construcción para pasar de dirigida a no dirigida multiplica el número de nodos por una constante, por lo que nos gustaría evitar esto si es posible; Otra forma en la que acabo de pensar que creo que funciona es dar un peso negativo muy grande al borde entre los nodos inicial y final, o un nodo que solo se conecta al inicio y al final con el peso 0, para garantizar que el ciclo resultante le permite comenzar en el nodo inicial y presionar todos los demás nodos que van en la otra dirección.
- ¿Qué papel juega la comprensión de los algoritmos y las estructuras de datos en la construcción de proyectos, conseguir un trabajo y hacer su trabajo?
- ¿Cuándo podrán los algoritmos de detección de imágenes filtrar imágenes ofensivas de manera confiable?
- ¿Cómo funciona el algoritmo de estimulación del presupuesto publicitario de Facebook?
- ¿Qué es una explicación intuitiva de inserción en un árbol AVL?
- Cómo ejecutar [(A * B) mod C] sin desbordamiento, si A y B son menores que C