• Author / Uploaded
• lealgol

Citation preview

INSTITUTO TECNOLÓGICO DE OAXACA MATERIA: Inteligencia Artificial

Puzzle

CATEDRÁTICO: M.C. Idarh Matadamas Ortiz.

ALUMNO: Leal Barragán Santiago ING. EN SISTEMAS COMPUTACIONALES

Horario: 17:00 – 18:00 hrs.

INTRODUCCIÓN En el presente trabajo se abordará el problema sobre el rompecabezas de ocho piezas el cual consta de una matriz de 3 x 3 con 8 elementos de números y un espacio en blanco, el problema consiste en que dado un patrón inicial de elementos desordenados los cuadrados adyacentes al espacio vacío pueden moverse a ese espacio de manera horizontal o vertical de tal forma que se puedan acomodar las piezas para llegar al estado final. PLANTEAMIENTO DEL PROBLEMA El rompecabezas de 8 piezas utiliza una cuadricula de 3 x 3 contiene cuadrados numerados del 1 al 8 y un espacio en blanco el problema consiste en ir de un estado inicial a un estado final utilizando solo los movimientos permitidos y la cantidad de pasos establecidos. ANALISIS DEL PROBLEMA  

Estados: 1, 2, 3, 4, 5, 6, 7, 8, 0. Estado inicial: 1, 2, 3, 8, 6, 4, x, 7, 5.

REPRESENTACION Costo del camino: Cada movimiento o paso, tiene un costo de uno (1), por lo tanto el camino desde un estado inicial a un estado meta es igual al número de pasos (o movimientos) que se dan para alcanzar el estado meta. 

Estado final: 1, 2, 3, 8, x, 4, 7, 6, 5. 1 8 7

2 x 6

3 4 5

 Reglas: se pueden mover las piezas que estén cerca del espacio en blanco, los movimientos permitidos son: arriba, abajo, izquierda, derecha. ESTADOA estados Un espacio de estados es el conjunto total de estados posibles que un problema tiene. Un estado representa un conjunto de propiedades que existen en un problema y que son únicos en cantidad/valor para todo el espacio de estados.

El espacio de estados para este problema se encuentra representado por el conjunto de todas las posibles ubicaciones de cada una de las fichas. A continuación se pretende graficar esto mediante una simple comparación de 2 estados distintos de 8 puzzle. Caso1: Caso2:

123 1 2 3 456 4 5 6 78X 7X 8 Caso1 es un estado distinto de Caso2 porque se ha movido 8 hacia la derecha y se ha dejado el espacio vacÌo en el espacio de al medio para la tercera fila. 

SOLUCION La cantidad de movimientos que se realizan para llegar al estado final. A. Grafos de estados 1 8 x

2 6 7

3 4 5

BUSQUEDA EN PROFUNDIDAD ARBOL

En la Podemos observar la representación del grafo con su respectiva solución. Cada nodo se deriva de otro nodo, para realizar la búsqueda y así sucesivamente hasta encontrar la solución. 28 17 2 1

BUSQUEDA EN AMPLITUD ARBOL

En la figura Se representa una parte del árbol de búsqueda del 8-puzzle, en esta podemos recorrer los estados o la ruta más corta para una solución del 8-puzzle, en el que consiste acomodar las piezas para llegar a un estado final (solución). El objetivo del árbol es encontrar un camino desde la raíz hasta una hoja donde represente la solución del problema planteado. El desplazamiento está dado en base al movimiento, si es un movimiento hacia arriba la posición en la que está el espacio en blanco tendría que restarle 3 para así ubicarse en la posición deseada como podemos ver en la fig. 4. Movimiento de desplazamiento. int desplazamiento[4] = { +3, -3, -1, +1 }; Para el desarrollo del programa se pidió desde consola el ingreso del patrón, esto para que si el usuario desea hacerlo aleatorio o variable pueda ver la diferencia, como podemos observar en la fig