IMPLEMENTACIÓN DE LA TÉCNICA DE BÚSQUEDA

ESCUELA POLITÉCNICA NACIONAL

FACULTAD DE INGENIERÍA DE SISTEMAS

INGENIERÍA EN SISTEMAS INFORMÁTICOS Y COMPUTACIÓN

INTELIGENCIA ARTIFICIAL

ALMENDÁRIZ VANESSA

MOLINA SAMANTHA

IMPLEMENTACIÓN DE LA TÉCNICA DE BÚSQUEDA

01 DE DICIEMBRE DEL 2014

ÍNDICE

pág.

Contenidos

ÍNDICE ................................................................................................................................................2

Tabla de Figuras .........................................................................................................................2

Introducción ...................................................................................................................................3

Marco Teórico ................................................................................................................................3

Búsqueda no informada .............................................................................................................3

Problema ....................................................................................................................................4

Implementación Conceptual ..........................................................................................................4

Diagrama de estados completos ................................................................................................5

Implementación Computacional ....................................................................................................5

Resultados ......................................................................................................................................8

Conclusiones ..................................................................................................................................9

Anexos ..........................................................................................................................................10

Tabla de Figuras

Figura 1: Generar estados. .................................................................................................................6

Figura 2: Método clone implementado para las funciones regresar y enviar. ...................................6

Figura 3: Comprobación del número de caníbales y de misioneros. ..................................................6

Figura 4: Función sucesor. ..................................................................................................................7

Figura 5: Función Arbol en la Clase Arbol ...........................................................................................7

Figura 6: Árbol que contiene los estados alcanzables por el agente. .................................................8

Figura 7: Resultado de la búsqueda primero en profundidad con profundidad iterativa...................9

Introducción

Uno de los problemas que se analiza en Inteligencia Artificial es el problema de los caníbales y los misioneros, en el cual se parte de un estadio inicial con tres caníbales y tres misioneros en una orilla y el estado objetivo es llevar a los seis a la otra orilla. Para hallar la solución de este problema se ha usado la búsqueda primero en profundidad con profundidad iterativa, que es una estrategia de la búsqueda no informada, con la eliminación de estados repetidos.

Marco Teórico

Búsqueda no informada

La búsqueda no informada, también conocida como búsqueda a ciegas, es un tipo de búsqueda que consiste en partir de un estado inicial para generar todos los estados posibles mediante los cuales se pueda encontrar la solución, cada vez que genera un estado lo compara con el estado objetivo. Si el estado actual es el estado objetivo encuentra solución, caso contrario genera un nuevo estado [1].

La búsqueda no informada posee cinco estrategias, estas son [1]:

a) Búsqueda en anchura

b) Búsqueda de costo uniforme

c) Búsqueda primero en profundidad

d) Búsqueda de profundidad limitada

e) Búsqueda primero en profundidad, con profundidad iterativa.

Búsqueda primero en profundidad con profundidad iterativa

La búsqueda primero en profundidad con profundidad iterativa, también conocida como búsqueda con profundidad iterativa, es una de las mejores estrategias que ofrece la búsqueda no informada. Esto debido a que combina las ventajas que ofrecen la búsqueda por anchura y búsqueda primero en profundidad [1].

Consiste en ir aumentando gradualmente el límite del árbol, comienza desde el nivel 0 y en cada iteración aumenta un nivel, en cada uno de estos se genera el árbol nuevamente. Esta estrategia es usada, especialmente, cuando el espacio de búsqueda es grande y no se conoce la profundidad de la solución [1].

Estados repetidos

Uno de los problemas que enfrenta este tipo de búsqueda es la generación de estados repetidos, para que este inconveniente se resuelve es conveniente llevar un registro de los estados visitados y comparar con el estado a generar para agregarlo, en el caso de que no esté presente en la lista, o para excluirlo, en el caso de que se encuentre dentro de la lista.

Problema

El problema de los tres misioneros y los tres caníbales radica en un estado inicial, donde los seis se encuentran en un lado de la orilla, y un estado objetivo que consiste en llevar a los seis al otro lado de la orilla. Para el transporte se tiene una canoa, en la cual pueden viajar dos personas (puede ser un misionero y un caníbal, o dos caníbales o dos misioneros) o una (un misionero o un caníbal).

También se debe considerar las restricciones, en estas se establece que el número de caníbales no puede superar al número de misioneros debido a que los caníbales devorarán al misionero y ya no se podría llegar al estado objetivo.

Implementación Conceptual

El objetivo del problema es pasar a todos a la otra orilla. La condición que se pone es que sólo se puede pasar a dos personas a la vez y que no debe ocurrir nunca que en una de las orillas haya un número mayor de caníbales que de misioneros, ya que se los comerían.

Estado inicial: I

D M:3;C:3

M:0;C:0

Estado objetivo:

I D

M:0;C:0 M:3;C:3

Condición: No debe existir #caníbales > #misioneros en cualquier orilla.

Estados:

 Parámetros:

Número de misioneros a la izquierda, número de caníbales a la izquierda, número de misioneros a la derecha, número de caníbales a la derecha, posición bote.

Operaciones:

 Transportar 2 misioneros.

 Transportar 2 caníbales.

 Transportar 1 misionero y 1 caníbal.

Diagrama de estados completos

Implementación Computacional

Para resolver el problema de manera óptima se ha utilizado un algoritmo con búsqueda en profundidad en el lenguaje de programación JAVA en Eclipse Luna.

Se creó una clase estado, donde se definió el número de misioneros a la izquierda, número de caníbales a la izquierda, número de misioneros a la derecha, número de caníbales a la derecha y posición bote (1: derecha, 0: izquierda. ). Los estados se implementan en una lista.

M:3;C:3M:0;C:0M:2;C:2M:1;C:1M:3;C:1M:0;C:2M:1;C:3M:2;C:0M:2;C:2M:1;C:1M:3;C:2M:0;C:1M:2;C:1M:1;C:2M:3;C:0M:0;C:3M:1;C:2M:2;C:1M:3;C:1M:0;C:2M:1;C:1M:2;C:2M:2;C:0M:1;C:3M:2;C:2M:1;C:1M:2;C:2M:1;C:1M:2;C:2M:1;C:1M:0;C:2M:3;C:1M:0;C:3M:3;C:0M:1;C:2M:2;C:1M:0;C:1M:3;C:2M:0;C:2M:3;C:1M:1;C:1M:2;C:2M:0;C:0M:3;C:3M:0;C:0M:3;C:3

Para la generación de estados se crea dos funciones: enviar y regresar.

Figura 1: Generar estados.

En estas dos funciones se implementa un clonable para poder clonar los estados. El método clone copia y regresa un clón del objeto. [2]

Figura 2: Método clone implementado para las funciones regresar y enviar.

Después se comprueba que los caníbales no sean mayores a los misioneros en cada orilla, para evitar un error (que se coman los misioneros).

Figura 3: Comprobación del número de caníbales y de misioneros.

Se crea una función sucesor que es una función recursiva. Ayuda a comprobar si el estado está en la lista y si ha aparecido para evitar que se repitan los estados que ya han pasado. Se establece el estado objetivo al que tiene que llegar (0, 0, 3, 3, 0 ).

Si, no cumple con las condiciones, salta al siguiente elemento de la lista de nodos hijos, el else if es igual al estado objetivo. Para la ejecución, el else es la parte recursiva que manda a generar estados de ese nodo, verifica si esta a la izquierda o a la derecha y en función de eso, envía o regresa. Puede enviar o regresar 2 caníbales, 2 misioneros o 1 caníbal y 1 misionero.

Figura 4: Función sucesor.

Mientras va buscando el estado objetivo, existe un caso especial en el que regresa 1 misionero o 1 caníbal, sino nunca pasa y se repite mientras no llegue a la solución.

Para generar el árbol de forma gráfica, se creó una clase Arbol y se usó los métodos para hacer árboles de JAVA.

Figura 5: Función Arbol en la Clase Arbol

Resultados

Para realizar la búsqueda no informada, con la estrategia primero en profundidad con profundidad iterativa, es necesario generar un árbol de los estados alcanzables por el agente; en este árbol se han eliminado los estados repetidos, esto debido a que ayuda a optimizar los la búsqueda.

En la Figura 6 se muestra el árbol generado, en el cual se

...