Funciones heurísticas.
1 DE JULIO 2014Introducción
En esta clase el objetivo es mostrar cómo una
estrategia de
funciones
heurísticas
se emplea para que nos den información sobre la naturaleza de la heurística
general, para cual
tomaremos dos ejemplos de búsqueda heurística que desarrollaremos a
continuación.
Desarrollo
Funciones heurística
El efecto de la precisión heurística en el
rendimiento
Una manera de
caracterizar la calidad de una heurística es el b* factor de ramificación
eficaz. Si el número total de nodos generados por A* para un problema
particular es N, y la profundidad de la solución es d. entonces b* es
factor de ramificación que un árbol uniforme de profundidad d deberá tener
para contener N + 1 nodos. Así,
N+1=1+b*+
(b*)2+……….. (b*)
Por lo tanto,
las medidas experimentales de b* sobre un pequeño
conjunto de problemas pueden proporcionar una buena guía para la utilidad total
de la heurística. Una heurística bien diseñada tendría un valor de b cerca de 1,
permitiría resolver problemas bastante grandes.
Aprendizaje de heurísticas desde la experiencia
Una función heurística h(n), como
se supone, estima el costo de una solución que comienza desde el estado en el
nodo n.
Los métodos de aprendizaje
inductivos trabajan mejor cuando se les suministrar características de un estado que
sean relevante para su evaluación, más que sólo la descripción del estado.
A partir de
esto, se puede utilizar un algoritmo de aprendizaje inductivo para
construir una función h(n) que pueda predecir los costos solución para otros
estados que surjan durante la búsqueda. Las técnicas para hacer esto, está
basado en la utilización de redes neuronales, árboles de decisión. Y otros
métodos.
Conclusiones
El rendimiento de los algoritmos de búsqueda heurística depende de
la calidad de la función heurística. Las heurística se pueden construir a veces
por coste de solución, para sub-problemas
BIBLIOGRAFIA
˜Russell, S. Norvig, P. 2004. INTELIGENCIA A HTXFKCIAI, UN ENFOQIJE MUDERNO.2 ed. PEARSON EDUCACIONS,.S A. Formato PDF. Pag.130-150
No hay comentarios:
Publicar un comentario