BÚQUEDA HEURÍSTICA
La búsqueda heurística
consiste en añadir información, basándose en el espacio estudiado hasta ese
momento, de forma que se restringe drásticamente esa búsqueda.
Las heurísticas son
formalizadas como reglas para elegir (buscar) las ramas en el espacio de
estados que son más probables de llegar a una solución aceptable del problema.
MÉTODOS DE BÚSQUEDA HEURÍSTICA
Los métodos de búsqueda
heurística disponen de alguna información sobre la proximidad de cada estado a
un estado objetivo, lo que permite explorar en primer lugar los caminos más
prometedores.
MÉTODOS HEURÍSTICOS
En general, 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.
La información del problema
concreto que estamos intentando resolver se suele expresar por medio de
heurísticas.
CARACTERÍSTICAS
FUNCIÓN HEURÍSTICA
Se trata de una función que
asocia a cada estado del espacio de estados una cierta cantidad numérica que
evalúa de algún modo lo prometedor que es ese estado para acceder a un estado
objetivo. Habitualmente, se denota esa función por h(e).
La función heurística puede
tener dos interpretaciones. Por una parte, la función puede ser una estimación
de lo próximo que se encuentra el estado de un estado objetivo. Bajo esta
perspectiva, los estados de menor valor heurístico son los preferidos. Pero en
otros casos puede suceder que lo que convenga sea maximizar esa función.
ESTRATEGIAS DE BÚSQUEDA
HEURÍSTICA
Tipos
• Estrategias
tentativas: aquellas en las que se puede abandonar la
exploración de una rama y pasar a explorar otra en cualquier momento del
problema.
• Estrategias
irrevocables: aquellas en las que no se puede abandonar la
exploración de la rama por la que se comenzó.
Métodos:
• Gradiente
• Primero
el mejor
• Búsqueda
en haz
• Algoritmo
A
GRADIENTE
Elegir el camino de máxima
pendiente, usando para ello la función de evaluación.
• Ventajas:
Se
llega a la solución con poco coste computacional.
• Inconvenientes: Puede ser que el problema no
sea compatible con este método, y, por lo tanto, no conseguiremos obtener la
solución.
• En
este caso, se generan todos los hijos de un estado, se calculan sus valores
heurísticos y se determina uno de los estados de mejor valor heurístico; se
compara dicho valor con el del estado expandido y si es mejor, se devuelve ese
estado como expansión.
PRIMERO EL MEJOR
• Ventajas: No depende en exceso de la
función de evaluación.
• Inconvenientes: Excesiva
complejidad espacial, pues se deben guardar todos los nodos abiertos.
BÚSQUEDA EN HAZ
Elegir un conjunto de nodos
como los siguientes a expandir, y hacerlo de forma irrevocable.
• Ventajas:
Más
permisible.
• Inconvenientes:
En
caso de que el sistema sea irrevocable, este método no actúa con eficacia.
ALGORITMO “A”
Ponderar a la vez lo cerca que
estamos del nodo meta y lo lejos que estamos del nodo inicial.
• Ventajas: Soluciones más cercanas a la
raíz.
• Inconvenientes:
La
función de evaluación se complica.
Definiremos una función
heurística f como la suma de dos funciones g y h:
Función g: Es una
medida del coste para ir desde el estado inicial hasta el nodo actual (suma de
los costes o valores heurísticos de todos los nodos).
Función h: Es una
estimación del coste adicional necesario para alcanzar un nodo objetivo a
partir del nodo actual, es decir, es una estimación de lo que me queda por
recorrer hasta la meta.
La función combinada f una
estimación del coste necesario para alcanzar un estado objetivo por el camino
que se ha seguido para generar el nodo actual (si se puede generar por varios
caminos el algoritmo se queda con el mejor).
NOTA: Los nodos buenos deben
poseer valores bajos.
FUENTE
• Silva
José M. (2016). Criterios de Busqueda en I.A. mayo 07,2020, de
SlideShare Sitio web: https://www.slideshare.net/jozsemanuel/criterios-de-busqueda-en-ia
• Malagón,Constantino.
(Sin fecha). Búsqueda heurística. mayo 07,2020, de nebrija Sitio web: https://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_heuristica.pdf
• Ramírez,J.
(Sin fecha). Métodos Heurísticos en Inteligencia Artificial. mayo,07,2020,
de kali Sitio web: http://kali.azc.uam.mx/clc/03_docencia/posgrado/i_artificial/8_FuncionesHeuristicas.pdf



Comentarios
Publicar un comentario