Estoy buscando el nombre de los siguientes dos problemas y un enfoque para resolverlos.
Problema n. ° 1: dados N nodos, encuentre la ruta más corta que comience en un nodo de inicio dado y termine en un nodo final dado, y pase por cada nodo exactamente una vez. La diferencia con el problema básico del viajante de comercio es que no hay regreso a la ciudad de inicio y se da la ciudad de destino.
Problema #2: similar al problema #1 pero con "pares" de nodos (o ciudades). Supongamos que tenemos N pares de nodos (por lo tanto, 2N nodos en total). La restricción de "par" significa que si la ruta llega a cierto nodo, entonces el siguiente nodo de la ruta es necesariamente su nodo par. Por ejemplo, imagina los siguientes pares de ciudades: Berlín/Roma, Washington/Seattle, Beijing/Seúl y Londres/París. Si el camino pasa por Berlín, entonces el siguiente nodo del camino debe ser Roma. De manera similar, si el camino pasa por Roma, entonces el siguiente nodo debe ser Berlín. Dado el nodo inicial Washington y el nodo final París, una ruta "válida" es Washington-Seattle-Seúl-Beijing-Roma-Berlín-Londong-París, por ejemplo. Dados N pares de nodos, un nodo inicial y un nodo final, encuentre el camino más corto que pase por cada ciudad exactamente una vez y verifique el "par"
¡Gracias!
Vaquero
Si está interesado en soluciones exactas y no se encuentra en un entorno geométrico (es decir, sin desigualdad triangular), puede agregar una constante muy grande a cada uno de los que no son pares y resolver el problema del viajante regular. Esta constante te obligará a usar todos los pares de aristas (1 en el primer problema, n en el segundo), y dado que la cantidad de veces que usas aristas que no son pares es fija, te da una solución óptima.
Una solución del Problema 1: Sea y ser nodos de inicio y final. Introducir un nuevo nodo (una ciudad ficticia) y establecer para todos . Ahora resuelve el problema básico del viajante de comercio.
Una solución del Problema 2: Si es un par "enlazado", conjunto y resuelva el problema básico del viajante de comercio (supongo que todas las distancias en su problema son positivas; si no, agregue un número positivo fijo a cada distancia).
JRN
hombre espacial