Plantear correctamente un problema de decisión para un problema de ciclo hamiltoniano

Estoy dirigiendo un seminario de algoritmos y estoy tratando de expresar el problema del ciclo hamiltoniano de una nueva manera que es emocionante para los estudiantes. Sé que muchos de ellos juegan un juego llamado Hearthstone y estoy tratando de expresar un problema en ese juego como un problema de decisión.

Esencialmente, en la mayoría de los juegos de cartas, se descomponen y dejan de ser divertidos cuando una mecánica, que el diseñador no anticipó, agrega recursividad. En Hearthstone y Yu-Gi-Oh! ese problema se expresa bien en este video. En el paquete que les doy les explico cómo funciona la mecánica y cómo lleva a la recursividad, luego les pregunto lo siguiente:

  1. Exprese formalmente la mecánica que conduce a la recursividad en un juego de cartas con estados de entrada y salida como un problema de decisión.

  2. Muestre que este problema está en NP dando un algoritmo de verificación para este problema y demostrando que el algoritmo es correcto.

  3. Ya se sabe que el problema del ciclo hamiltoniano es NP-completo. Podemos demostrar que el problema de recursión en los juegos de cartas es NP completo al reducir el problema del ciclo hamiltoniano al problema de recursión del juego de cartas. Hágalo dando primero una reducción del problema del ciclo hamiltoniano al problema de recursión del juego de cartas. La reducción toma la entrada al problema del ciclo hamiltoniano y la convierte en entrada al problema de recursión del juego de cartas. Luego prueba que tu reducción es correcta.

Mi pregunta principal es: ¿Declaré algo incorrectamente? ¿Cambiarías algo sobre mi formulación del problema?

¿Cómo puedes expresar un juego de cartas como un problema de decisión?
Entrada de @JackM: "Algún juego de cartas" → ¿Pueden estas tarjetas llamarse recursivamente? Sí o no.
Pero, ¿qué es una "tarjeta"? ¿Qué significa que una tarjeta se "llame a sí misma"? ¿Todas las tarjetas llaman a otras tarjetas? ¿Por qué no puedo simplemente modelar esto diciendo que una tarjeta es básicamente un 0 si no puede llamarse a sí misma, o un 1 si puede, y luego un juego es una lista de bits, y el juego es recursivo si contiene un 1? Esta es una pregunta absurdamente amplia. Si yo fuera uno de sus estudiantes no tendría idea de qué hacer con él. La idea de modelar un juego de cartas como un gráfico no tiene sentido, porque no es como si cada carta en cada juego "llamara" a otra carta. Eso es algo específico de esta carta de Hearthstone.
Bueno, al menos en este problema, se necesitan combinaciones de cartas para poder hacer que el juego sea recursivo. En este juego, esta carta debe jugarse con cartas previamente, lo que llamará más de esta carta. Creo que la mayoría de las recursiones ocurren a través de alguna propiedad transitiva A → segundo, segundo → un, un → segundo, segundo → A,.... y así sucesivamente.
Ese es el ejemplo más simple de recursividad. Si se piensa en un gráfico, la recursividad ocurre cuando tienes un ciclo en el gráfico. Si no hay ciclo entonces no habrá recursión.
¿Qué es este gráfico? Los nodos son el conjunto de todas las cartas del juego, y los bordes son... ¿qué? A → B si A "llama" a B? Pero eso es tan arbitrario. Esta carta "Saronite Chain Gang" es la única en el juego que yo sepa que tiene la capacidad de invocar otra carta. Entonces, ¿todo este gráfico tiene solo un borde, desde un nodo hacia sí mismo?
Bueno, hay muchas combinaciones de este tipo de mazos que formarán árboles, no gráficos. Son pocos los que pueden formar ciclos. El objetivo es simplemente encontrar una baraja que pueda producir un ciclo. Entonces sí, un bucle sería un ciclo. Parte de la razón por la que elegí este ejemplo es que puede producir resultados triviales. El objetivo de la pregunta es que, en poco tiempo, aprendan sobre las reducciones.
Los vértices en este caso serían las cartas de un mazo de jugadores determinado y los bordes representan los caminos que cada carta puede hacer desde los demás vértices. En el caso de Saronite Chain Gang, eso produciría un bucle porque se llamaría a sí mismo. Para la mayoría de las barajas, no existiría un bucle.
Si el problema de detectar recursividad en un mazo realmente se reduce a detectar si existe o no un ciclo (en algún gráfico relacionado razonable), entonces el problema no es NP-completo y, por lo tanto, una reducción correcta del gráfico hamiltoniano no debería ser posible a menos que P=NP.

Respuestas (1)

Esto suena como una idea divertida. Tengo algunas ideas que podrían ayudar a depurar la tarea y mejorarla. (Parte del problema podría ser que no tengo suficiente información sobre el resto de la tarea, así que siéntete libre de corregirme).

  • Incluiría la mención de la elección del jugador en la definición de recursividad. Por ejemplo: "Los efectos de recurrencia ocurren en un juego de cartas cuando una cadena de efectos automáticos se activa en un bucle, sin que ningún jugador pueda romper el ciclo o elegir una alternativa".
  • La recursión fuera de control no es exactamente un proceso de bucle en términos de estados del juego, porque cantidades como la cantidad de cartas en tu biblioteca, o la cantidad de vida que te queda, etc. pueden cambiar. Por lo tanto, la locura tiene más que ver con la relación de activación automática entre diferentes efectos (A activa B activa C activa A). Esto hace que la declaración del problema sea un poco abstracta: no estoy inmediatamente seguro de cómo representar los efectos y sus relaciones desencadenantes.

  • El problema de decisión es un poco ambiguo (que podría ser intencional para permitir la creatividad, o que podría hacerse más preciso para ayudar a los estudiantes). Por ejemplo, podríamos querer formular el problema como: (1) ¿Puedes hacer un par de mazos de cartas de Hearthstone que podrían conducir a una condición de recurrencia? (2) ¿Pueden estos dos mazos, cuando se barajan y durante el transcurso del juego, dar lugar a una condición de recurrencia? (3) En este punto exacto del juego, ¿hay alguna acción que un jugador pueda realizar que conduzca a una condición de recurrencia?

    Todas estas alternativas equivalen básicamente al mismo tipo de problema NP, pero tener una implementación precisa puede ayudar. Creo que (3) es más atractivo para mí porque lo único que estás buscando son los efectos secundarios de las acciones disponibles actualmente de los jugadores.

  • ¿Tiene en mente una mecánica específica que cause la recurrencia, como el Shudderwock? De lo contrario, parece un poco abierto si tiene que asignar gráficos a un estado de juego particular entre dos jugadores que tiene un efecto de recurrencia descontrolado si el gráfico es hamiltoniano y si no. No estoy seguro si tiene un mapeo más específico en mente.

  • Podría ayudar proporcionar una razón contextual por la cual un procedimiento de decisión es apropiado aquí; por ejemplo, como parte del diseño del juego, puede intentar calcular si un jugador puede realizar alguna acción que conduzca a un efecto de recurrencia.

¿Tiene ejemplos de respuestas a las preguntas 1 y 2, y la reducción en 3?

El resto de la tarea se puede encontrar aquí: github.com/jakemckenzie/AlgorithmsSeminar/blob/master/Week8/… Todavía no he puesto las respuestas en formato pdf. Lo trabajé en una pizarra y aún no los he traducido a látex. Estaba dejando el problema más ambiguo ya que así es como mi instructor formuló un problema similar del que obtuve la idea. En ese problema, teníamos que reducir la recolección de cartas de Pokémon de los paquetes de cartas a la cubierta de vértices.
Quería publicar eso y luego volver después de pensar un poco más en tu respuesta. Creo que respondiste mi pregunta adecuadamente, pero quiero pensarlo un poco más. Gracias por tus comentarios.
Plantear correctamente un problema de decisión para un problema de ciclo hamiltoniano
RespuestasAquíPolítica de privacidad1y, 0v