Cómo encontrar el mayor valor posible al desplazar valores entre N nodos

Question

Me encontré con una interesante cuestión combinatoria mientras jugaba a Magic: the Gathering.

Tome N nodos en un grafo completo, cada nodo con un valor asignado. El valor de cada nodo comienza en 1, y puede aumentar a medida que avanza el juego. Cada movimiento del juego consiste en que un nodo suma su valor al valor de otro nodo con el que está conectado. (El nodo de origen no reduce su valor después de esta operación; los valores nunca pueden disminuir). Después de un movimiento en cada dirección a lo largo de una arista del grafo (dos movimientos en total), esa arista se borra y no se pueden hacer más movimientos a lo largo de esa arista. El objetivo es obtener el mayor valor total posible de todos los nodos después de realizar todos los movimientos. El número total de movimientos en el juego será (N elige 2) * 2. (El número de aristas multiplicado por 2, ya que cada arista permite un movimiento en cada dirección).

Por ejemplo, consideremos N=2. La configuración inicial es A=1, B=1. Para empezar el juego, el nodo A suma su valor al nodo B, resultando A=1, B=2. A continuación, el nodo B añade su valor al nodo A, lo que da como resultado A=3, B=2. El juego ha terminado, y la puntuación final es 5. La única otra posibilidad es que el nodo B se mueva primero, lo que simplemente da como resultado A=2, B=3 y la misma puntuación final.

Sin embargo, el problema se complica enormemente cuando se añaden más nodos. La complejidad del juego aumenta con extrema rapidez, lo que hace inviables los enfoques de fuerza bruta. Hasta ahora, los máximos que he alcanzado para varios N a través de la experimentación son:

N=1: 1 N=2: 5 N=3: 29 N=4: 249 N=5: 3866

Pero no estoy en absoluto convencido de que éstas sean las mejores respuestas (al menos para N>2). Hay una serie de conjuntos de instrucciones simples que pueden hacerlo bien, como "alejarse siempre del nodo con el valor más alto hacia el nodo con el valor más alto entre sus opciones legales". Esto no es necesariamente óptimo, sin embargo, y tengo curiosidad por saber si hay un algoritmo simple para maximizar el valor final que funciona en todos los N.

Answer 1

La secuencia de los mayores valores posibles parece comenzar $$1, 5, 29, 260, 4106, 122762, \dots$$ Sólo los cuatro primeros valores son seguros, pero tengo considerables pruebas numéricas de los dos últimos.

---

Dos patrones emergen cuando observamos las soluciones de alta puntuación para casos pequeños:

Conjetura 1. La mejor solución sigue un recorrido euleriano del grafo completo dirigido $\overrightarrow{K_n}$ . Mientras seguimos el recorrido, cada vez que damos un paso $v \to w$ añadimos el valor a $v$ al valor en $w$ .

Si es verdadero, esto reduce el número de casos que tenemos que comprobar: en lugar de $(N^2-N)!$ órdenes, sólo tenemos que probar todos los recorridos eulerianos posibles, y hay muchos menos.

Conjetura 2. Existe una solución óptima que realiza todas las operaciones que implican $N-1$ de los nodos (en cierto orden) antes de realizar todas las operaciones que afectan al último nodo (en cierto orden).

En cuanto a la conjetura 2, se puede demostrar que si la mejor solución tiene esta forma, entonces (después de permutar los nodos) termina con los pasos $$1 \to N \to 2 \to N \to 3 \to N \to \dots \to (N-1) \to N \to 1.$$ Esto también nos deja menos casos que comprobar: esencialmente, todas las formas en que podemos tratar la primera $N-1$ nodos.

---

Estas son las mejores soluciones que he encontrado:

• En $N=1$ , sin hacer nada anotaciones $1$ punto al final.
• En $N=2$ el recorrido euleriano $1 \to 2 \to 1$ puntuaciones $5$ puntos.
• En $N=3$ el recorrido euleriano $1 \to 2 \to 3 \to 2 \to 1 \to 3 \to 1$ puntuaciones $29$ puntos.
• En $N=4$ el recorrido euleriano $1 \to 3 \to 2 \to 3 \to 1 \to 2 \to 1 \to 4 \to 2 \to 4 \to 3 \to 4 \to 1$ puntuaciones $260$ puntos.

Hasta ahora, todo esto se ha verificado con fuerza bruta.

• En $N=5$ el recorrido euleriano $1 \to 4 \to 2 \to 4 \to 3 \to 4 \to 1 \to 3 \to 2 \to 3 \to 1 \to 2 \to 1 \to 5 \to 2 \to 5 \to 3 \to 5 \to 4 \to 5 \to 1$ puntuaciones $4106$ puntos.

He encontrado una variante de esta solución de tres formas: usando recocido simulado para obtener una solución de alta puntuación sin fuerza bruta; usando fuerza bruta sobre todos los recorridos eulerianos, asumiendo sólo la Conjetura 1; usando fuerza bruta sobre todos los $12!$ órdenes de las operaciones en los nodos $1,2,3,4$ suponiendo únicamente la conjetura 2. Esto sugiere que, de hecho, es óptima y que ambas conjeturas son ciertas.

• En $N=6$ el recorrido euleriano $1 \to 5 \to 2 \to 4 \to 2 \to 3 \to 2 \to 5 \to 3 \to 5 \to 4 \to 3 \to 4 \to 5 \to 1 \to 4 \to 1 \to 3 \to 1 \to 2 \to 1 \to 6 \to 2 \to 6 \to 3 \to 6 \to 4 \to 6 \to 5 \to 6 \to 1$ puntuaciones $122762$ puntos.

Esta última sólo era factible de encontrar asumiendo ambas conjeturas, y haciendo fuerza bruta sobre todos los recorridos eulerianos de nodos $1,2,3,4,5$ seguida de la secuencia $1 \to 6 \to 2 \to 6 \to 3 \to 6 \to 4 \to 6 \to 5 \to 6 \to 1$ .