Digamos que hay una línea de x contenedores llenos de baratijas (cantidad aleatoria), a la vista (se puede ver cuántos abalorios hay en cada contenedor). Ahora hay dos jugadores que pueden cuando es su turno escoger un contenedor de cualquier lado. No pueden renunciar a un turno. Propón una estrategia para que un jugador obtenga la cantidad máxima de baratijas.¿Este problema es np-completo?
x es par.
¿Es un problema NP-completo? ¿Es similar al SAT booleano?
Es muy sencillo problema, y no es NP completo. Aquí hay una breve descripción del algoritmo, se basa en la programación dinámica.
Can [i] - array que almacena número de baratijas.
F [i, j] - array que determina cuál es el mejor movimiento si solo las latas de i a j están disponibles. 0 significa tomar desde el lado izquierdo, 1 significa tomar desde el lado derecho.
G [i, j] - array donde se almacena la 'bondad' del 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 lee algunos artículos sobre la programación dinámica lo obtendrá sin ningún problema.
No, es fácilmente solucionable con programación dinámica en O(x^2). Mire el problema 10 here.
Este problema parece ser perfecto para la poda alfa-beta, ya que es fácil obtener un límite inferior para sus puntos. Supongamos que el jugador se enfrenta a un número par de bandejas. Entonces puede jugar de una manera para obtener todos los contenedores en forma pareja o todos en posiciones impares:
Digamos que tenemos 1 0 1 0 1 0, entonces él puede tomar el 1 de la izquierda, y haga lo que haga su oponente, él sigue recogiendo los 1's.
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 "impar" puede simplemente sumar la suma de (longitud + 1)/2 valores más pequeños, que no es tan bueno como el límite para el jugador "par", pero también es fácil de calcular.
Creo que con estos límites el árbol de búsqueda será escaso para aplicaciones prácticas (aunque siempre se pueden encontrar contra-ejemplos "patológicos" para este tipo de problema), la solución debería ser bastante rápida.
Está claro que el primer jugador tiene una estrategia de empate/victoria. Todo lo que tiene que hacer es verificar si los bins de posición impar o los bins de posición pares tienen un total mayor, y luego puede jugar fácilmente de manera tal que obligue al oponente a recoger los bins de la paridad "perdedora".
Por ejemplo:
2,6,11,4,7,3
Aquí las posiciones impares son mejores (20 vs 13), por lo que el jugador 1 debe elegir 2. A continuación, el jugador 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 siempre debe elegir la posición al lado de la elegida por su oponente, y garantiza un empate o una victoria.
¿Realmente desea crear una estrategia, que pueda competir contra oponentes arbitrarios o desea crear para una línea de baratija determinada la secuencia de movimientos (del jugador uno * y * del jugador dos), de modo que el jugador uno obtenga el cantidad máxima posible de baratijas? – phimuemue
@phimuemue - En esencia, si fuera jugador1, ¿cuál es la estrategia que debo seguir para ganar? Dado el jugador 2 hace cualquier tipo de movimiento. Lo más probable es que juegue a su favor también. Creo que necesita enumerar todos los caminos posibles y encontrar la recompensa de ese camino. Y el jugador simplemente sigue ese camino. – user376070
No es realmente significativo preguntar si un juego (en el sentido de la teoría del juego, que es) es NP-completo. Sin embargo, puede preguntar si una estrategia en particular es NP completa. –