ALGORITMO A*

Para juegos simples unipersonales puede usarse el algoritmo A* (Hart, 1968). Este algoritmo implementa una búsqueda primero el mejor.

Se utiliza una función de evaluación estática f formada por:

f = g + h

• La función g es una función de coste de llegar del estado inicial al estado evaluado.
• La función h es una estimación del coste de llegar desde el estado evaluado al estado final u objetivo del juego.

En cada paso del algoritmo se selecciona el mejor nodo que no se ha expandido hasta el momento, es decir, aquel que tiene menor valor de función f. Este nodo se agrega a una lista de nodos explorados (NodosExplorados) y sus nodos sucesores se agregan a la lista de nodos pendientes de ser explorados (NodosNoExplorados).
El algoritmo A* es el siguiente: Estado_Inicial.g := 0;
Estado_Inicial.h := H(Estado_Inicial);
Estado_Inicial.f := Estado_Inicial.g + Estado_Inicial.h; NodosNoExplorados := Estado_Inicial;
NodosExplorados := Ø; Bool EncuentraEstadoFinal := FALSE; Mientras NOT EncuentraEstadoFinal AND NodosNoExplorados != Ø

EstadoActual := SeleccionarMejorNodo(NodosNoExplorados);
NodosExplorados := NodosExplorados + EstadoActual; Si EsEstadoFinal (EstadoActual) entonces
EncuentraEstadoFinal := TRUE;
Sino
Sucesores := CalcularSucesores (EstadoActual);
Para cada EstadoSucesor de Sucesores
EstadoSucesor.padre := EstadoActual;
EstadoSucesor.g: EstadoActual.g + Coste(EstadoActual,EstadoSucesor);
Si Pertenece(EstadoSucesor, NodosNoExplorados) entonces
EstadoViejo:=ExtraerNodo(EstadoSucesor, NodosNoExplorados);
EstadoActual.sucesores := EstadoActual.sucesores + EstadoViejo;
Si EstadoViejo.g > EstadoSucesor.g entonces
EstadoViejo.padre := EstadoActual;
EstadoViejo.g := EstadoActual.g;
EstadoViejo.f := EstadoViejo.g + EstadoViejo.h;
Fin si;
Sino si Pertenece(EstadoSucesor, NodosExplorados) entonces
EstadoViejo:=ExtraerNodo(EstadoSucesor, NodosNoExplorados);
EstadoActual.sucesores := EstadoViejo;
Si EstadoViejo.g > EstadoSucesor.g entonces
EstadoViejo.padre := EstadoActual;
EstadoViejo.g := EstadoActual.g;
EstadoViejo.f := EstadoViejo.g + EstadoViejo.h;
ActualizarSucesores(EstadoViejo);
Fin si;
Sino
NodosNoExplorados := NodosNoExplorados + EstadoSucesor;
EstadoActual.sucesores :=EstadoActual.sucesores + EstadoSucesor;
EstadoSucesor.f := EstadoSucesor.g + EstadoSucesor.h;
fin sino;
Fin para;
Fin sino;

Fin mientras;



tomado de http://dmi.uib.es/~abasolo/intart/2-juegos.html
imagen tomada de http://ensino.univates.br/~chaet/algoritmos.jpg