Ir al contenido principal

BÚSQUEDA HEURÍSTICA


BÚQUEDA HEURÍSTICA

Pattern de búsqueda avanzada en bases de datos académicasLa 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
Búsqueda Informada y explorada : Introducción | Inteligencia ...Elegir como siguiente nodo aquel con mayor función de evaluación.
•       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