• Author / Uploaded
• Ismael Tlapaya Tepech

Citation preview

2013 Técnicas de IA Integrantes: Andros, Miguel, Ismael, Stephanie y Tomas

[PROBLEMA DE LAS TRES JARRAS] IMPLEMENTACION DE UN PROGRAMA QUE HALLE LA SOLUCION AL PROBLEMA MEDIANTE LOS METODOS DE BUSQUEDA CIEGA

PROBLEMA DE LAS TRES JARRAS Disponemos de tres jarras de capacidades 8, 5 y 3 litros, respectivamente, y queremos conseguir 4 litros en una de ellas, vaciando y llenando adecuadamente el líquido.

Se representan los estados con (x,y,z) con x en {0,1,2,3}, y en {0,1,2,3,4,5}, z en {0,1,2,3,4,5,6,7,8}

Diseño Dados los requerimiento del problema es necesario hacer uso de estructuras de datos que nos permitan ofrecer una solución. Las estructuras de datos empleadas son   

Árbol Cola Pila

La estructura de dato básica es un árbol, donde cada nodo representa un estado, la raíz representa el estado inicial, los hijos son los estados resultantes que se obtienen al aplicar operaciones sobre los estados. Dada la naturaleza da la búsqueda a ciegas el árbol se construye explorando y aplicando operadores, esto se hace mediante los recorrido vistos en clase. Para este propósito se usa la pila para el recorrido en profundidad y la cola para el recorrido en anchura, así mismo es necesario usar una cola para almacenar los nodos visitados y así evitar repetirlos Por último el lenguaje que decidimos usar fue java, la razón es que dominamos mejor java que otros lenguajes.

Resultados EL programa tiene la siguiente secuencia de operaciones

Primera secuencia Estado inicial (0, 0 ,0) Vaciar jarra 1 Vaciar jarra 2 Vaciar jarra 3 Llenar jarra 1 Llenar jarra 2 Llenar jarra 3 Vaciar jarra 1 en 2 Vaciar jarra 1 en 3 Vaciar jarra 2 en 1 Vaciar jarra 2 en 3 Vaciar jarra 3 en 1 Vaciar jarra 3 en 2

Anchura Tiempo 0:320 Seg:Milisegundos Espacio 85 Completa SE ENCONTRO LA SOLUCION Camino (000)(300)(030) (330)(150)(051) (351)(054)

Profundidad 0:13

Profundidad acotada iterativa 0:805

10 SE ENCONTRO LA SOLUCION (000)(008)(053) (323)(026)(206) (251)(341)(044)

405 9 iteraciones SE ENCONTRO LA SOLUCION (000)(008)(053) (323)(026)(206) (251)(341)(044)

Segunda secuencia

Estado inicial (0, 0, 0) Vaciar jarra 1 en 3 Vaciar jarra 3 Llenar jarra 1 Llenar jarra 2 Vaciar jarra 1 Llenar jarra 3 Vaciar jarra 3 en 1 Vaciar jarra 1 en 2 Vaciar jarra 2 en 1 Vaciar jarra 2 en 3 Vaciar jarra 3 en 2 Vaciar jarra 2

Anchura Tiempo 0:334 Seg:Milisegundos Espacio 83 Completa SE ENCONTRO LA SOLUCION Camino (000)(300)(003) (303)(006)(306) (036)(054)

Profundidad 0:17 12 SE ENCONTRO LA SOLUCION (000)(008)(053) (003)(030)(038) (056)(006)(051) (001)(010)(018) (054)

Profundidad acotada iterativa 1:134 492 9 iteraciones SE ENCONTRO LA SOLUCION (000)(008)(053) (323)(026)(206) (251)(341)(044)

Tercera secuencia

Estado inicial (0, 0, 0)

Vaciar jarra 1 en 3 Vaciar jarra 3 Vaciar jarra 3 en 2 Vaciar jarra 1 en 2 Llenar jarra 2 Vaciar jarra 1 Llenar jarra 3 Vaciar jarra 3 en 1 Vaciar jarra 2 en 3 Vaciar jarra 2 en 1 Vaciar jarra 2 Llenar jarra 1

Anchura Tiempo 0:334 Seg:Milisegundos Espacio 83 Completa SE ENCONTRO LA SOLUCION Camino (000)(050)(005) (055)(352)(052) (007)(304)

Profundidad 0:17 10 SE ENCONTRO LA SOLUCION (000)(300)(308) (358)(058)(328) (028)(208)(307) (007)(304)

Profundidad acotada iterativa 0:696 421 9 iteraciones SE ENCONTRO LA SOLUCION (000)(300)(308) (038)(338)(158) (108)(018)(054)

Cuarta secuencia

Estado inicial (0, 0, 0) Vaciar jarra 3 en 2 Vaciar jarra 1 en 2 Vaciar jarra 2 Vaciar jarra 3 Llenar jarra 3 Vaciar jarra3 en 1 Vaciar jarra 1 en 3 Llenar jarra 2 Vaciar jarra 2 en 3 Vaciar jarra 2 en 1 Llenar jarra 1 Vaciar jarra 1

Anchura

Profundidad

Tiempo 0:336 Seg:Milisegundos Espacio 91

0:222

Completa

SE ENCONTRO LA SOLUCION (000)(300)(350)(305) (005)(055)(325)(025) (205)(255)(345)(045) (315)(015)(105)(155) (335)(038)(338)(158) (108)(153)(333)(036) (336)(138)(130)(031) (331)(034)

Camino

SE ENCONTRO LA SOLUCION (000)(050)(005) (302)(352)(307) (037)(334)

32

Profundidad acotada iterativa 1:18 470 11 iteraciones SE ENCONTRO LA SOLUCION (000)(300)(350) (305)(005)(055) (325)(025)(205) (304)

Quinta Secuencia Estado inicial (2, 4, 7) Vaciar jarra 1 Vaciar jarra 2 Vaciar jarra 3 Llenar jarra 1 Llenar jarra 2 Llenar jarra 3 Vaciar jarra 1 en 2 Vaciar jarra 1 en 3 Vaciar jarra 2 en 1 Vaciar jarra 2 en 3 Vaciar jarra 3 en 1 Vaciar jarra 3 en 2

Anchura Tiempo 0:141 Seg:Milisegundos Espacio 15 Completa SE ENCONTRO LA SOLUCION Camino (247)(047)(344)

Profundidad 0:140

Profundidad acotada iterativa 0:15

20 SE ENCONTRO LA SOLUCION (247)(256)(355) (328)(320)(302) (005)(000)(008) (053)(323)(026) (326)(128)(155) (335)(330)(033) (051)(321)(024)

48 iteraciones SE ENCONTRO LA SOLUCION (247)(240)(204)

Profundidad 0:001

Profundidad acotada iterativa 0:001

2 SE ENCONTRO LA SOLUCION (315)(351)(054)

10 4 iteraciones SE ENCONTRO LA SOLUCION (315)(351)(054)

Estado inicial (3, 1 ,5)

Vaciar jarra 1 Vaciar jarra 2 Vaciar jarra 3 Llenar jarra 1 Llenar jarra 2 Llenar jarra 3 Vaciar jarra 1 en 2 Vaciar jarra 1 en 3 Vaciar jarra 2 en 1 Vaciar jarra 2 en 3 Vaciar jarra 3 en 1 Vaciar jarra 3 en 2

Anchura Tiempo 0:140 Seg:Milisegundos Espacio 25 Completa SE ENCONTRO LA SOLUCION Camino (315)(045)(054)

Estado inicial (1, 1, 1) Vaciar jarra 3 en 2 Vaciar jarra 1 en 2 Vaciar jarra 2 Vaciar jarra 3 Llenar jarra 3 Vaciar jarra3 en 1 Vaciar jarra 1 en 3 Llenar jarra 2 Vaciar jarra 2 en 3 Vaciar jarra 2 en 1 Llenar jarra 1 Vaciar jarra 1

Anchura Tiempo 0:156 Seg:Milisegundos Espacio 43 Completa Camino

Profundidad 0:842

Profundidad acotada iterativa 0:141

53

69 6 iteraciones SE ENCONTRO LA SE ENCONTRO LA SE ENCONTRO LA SOLUCION SOLUCION SOLUCION (111)(021)(321)(024) (111)(011)(311) (111)(011)(311) (302)(352)(052) (014) (322)(022)(202) (252)(342)(042)(312) (303)(003)(053)(323) (023)(203)(253)(343) (043)(313)(013)(103) (153)(333)(036)(336) (318)(308)(038)(335) (035)(332)(152)(107) (157)(057)(327)(027) (324)

Observaciones La primera secuencia de operadores tiene un orden de procesar según el tipo de operación llenar vaciar o vaciar en desde la jarra de menor capacidad hasta la de mayor capacidad, esta fue la que mejores resultados nos arrojó. Como se puede observar el tiempo varía entre un método y otro, así como el camino solución que nos arrojan las funciones. Denotamos que la función de búsqueda en profundidad siempre resulto ser mas rápida, mientras que el recorrido a lo ancho a pesar de no ser el más rápido siempre nos entregó el camino más eficiente para resolver el problema. Cuando cambiamos los estados iniciales los tiempos en nuestros casos de prueba se redujeron en un 50%, esto es lo nosotros hemos experimentado a menudo al tratar de destapar la mermelada sin éxito (solo aflojarla) para que alguien más destape el frasco sin mayor esfuerzo.

Conclusión La búsqueda sin información requiere un mayor esfuerzo que en ocasiones solo conduce a callejones sin salida, la implementación de la solución fue relativamente fácil, sin embargo hallar la solución exige un gran costo, podemos decir que entre los tres métodos a pesar de las desventajas que tienen el método de recorrido en profundidad, fue este el que nos entregó mejores resultados minimizando los costos operacionales. Por esta razón si nos pidieran elegir entre los métodos nos aventuraríamos a elegir recorrido en profundidad o alguna de sus versiones modificadas.