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
- 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
