Traer el zorro, el ganso y el cereal a través del río ileso

Question

Resolver el puzzle algebraicamente? No puedo llegar hasta elegante y algebraico de la solución.

Hay hombre, el zorro, la gallina, y los cereales. Si el hombre no está al lado de el zorro, el zorro se come la gallina. Si el hombre no está al lado de la gallina, la gallina va a comer el cereal. El hombre quiere llevarlos a una tierra a través del río. Lamentablemente, hay sólo un pequeño barco. La nave sólo puede contener el hombre y el zorro o el hombre y la oca o el hombre y el cereal.

Cómo resolver este rompecabezas con el álgebra? O cualquier concepto matemático, excepto de fuerza bruta enfoque.

Alguna idea? Gracias.

Answer 1

Me gustaría acercarse a este como un problema de teoría de grafos. Vamos a las configuraciones de la fox, de ganso, de cereales, y el barco de ser los vértices de un grafo. Cada vértice de los registros de una posición, y estamos tratando de encontrar un camino a través de la gráfica de la posición de inicio (marcado en verde) a la posición final (marcado en azul):

Un nodo llamado bg_cf significa que el barco (y el hombre) y la oca están en la orilla izquierda del arroyo, el cereal y el zorro en el margen derecho. La posición inicial, en verde, bcfg_ con las cuatro entidades en la orilla izquierda; el objetivo de la posición, en azul, es _bcfg con las cuatro entidades en la orilla derecha. Rojo posiciones están prohibidos. Entonces tenemos que encontrar un camino a través de la gráfica desde el verde al azul, evitando todos los red nodos.

Desde la red los nodos no ayuda, puede ser que también acaba de quitar de ellos:

Representados de esta forma, podemos resolver el rompecabezas de la globo ocular, o podemos utilizar un gráfico estándar de búsqueda algoritmo para encontrar una solución. Por ejemplo, si queremos que la más corta posible solución, se puede utilizar el habitual algoritmo de búsqueda en anchura. Pero una vez que el gráfico se dibuja, la solución es totalmente obvio, y es igual de claro que hay dos igual de corto mínima soluciones, y una familia infinita de los ya obtenidos por ir alrededor del bucle una o más veces.

Answer 2

La teoría de grafos, de cierta manera, puede ayudar a ver una solución.

Hacer un gráfico bipartito. Los vértices hacia la izquierda, significa que el barco (y el hombre) se encuentra en la orilla izquierda. Los vértices hacia la derecha, significa que el barco está en la orilla derecha. Cada uno de los dos conjuntos ha $8$ vértices, uno para cada uno de los posibles subconjuntos que podría estar en el banco correspondiente. Hacer que los bordes simplemente metódicamente conectando los vértices de un lado legalmente a los vértices de la otra, donde una relación jurídica es la que no deja a nadie/nada de comer. En realidad, no habrá tantos como 8 vértices en cada lado, ya que algunos estados nunca va a ocurrir, como (a la izquierda,el zorro,el ganso) y (a la izquierda, el hombre, fox).

La solución será visible como un camino desde el vértice (a la izquierda, el hombre, el zorro, la gallina, cereales) a la derecha, el hombre, el zorro, la gallina, cereales).

Answer 3

Pero tal vez la teoría de grafos es un exceso; en este caso, podemos resolver el problema mediante el razonamiento acerca de él. Esta no es la fuerza bruta como no tenemos en cuenta todas las posibilidades. Lejos de ello! – de hecho, en todas las etapas resulta que sólo hay en realidad un movimiento a tener en cuenta. Para anticiparse a cualquier acusaciones de falta de las matemáticas en esta solución, la matemática está en la simetría de la observación en el paso 3.

Voy a escribir posiciones cosas como FG-Cb, donde las letras tienen el zorro, la gallina, el cereal, el barco y el guión indica qué de qué lado. Por lo tanto, la posición inicial es FGCb-.

1. Si no nos movemos a la gallina, algo que se come mientras estamos fuera. Por lo tanto, moverse a la FC-Gb.
2. Trayendo a la gallina de vuelta a la izquierda es inútil, así que vuelven de vacío: FCb-G.
3. Por simetría, no importa lo cruzamos con el rompecabezas no cambia si nos movemos en un universo donde el cereal come ocas y gansos comen zorros. Lanzar una moneda, sale cara, tomamos el zorro: C-FGb.
4. Llevar el zorro de nuevo es inútil, así que tenemos que volver con el ganso para evitar ser comido: CGb-F.
5. Traer a la gallina de espalda es inútil, por lo que debemos tomar el cereal para evitar ser comido: G-FCb.
6. Ahora es obvio que la solución es ir a buscar el ganso: Gb-FC, entonces -FGCb y hemos terminado.

Answer 4

Las soluciones de MJD y alex.jordania tanto el uso de la teoría de grafos. Sin embargo, MJD es sólo solucionable "globo ocular", porque su gráfica-dibujo de software ha hecho que los caminos obvios y alex.jordania es bastante difícil (pero no imposible) para resolver por el ojo debido a que la gráfica se dibuja con la mano y salió un poco desordenado. Así, la pregunta es, "¿Cómo puedo producir un gráfico de la mano que se parece más a MJD y menos como la de alex?"

La primera cosa a hacer es comprobar cómo es de grande el espacio de búsqueda. Si el espacio de búsqueda es pequeño, se puede trabajar a mano, sin necesidad de ser demasiado inteligente; si es de tamaño moderado, se puede resolver por computadora, sin ser demasiado inteligente; si es grande, es necesario utilizar un ordenador y ser inteligente. Estimación aproximada: tenemos un barco, un zorro, un ganso y algunos cereales, cada uno de los cuales puede ser a la izquierda o a la derecha del río, por lo que el número de estados es en la mayoría de las $2^4=16$, que es pequeño. De hecho, hay un menor número de estados que en esto porque varios posibles estados de dejar la gallina de los desatendida con el zorro o el cereal.

También debemos conseguir una manija en el factor de ramificación: ¿cuántos movimientos legales que hay en cada posición? Nunca hay más de cuatro opciones (cruz con nada, con la fox, con el ganso o con los cereales), pero, en realidad, no puede haber más de tres que no resultan en algo ser comido, ya que, si todos los tres cargas están en el mismo lado, debemos mover el ganso. También, en cualquier posición, excepto la inicial, uno de nuestros movimientos disponibles es deshacer el movimiento que acabamos de hacer, que es inútil. Por lo que el factor de ramificación es, de hecho, en la mayoría de los dos para cada posición, de nuevo, no necesitamos hacer nada inteligente.

Desde el espacio de búsqueda y el factor de ramificación son pequeños, se puede proceder mediante la búsqueda en anchura. En profundidad se corre el riesgo de ir hacia abajo de los lados largos sucursales y perdiendo mucho tiempo en investigar cualquier largo soluciones que puedan existir. Para ayudar a la búsqueda en anchura, también tenemos la siguiente observación clave que tenemos, de hecho, ya se utiliza: una óptima (la más corta) de la solución nunca se repite una posición. Si una solución se repite una posición, usted podría conseguir a un acortamiento de la solución sin pasar por los pasos entre las dos ocurrencias de esa posición. Por lo tanto, en nuestra búsqueda, si alguna vez nos viene a través de una rama que hemos visto antes, podemos descartar de inmediato. Asimismo, descartar cualquier posición en la que algo se come.

Ahora, si empiezas a dibujar a cabo la búsqueda en anchura árbol, verás algo que se parece mucho a MJD los diagramas y es fácil ver que hay una solución.

Answer 5

Si usted quiere evitar la lógica y la gráfica de las pruebas, la otra manera de hacerlo es observando las siguientes: fox y cereales +- el mismo, se plantean problemas cuando se coloca junto con la gallina, pero no hacen daño el uno al otro.

Usted puede entonces construir los siguientes estados:

----------------
| left | right | (fox/cereal)
----------------
| left | right | (goose)
----------------
| left | right | (man)
----------------

Si usted anote toda permitido posiciones con el hombre a la izquierda, el symmetrie de las reglas dice que si cambiamos a la izquierda y a la derecha, usted tiene todo el conjunto de posiciones.

A continuación, puede definir los siguientes estados :

A     B     C     D
2|0   2|0   1|1   0|2
1|0   0|1   1|0   1|0
1|0   1|0   1|0   1|0

y definir el operador * como el intercambio de izquierda y derecha, básicamente, tenemos que ir de A->a* para resolver este acertijo.

Usted puede entonces construir la siguiente matriz:

         state1*     state2*    ...
state1   possible?   possible?
state2   possible?   possible?
...

Aplica a los estados que hemos definido, esta matriz sería algo como esto (vamos a llamarlo Y) También aviso, Y es simétrica.

     A* B* C* D*
A    0  0  0  1
B    0  0  1  1
C    0  1  1  0
D    1  1  0  0

Es posible, entonces, encontrar la menor cantidad de pasos que se tarda en ir desde A->A* por encontrar el más pequeño de n (n un valor natural) para que Y^(2*n+1)[0][0] no es cero, entonces la más pequeña ruta es de 2*n+1. En nuestro caso es n=3 => el más pequeño de la ruta es de 7 pasos

Ahora a encontrar el camino. Si usted

(Y^7).1 = 1
      0   6
      0   14
      0   14

Nos damos cuenta de que sólo hay 1 camino para ir de Un punto a a Un* en 7 pasos, esto significa que en cada paso a lo largo del camino, sólo debe haber un camino para llegar a él. Ahora la reconstrucción de este camino, debemos tomar Y^6, Y^5, Y^4 ... y se multiplica por [1,0,0,0] (ya hemos tenido que hacer esto para darse cuenta de 7 pasos es lo de menos). Si usted ve un 1 en la matriz resultado, fue un punto de nuestra solución fue pasado. (impar exponentes de Y significa que vamos a la derecha, incluso exponentes significa que vamos a la izquierda)

Por ejemplo:

(Y^6).1 = 5
      0   9
      0   5
      0   1

entonces, el paso antes de que la última fue en estado D. Un ejemplo para los últimos pasos : A* <= D <= B* <= ... <= A

--------------------------------------------------

Yo creo que esta no es la mejor solución, pero solicitó una solución algebraica. Este es el más algebraicas yo podría hacer con la menor cantidad de fuerza bruta / la enumeración de soluciones. Este rompecabezas es, sin embargo, tan pequeños que en cada paso a lo largo del camino es esencialmente forzado, y usted podría simplemente usar la lógica...

No creo que los gráficos eran correctas soluciones, porque eran llanura de la fuerza bruta de la búsqueda de espacio.