Enciclopedia/Diccionario de Psicología y Neurociencias:
ıllı Heurística admisible wiki: info, libros pdf y vídeos
- Detalles
- Categoría: PSICOLOGIA (WIKINFO)
Heurística admisible
Una heurística aceptable es utilizada para querer el costo de lograr el estado objetivo en un algoritmo de busca informada. Una heurística va a ser aceptable para determinado inconveniente de busca cuando el costo estimado sea siempre y en todo momento menor o bien igual que el costo mínimo de lograr el estado objetivo. El algoritmo de busca utiliza la heurística para localizar una estimación del camino inmejorable hasta el propósito desde el nodo actual. Por poner un ejemplo, uno de los algoritmos de busca más populares es el A* (en inglés A-Star Search). En este la función de evaluación para n, donde n es el nodo actual, es así: f(n)=g(n)+h(n) donde: h(n) es calculado utilizando una función heurística. Con una heurística no aceptable, el algoritmo A* podría pasar por alto la solución inmejorable a lo largo de la busca debido a una sobreestimación de f(n). Las heurísticas aceptables son por su naturaleza optimistas, por el hecho de que creen que el costo de solventar el inconveniente es menor que el que verdaderamente es. Como g(n) es el costo preciso de lograr n, tenemos como consecuencia inmediata que f(n) jamás sobreestima el costo auténtico de la solución mediante n. De estar h(n) definida por una heurística aceptable, el algoritmo de busca A* va a devolver una solución inmejorable. Por ejemplo, si se quiere solucionar el quince-rompecabezas (o bien juego del quince) en la menor cantidad de pasos posible utilizando A*, es preciso emplear una heurística aceptable. Hay una larga historia de semejantes heurísticas para el quince-rompecabezas, acá tenemos 2 de las más generalmente usadas: Queda claro que la Distancia de Hamming es aceptable, puesto que el total de movimientos para ordenar las fichas apropiadamente es cuando menos el número de fichas que no están en su sitio (si cada ficha no está en su situación original habrá de ser movida cuando menos una vez).La Distancia Manhattan asimismo va a ser una heurística aceptable pues cada ficha va a ser movida el menos la cantidad de pasos entre ella misma y su situación original. Considere el próximo rompecabezas: la distribución de las distancias Manhattan para cada ficha quedaría así: La distancia total de Manhattan para el rompecabezas quedaría: h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36 Una heurística aceptable puede derivar de una versión simplificada del inconveniente, o bien por información desde un patrón de base de datos que almacene la solución precisa de un inconveniente, o bien utilizando aprendizaje inductivo.Por ejemplo, del quince-rompecabezas visto previamente, podemos acotar 3 inconvenientes más simples:La regla del juego original es "Una ficha se puede desplazar desde la casilla A hasta la casilla B si A es lindante a B y B está vacía". Se pueden producir 3 inconvenientes quitando una o bien las dos condiciones: De 1) podemos derivar la Distancia Manhattan, de dos) podemos derivar otra heurística famosa como La heurística de Gaschnig y de tres) podemos derivar la Distancia de Hamming. La idea tras el patrón de base de datos es guardar los costos de las soluciones precisas de cada posible instancia de un sub-inconveniente, en nuestro ejemplo las instancias de sub-inconvenientes podrían ser ocho casillas y el espacio en blanco o bien siete casilla y el espacio en blanco. Por poner un ejemplo (1-dos-tres-cuatro-cinco-seis-siete-ocho) y (nueve-diez-once-doce-trece-catorce-quince). Si las casillas escogidas no se repiten en 2 sub-inconvenientes (o bien dicho por lo general, no hay solapamiento en 2 sub-inconvenientes), podemos crear una heurística aceptable que sea la suma de los dos costos guardados en la base de datos. Utilizando esta heurística se resolvería el quince-puzle en unos pocos milisegundos, el número de nodos generados se reduce en diez equiparado con como cuando se utiliza la distancia Manhattan. Si se tiene de una heurística aceptable, la que mejor funcione será la de mayor valor, es decir, la que mejor aproxime la solución inmejorable real sin exceder su valor. De ahí si tenemos múltiples heurísticas aceptables y no sabemos cuál escoger, podemos crear una nueva que sea el máximo de todas las demás. Mientras que todas y cada una de las heurísticas consistentes son aceptable, no todas y cada una de las heurísticas aceptables son consistentes.Una heurísticah(n) es consistente si, para todo nodo n y todo sucesor n' de n generado por cualquier acción A, el costo estimado de lograr la meta desde n no es mayor que el costo de conseguir n' más el costo estimado de conseguir la meta desde n': h(n)=c(n,A,n')+h(n') Para inconvenientes de busca en árbol, si una heurística aceptable es utilizada, el algoritmo A* jamás va a devolver un nodo objetivo subóptimo.
