Como establece la red de hoja perenne The Physics of Santa , es físicamente imposible para Santa obtener un regalo para todos los niños del planeta. La planificación de rutas no ayudará mucho allí, pero ¿puede un buen algoritmo de planificación al menos asegurarse de que cada niño reciba un regalo de vez en cuando, mientras que Santa también atiende a tantos niños como sea posible cada año?
Considere una gráfica completa con pesos reales, positivos y una constante . Queremos resolver una variante del problema del vendedor ambulante:
¿Hay una ruta circular de longitud como máximo eso sirve más que nodos?
La versión de optimización sería:
Maximice la cantidad de nodos que se pueden servir con una ruta circular de longitud como máximo .
Esto está motivado por limitaciones del mundo real en las rutas: Santa tiene una noche para entregar tantos regalos como sea posible, un vendedor tiene ocho horas para la ruta de un día, y así sucesivamente.
La primera, pero no la última pregunta es: ¿qué tan difícil es este problema? Supongamos que podemos comenzar en cualquier nodo, pero eso no debería hacer mucha diferencia.
Ahora, para modelar la equidad, supongamos que hay nodos y podemos visitar como máximo con cada recorrido Idealmente, nos gustaría que cada nodo sea visitado veces a través Tours eficientes. Dado que puede haber nodos de cuello de botella que deben visitarse con mayor frecuencia para garantizar que las rutas visiten muchos nodos, inevitablemente algunos tendrán que visitarse con menos frecuencia. Eso también excluye la aproximación trivial de eliminar nodos una vez visitados hasta que todos hayan sido visitados.
Entonces, aquí está la pregunta final. Dejarser el número de recorridos necesarios hasta que todos los nodos hayan sido visitados por eficientes -Excursiones. ¿Cómo podemos determinar algorítmicamente el valor mínimo de(y todas las rutas necesarias)? ¿Qué tan complejo es este problema?
Supongo que este es realmente un problema de criterios múltiples: cada recorrido debe visitar tantos nodos como sea posible, mientras que queremos mantener los recorridos lo más disjuntos posible.
fuente
Respuestas:
Estoy un poco confundido Sik es una constante, entonces puedes probar todo O (nortek) Posibles recorridos. Por lo tanto, el problema está enPAGS .
Sin embargo, sik es parte de la entrada, el problema de decisión es N P -completar. Esto se puede demostrar reduciendoCIRCUITO DE JAMON al problema, por la siguiente reducción.
Supongamos que queremos determinar si unnorte gráfico de vértices sol tiene un circuito hamiltoniano. Luego tomamos el gráfico completoKnorte con la siguiente función de distancia
Déjame decirte por qué esto es una reducción. Sisol tiene un circuito hamiltoniano, luego hay un recorrido en Knorte con longitud norte . En otras palabras, una ruta circular de longitud≤ n eso sirve > ( n - 1 ) nodos Por otro lado, si hay un tour de Santa que visita> ( n -1 ) nodos tiene que visitar todos los nodos. Dado que la gira de Santa solo puede tener duración≤ n y cada longitud de borde es al menos 1, todo norte los bordes en este recorrido tienen longitud 1. Por lo tanto, este recorrido corresponde a un circuito hamiltoniano en sol .
fuente