El algoritmo de la mente maestra de Knuth

Question

Leí el otro rosca sobre el algoritmo de Knuth y la mente maestra, pero todavía no entiendo muy bien cómo se implementaría. Estoy confundido por el lenguaje o mi cerebro está roto (o ambos).

Entiendo que se parte de una lista S de todas las permutaciones posibles en función de los parámetros del juego concreto, por ejemplo una lista de 1296 combinaciones posibles de 4 dígitos donde cada dígito puede ser un número del 1 al 6 (incluyendo las repeticiones).

Se crea un número de 4 dígitos código secreto .

Usted juega un adivinar (de la lista S) contra el código secreto y recibir un respuesta en términos de "clavijas" blancas y negras, donde cada clavija negra significa la adivinar tiene el dígito correcto en el lugar correcto, y cada clavija blanca significa el adivinar tiene el dígito correcto en el lugar equivocado.

Según Knuth, siempre hay que utilizar 1122 como primer adivinar, del que se obtiene un respuesta en términos de clavijas blancas y negras.

A continuación, con el fin de reducir el número de posibles conjeturas para el siguiente turno y finalmente encontrar el código correcto, si la respuesta no es 4 clavijas negras (lo que significa que el código ha sido adivinado correctamente y el juego ha terminado), vamos a eliminar de S cualquier elemento (conjetura, código, como quieras llamarlo) que no daría la misma respuesta si it (el Supongo/código/elemento en S ) fueron los código .

¿Qué significa eso? ¿Alguien más está confundido por esa redacción?

No entiendo qué comparación se hace aquí. Para mí, esto significa que si la respuesta a la primera conjetura de 1122 es una negra, una blanca, eliminaríamos de S todas las conjeturas potenciales que, cuando se juega contra el código secreto, no devolvería la misma respuesta de un negro y un blanco. Eso nos dejaría, por supuesto, con una lista de posibilidades que no contendría la respuesta correcta, porque sería simplemente una lista de elementos que obtendrían todos una respuesta de un negro, un blanco.

Así que veo que obviamente eso no puede ser lo que significa, por lo que la alternativa es decir "OK debe significar que debes eliminar de S todas las conjeturas potenciales que también devuelven la respuesta de un negro, un blanco) y partir de ahí". Eso tiene más sentido que mi interpretación inicial, pero sigue sin parecerme correcto.

¿Puede alguien ayudar a explicar esto con múltiples ejemplos? No puedo entender qué comparación se hace y qué dos cosas se comparan realmente para eliminar elementos de S.

Answer 1

Digamos que $S_i$ es un elemento de $S$ los posibles valores del código ganador.

Lo que se pide a cada uno $S_i$ en el paso que te desconcierta es este:

Si la respuesta fuera $S_i$ ¿habría obtenido la respuesta que obtuve con mi suposición actual?

Si la respuesta es no, entonces $S_i$ no puede ser el código, porque habrías obtenido una respuesta diferente. Si la respuesta es afirmativa, entonces lo mantienes para otro turno, porque es consistente con la respuesta que obtuviste. En otras palabras, no puedes eliminarlo como imposible.

Mirando el ejemplo en el otro hilo:

Adivina $1122$ y obtener una clavija negra (un color de clavija correcto y en la posición correcta) y una clavija blanca (un color de clavija correcto pero en la posición incorrecta).

El paso de reducir la lista implica pedir, para cada $S_i$ "¿Habría conseguido una clavija negra y otra blanca con mi suposición de $1122$ si el código fuera $S_i$ ?"

Bien, hagamos unos cuantos:

• Si el código fuera $1111$ Habría conseguido dos clavijas negras ( $BB$ ) con mi suposición de $1122$ que no es lo mismo que una clavija negra y otra blanca ( $BW$ ). (Representar esto por $F(1122, 1111) = BB$ .) Así que quito $1111$ de la lista de posibles soluciones.
• $F(1122, 1112) = BBB \neq BW \to \text{Remove 1112 from S}$
• $F(1122, 1113) = BB \neq BW \to \text{Remove 1113 from S}$
• $F(1122, 1114) = BB \neq BW \to \text{Remove 1114 from S}$
• $F(1122, 1115) = BB \neq BW \to \text{Remove 1115 from S}$

Y así sucesivamente.

Sin embargo,

• $F(1122, 1314) = BW = BW \to \text{Keep 1314 in S}$

Espero que esto ayude.