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 masmás eficiente. Este conocimiento o función nonos ayudaraayudará a estimar quequé camino o estado es masmás prometedor, es decir quequé configuración estaestá masmás cercana del objetivo final.

Del griego heuriskein, descubrir. En nuestro caso es la función que nos ayudaraayudará a acércanosacercarnos al objetivo planteado.

Analizar preferentemente los mejores nodos. Para saber cualescuáles 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.

* La complejidad espacio-temporal es de 0(r ^m), donde ''r'' es el factor de ramificación y ''m'' la profundidad del árbol de búsqueda.

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

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

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 aA* 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'':

'''g''' = el movimientocuánto cuesta moverse desde el punto inicial a un nodo dado, siguiendo la ruta generada para llegar allí.

'''h''' = el coste del movimiento estimado para pasar de ese nodo dado al destino final.Esto a menudo se conoce como la heurística, que no es más que una especie de suposición inteligente. Realmente no sabemos la distancia real hasta que encontramos el camino.

La cola a la hora de ir sacando nodos irairá de menor a mayor ''f'', siendo el nodo con menor ''f'' el nodo más prometedor.

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

Hemos visto como ''f'' es la función que evalúa el coste total de la función.

laHemos funciónvisto quecomo evalúa''g'' calcula el coste totalhasta de lael funciónnodo.

CuandoCuándo usarla:

CuandoCuándo usarla:

CuandoCuándo usarla: