3-3er PA

 Realizar un proyecto para resolver un problema de un juego clásico 1a parte (gato, ajedrez, puzzle, misioneros y caníbales, etc.), empleando un método de búsqueda óptima.

Puzzle 3x3 con búsqueda primero en profundidad.

Se tiene un Puzzle deslizante de 3x3 con un estado inicial y final como se muestra:

Estado inicial:

Estado final:   

El objetivo es así entonces llegar al estado final en el mínimo número de movimientos posibles (que para este juego por la ubicación del espacio vacío es de 12 movimientos que resulta la solución más viable).

Explicando por medio de grafos la acción a realizar, es decir la búsqueda del camino más “optimo”:

Como se puede observar, se tiene un nuevo puzzle, mismo que debe ser solucionado por medio de búsqueda primero en profundidad, teniendo en cuenta que este no puede ir en diagonal y por el tipo de “método” a utilizar, se opta por elegir el nodo del medio que será analizado a profundidad ya que este método nos permite realizarlo de esta forma (No se enseña todos los pasos por medio de nodos ya que supera el límite del peso en el documento). Se observará como se soluciona de tal forma que este nodo seleccionado, toma 12 pasos siendo el más óptimo para este caso.

Solución:

Representación:

Estado inicial: [[6,1,4], [8,3, 2], [h, 7, 5]]

Estado final: [[1,2,3], [8, h, 4], [7,6, 5]]

Operadores:

➢ Izquierda

➢ Arriba

➢ Derecha

➢ Abajo

✓ Número de estados = 9! = 362.880.

Movimientos del espacio vacío:

Arriba, Arriba, Derecha, Abajo, Izquierda, Abajo, Derecha, Arriba, Derecha, Arriba, Izquierda, Abajo.

Por lo tanto, como podemos observar en este caso, de utilizar otro nodo, nos puede llevar a caer en redundancias, ¿Por qué caería en el mismo lugar?, simplemente porque al elegir cualquier otro nodo, aunque no se muestra, en algún punto nos lleva al cómo estaba al inicio o si no entonces, después de muchos movimientos innecesarios, nos llevaría directamente al segundo nodo, sin tomar en cuenta también que pasaríamos por el tercer nodo que igual nos llevaría al segundo, creando así un tipo de bucle, como el que se mencionaba en el segundo producto de aprendizaje.