METODOS DE BUSQUEDA (PRIMERO EN ANCHURA, PRIMERO EN PROFUNDIDAD).

 MÉTODOS DE BÚSQUEDA

En inteligencia artificial el tema de búsquedas es central, dado que, por ejemplo, realizar acciones mecanizadas o resolver problemas, se reduce a buscar en un espacio de estados como se explicaba en el apartado anterior. En esa disciplina se estudian búsquedas ciegas (búsqueda primero en amplitud, primero en profundidad, profundidad iterativa, de costo uniforme, etc.)

Relacionado con la búsqueda del óptimo está el problema del control de la búsqueda, control planteado por Newell y Simon que ha generado una abundancia de trabajos en el campo de la inteligencia artificial. Se trata de elegir entre búsquedas heurísticas lo suficientemente buenas (no perfectas) como para que se pueda dar por concluida la búsqueda con una aceptable respuesta al problema en un lapso aceptable de tiempo.

EL PAPEL DE LA BÚSQUEDA EN LA INTELIGENCIA ARTIFICIAL

En Inteligencia Artificial (IA) los términos resolución de problemas y búsqueda se refieren a un núcleo fundamental de técnicas que se utilizan en dominios como la deducción, elaboración de planes de actuación, razonamientos de sentido común, prueba automática de teoremas, etc. Aplicaciones de estas ideas generales aparecen en la práctica totalidad de los sistemas inteligentes, como por ejemplo en los programas que tratan de entender el lenguaje natural, en los programas que tratan de sintetizar un conjunto de reglas de clasificación en un determinado dominio de actuación, o en los sistemas que realizan inferencias a partir de un conjunto de reglas.

CLASIFICACIÓN 

Para elaborar una clasificación de los sistemas de búsqueda se tienen muchas clasificaciones tantas como investigadores y autores en inteligencia artificial existen, en el módulo se ha tratado de organizar esta información para ofrecer un panorama lo más amplio posible para que el estudiante abarque la mayor cantidad de información, los nombres de los algoritmos y métodos de solución en unos casos tienen diferencias que se aclaran en el transcurso del documento. La siguiente clasificación se puede tomar como genérica para tener una idea de las posibilidades de búsqueda.

BÚSQUEDAS EN LOS ESPACIOS DE ESTADO

Agentes para la solución de problemas Son agentes basados en metas que determinan que deberán hacer por medio de secuencias de acciones que les permitan obtener estados deseables.

PASOS PARA LA SOLUCIÓN DE PROBLEMAS:

• ·     Formulación de metas: se establece el objetivo
• ·     Formulación del problema: se decide qué acciones y estados habrán de considerarse.
• ·   Búsqueda: evaluación de las posibles secuencias de acciones que le llevan a la meta y   elección de la más apta.
• ·    Ejecución: se llevan adelante la solución que presenta la búsqueda.                                                                                                                                                                                                  

 BÚSQUEDA PRIMERO EN ANCHURA

•  Principio: expandir el nodo menos profundo que no haya sido expandido
•  La frontera es una cola LIFO, i.e. nuevos sucesores van al inicio

 

ALGORITMO: PRIMERO EN ANCHURA

1.                Crear una lista con un solo elemento consistente en una trayectoria o camino de longitud cero: el nodo raíz

2.                Hasta que el primer camino de la lista llegue al nodo objetivo o se llegue a la lista vacía hacer

a.              Extraer el primer camino de la lista

b.              Expandir el nodo final de este camino a todos los vecinos del nodo terminal.

c.               Eliminar los ciclos de los caminos expandidos.

d.              Insertar estos nuevos caminos al Final de la lista.

3.                FIN Hasta

4.                Si se halla el nodo meta notifique el éxito, si no el fracaso

 

BÚSQUEDA PRIMERO EN ANCHURA

 

BUSQUEDA PRIMERO EN PROFUNDIDAD

•     Principio: expandir el nodo más profundo que no haya sido expandido
•   La frontera es una cola LIFO, i.e. nuevos sucesores van al inicio

ALGORITMO: PRIMERO EN PROFUNDIDAD

1.                Crear una lista con un solo elemento consistente en una trayectoria de longitud cero: el nodo raíz

2.                Hasta que el primer camino de la lista llegue al nodo objetivo o se llegue a la lista vacía HACER

a.              Extraer el primer camino de la lista

b.              Expandir el nodo final de este camino.

c.               Eliminar los ciclos de los caminos expandidos.

d.              Insertar estos nuevos caminos al INICIO de la lista

FIN Hasta

1.        Si la lista está vacía, entonces NO hay solución; Si no el primer camino de la lista es la solución

PRIMERO EN PROFUNDIDAD