¿Puede Santa ser justo y eficiente?

8

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 k. Queremos resolver una variante del problema del vendedor ambulante:

¿Hay una ruta circular de longitud como máximo k eso sirve más que m 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 k.

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 N nodos y podemos visitar como máximo Mcon cada recorrido Idealmente, nos gustaría que cada nodo sea visitadotMN veces a través tTours 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. DejarTser el número de recorridos necesarios hasta que todos los nodos hayan sido visitados por eficientes k-Excursiones. ¿Cómo podemos determinar algorítmicamente el valor mínimo deT(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.

Rafael
fuente
2
El verdadero Santa usa buena magia para resolver problemas NP-completos en O(1)hora. Si tiene una instancia difícil de 3DM que necesita resolver antes de fin de año, intente escribirle en el polo norte, y si ha sido un buen pequeño investigador, puede que le traiga la respuesta en Navidad.
Mark Dominus

Respuestas:

5

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, si k es parte de la entrada, el problema de decisión es nortePAGS-completar. Esto se puede demostrar reduciendoCIRCUITO DE JAMON al problema, por la siguiente reducción.

Supongamos que queremos determinar si un nortegráfico de vértices soltiene un circuito hamiltoniano. Luego tomamos el gráfico completoKnorte con la siguiente función de distancia

wyoj: ={1Si (vyo,vj) es una ventaja en sol2de otra manera.
Además elegimos k=norte y metro=norte-1.

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 longitudnorte eso sirve >(norte-1)nodos Por otro lado, si hay un tour de Santa que visita>(norte-1)nodos tiene que visitar todos los nodos. Dado que la gira de Santa solo puede tener duraciónnorte 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.

A.Schulz
fuente
Esto es cierto para encontrar un recorrido con muchos nodos, pero ¿el objetivo adicional y competitivo de visitar todos los nodos con pocos recorridos complica las cosas?
Rafael