ESTRATEGIAS DE BÚSQUEDA

Fecha de clase: 20/mayo/2014

INTRODUCCIÓN

Problemas en el mundo real existen (y muchos), así mismo existen soluciones para estos, pero no todas nos llevan a esta esperada solución con la misma eficiencia. Es por esto que se hace necesario conocer las técnicas de resolución, abstraer sus características más significativas para poder decidir cuál es la adecuada frente a cada problema.  

En este caso se desea dar solución a problemas de búsqueda en inteligencia artificial, para esto existen técnicas heurísticas (cuando se dispone de información) y técnicas a ciegas (o no informadas, cuando apenas se tiene la descripción del problema).

Los temas propuestos y la explicación de la docente se orientan a que el estudiante comprenda el funcionamiento básico de las técnicas de búsqueda para luego tener la capacidad de aplicarlos en problemas del mundo real, identificando el método de búsqueda adecuado para la resolución de problemas, dependiendo si se tiene o no información.  

MARCO TEÓRICO

Un problema de búsqueda en Inteligencia Artificial tiene algoritmos que trabajan con estructuras de datos llamadas nodos que contienen en particular información sobre un estado. Un problema de búsqueda consta de:

-          Un espacio de estados, que es el conjunto de estados factibles para un problema junto a la estructura de adyacencia definida implícitamente por los operadores o reglas. (Rubio et al. 1998)

-          Un conjunto de operadores (acciones, con costes). La finalidad de una secuencia de operadores es transformar el estado inicial en el estado objetivo.

-          Un estado inicial (punto de partida de la búsqueda).

-          Una función objetivo (comprueba si el estado actual corresponde a una solución del problema). La solución consiste en una secuencia de operadores que transforman el estado inicial en el estado objetivo. (Rubio et al. 1998)

La búsqueda la realiza un programa (o agente). El espacio de búsqueda será un grafo dirigido en el que cada nodo representa un posible estado del sistema. Dependiendo del problema, cada nodo incluirá una descripción completa del sistema, o bien sólo las modificaciones necesarias para pasar de un nodo padre a su hijo. (Berzal, F. s.f.)

Debido a que la búsqueda es el núcleo de muchos procesos inteligentes, es necesario escoger la estructura de control apropiada con el fin de que el proceso de búsqueda sea eficiente. La inteligencia artificial proporciona varias técnicas de búsqueda que tienen una formulación matemática, la cual hace posible su implementación computacional bajo el esquema de programación estructurada. (Molina et al. 2008)

Rubio et al (1998) indican las restricciones sobre las secuencias solución:

-          Encontrar la secuencia más corta.

-          Encontrar la secuencia menos costosa (en este caso se supondrá que los disparos de las reglas tienen asociado un coste o, equivalentemente, que el espacio de estados tiene pesos en las aristas).

-          Encontrar cualquier secuencia lo más rápido posible.

Al evaluar una estrategia habrá que tener en cuenta lo siguiente:

Tiempo de cálculo <==> Calidad de la solución.

Un punto muy importante que señalan estos autores es que todos los problemas de búsqueda requieren no sólo que se encuentre un camino solución, sino todos los que existan (probablemente para poder aplicar estrategias, por ejemplo en un juego de ajedrez).

Existen diversos métodos de realizar búsquedas, a continuación se muestran dos grandes grupos que son búsqueda informada o heurística y la búsqueda a ciegas o no informada.

HEURÍSTICAS

Las heurísticas son criterios, métodos o principios para decidir cuál de entre varias acciones promete ser la mejor para alcanzar una determinada meta. (Berzal, F. s.f.)

Es el tipo de estrategia que sabe si un estado no objetivo es más prometedor que otro, permitiendo reducir la búsqueda (Russell y Norvig. 2004); es decir, como disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, se pueden explorar en primer lugar los caminos más prometedores. (Rubio et al. 1998)

Según Rubio et al (1998), los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.

BÚSQUEDA NO INFORMADA O BÚSQUEDA A CIEGAS

Engloba las estrategias de búsqueda que no cuentan con información adicional sobre los estados, aparte de la definición del problema. Estas sólo pueden generar los sucesores y distinguir entre un estado objetivo de un estado no objetivo. Las estrategias que saben que un estado no objetivo es más prometedor que otros se llaman por lo contrario búsqueda informada o búsqueda heurística. Sin embargo, todas las estrategias se distinguen por el orden de expansión de los nodos (Russell y Norvig. 2004).

A continuación se muestran dos métodos de búsqueda no informada:

- Búsqueda Primero en Anchura 
- Búsqueda Primero en Profundidad

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Bibliografía Complementaria

Berzal, F. s.f. Búsqueda en Inteligencia Artificial. DECSAI (Departamento de Ciencias de la Computación e I.A.). Universidad de Granada. Formato (PDF). Disponible en: http://elvex.ugr.es/decsai/iaio/slides/A3%20Search.pdf

Molina, J.; Torres, C. y Restrepo, C. 2008. TÉCNICAS DE INTELIGENCIA ARTIFICIAL PARA LA SOLUCIÓN DE LABERINTOS DE ESTRUCTURA DESCONOCIDA. Scientia et Technica Año XIV, No 39. Universidad Tecnológica de Pereira. ISSN 0122-1701. Formato (PDF). Disponible en: http://revistas.utp.edu.co/index.php/revistaciencia/article/viewFile/3171/1933

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf