Es este problema NP-completo?

Question

dicen que hay una línea de x contenedores llenos de baratijas (cantidad al azar), en la llanura de visión (se puede ver el número de baratijas que hay en cada grupo). Ahora hay dos jugadores que puede, cuando es su turno recoger un contenedor desde cualquier extremo. No pueden renunciar a un turno. Vamos con una estrategia para un jugador para obtener la máxima cantidad de baratijas.

x es par.

¿Es un problema NP-completo? ¿Es similar a Boolean SAT?

Answer 1

Es muy sencillo problema, y ??no es NP completo. Aquí es breve descripción del algoritmo, que se basa en la programación dinámica.

Can [i] -. Array que almacena el número de baratijas
F [i, j] - array determinar lo que es mejor jugada si sólo latas de i a j son avaible. 0 significa llevan desde el lado izquierdo, 1 significa llevan desde el lado derecho.
G [i, j] - matriz donde se almacena 'bondad' de movimiento.

for (i=1 to n) F[i,i] = 0
for (i=1 to n) G[i,i] = Can[i]

for (i=1 to n-1)
   for (j=1 to n-i)
       tmp1 = Can[j] - G[j+1,j+i]
       tmp2 = Can[j+i] - G[j,j+i-1]
       if (tmp1>tmp2)
       {
             F[j,j+i] = 0;
             G[j,j+i] = tmp1;
       }
       else
       {
             F[j,j+1] = 1;
             G[j,j+i] = tmp2;
       }

Lo siento por la falta de comentarios, pero si usted lee algunos artículos sobre programación dinámica Usted recibirá sin ningún problema.

Answer 2

No, no es fácil de resolver con la programación dinámica en O(x^2). Mire problema 10 aquí .

Answer 3

Este problema parece ser perfecto para el alfa-beta-poda, ya que es fácil de obtener un límite inferior para sus puntos. Supongamos que el jugador se enfrenta a un número par de contenedores. Luego se puede jugar de una manera ya sea para obtener todos los contenedores en par o todos en posiciones impares:

Supongamos que tenemos 1 0 1 0 1 0, entonces él puede tomar la 1 a la izquierda, y cualquiera que sea el oponente lo hace, él sólo sigue recogiendo las 1 de.

Así que una forma fácil de calcular el límite inferior es el máximo de la suma de todos los contenedores en posiciones pares y la suma de todos los contenedores en posiciones impares.

Para el jugador "raro", se puede simplemente tomar la suma del (largo + 1) / 2 valores más pequeños, que no es tan bueno como el destino a la "par" jugador, pero también fácil de calcular.

Creo que con estos límites el árbol de búsqueda será escasa para aplicaciones prácticas (supongo que siempre se puede encontrar "patológicos" contra-ejemplos para este tipo de problema, sin embargo) por lo que la solución debe ser bastante rápido.

Answer 4

Es evidente que el primer jugador tiene una estrategia de lazo / ganar. Todo lo que tiene que hacer es comprobar si los contenedores de posición impares o los contenedores posición aún tienen un total mayor, y luego se pueden reproducir fácilmente tal que obliga al oponente para recoger los contenedores de la "pérdida de la" paridad.

Por ejemplo:

2,6,11,4,7,3

A continuación las posiciones impares son mejores (20 vs 13), por lo que el jugador 1 debe elegir 2. jugador entonces 2 debe elegir ya sea 6 o 3, que están en posiciones pares. Si se elige 3, el jugador 1 debe elegir 7, y así sucesivamente. En realidad, el jugador 1 debe elegir siempre la posición próxima a la elegida por su oponente, y se garantiza un empate o una victoria.