Diferencia entre revisiones de «Inteligencia artificial para videojuegos/Estrategias de búsqueda informada»

Las estrategias de búsqueda informada se basan en aplicar un conocimiento al proceso de búsqueda para hacerlo mas eficiente. Este conocimiento o función no ayudara a estimar que camino o estado es mas prometedor, es decir que configuración esta mas cercana del objetivo final.

 

 

Del griego heuriskein, descubrir. En nuestro caso función que nos ayudara a acércanos al objetivo planteado.

La función heurística:

 

* Valor en el estado final igual a 0.

 

Analizar preferentemente los mejores nodos. Para saber cuales son los mejores utilizaremos una función heurística f para evaluarlos que estima el coste total de la función. Los ordenaremos de tal forma que el primer nodo será el que tenga la heurística mas baja. Por lo tanto estarán ordenados en función de f y no de g, que devuelve el coste de la raíz al nodo.

 

 

* Algoritmo que intenta llegar cuanto antes a la solución.

Sin embargo escogiendo una buena función heurística puede reducir mucho los costes.

 

Algoritmo basado en el primero el mejor que combina el coste directo de la raíz al nodo con la estimación del nodo al objetivo.

Es uno de los algoritmos más populares para encontrar caminos y grafos.

A diferencia de otras técnicas transversales, tienen "cerebros". Lo que significa es que es realmente un algoritmo inteligente que lo separa de los otros algoritmos convencionales.

Nosotros estaremos en un nodo inicial y debemos dirigirnos a un nodo final. En cada paso el resultado de la función del a* será igual a la suma de otros dos parámetros g y h, f = g + h. En cada paso elegirá el nodo cuya f sea la más baja.

Definamos ahora g y h:

 

Un ejemplo de esto son los mapas cuadriculados, donde los nodos iniciales y destino son casillas. Pueden existir casillas por las que no se pueden pasar, la gracia del a* es que las tiene en cuenta, al igual que casillas que supongan un mayor coste.

 

Hemos visto como g calcula el coste hasta el nodo.

Sin embargo como calculamos la heurística, h. Existen muchas heurísticas, algunas pueden partir del coste de subproblemas del problema original, otras parten de la experiencia de intentos fallidos.

 

* Hamming:

* Damerau-Levenshtein: