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

...