AEstrella

Algoritmo A*

Definición de la función evaluación. Utilización de las distancias.

f(n): Función de evaluación.

f(n)= g(n)+h(n)

g(n): Es el coste del camino recorrido desde el inicial a n. Ennuestro caso será la
h(n):

distancia por carretera.

Representa el valor heurístico del nodo a evaluar, desde el actual n hasta el final. Es decir, estima la distancia a la
meta desde el nodo n. Ennuestro caso será la distancia aérea, que consideramos función admisible ya que nunca superará la
distancia real para todo n .

Grafo Inicial

Ejecución paso a paso del Algoritmo A*.
A continuación seilustrarán paso a paso las expansiones de los nodos, resultado de la ejecución del algoritmo, así como, la
evolución de las listas Interior y Frontera.

Frontera

0
1
2
3
4
5
6

InteriorPalencia(0+580=580)

Vacio

Madrid(239+550=789), Santander(203+605=808) , Cáceres(368+850=1218)

Palencia

Santander(203+605=808), Zaragoza(322+239+275=836), Valencia(350+239+303=892),
Cáceres(368+850=1218)Bilbao(111+203+502=816), Zaragoza(322+239+275=836), Valencia(350+239+303=892),
Cáceres(368+850=1218)

Palencia, Madrid
Palencia, Madrid, Santander

Zaragoza(322+239+275=836), Valencia(350+239+303=892),Cáceres(368+850=1218)

Palencia, Madrid, Santander, Bilbao

Barcelona (299+322+239=860), Valencia (350+239+303=892), Cáceres (368+850=1218)

Palencia, Madrid, Santander, Bilbao, Zaragoza

Valencia(350+239+303=892) , Cáceres (368+850=1218)

Palencia, Madrid, Santander, Bilbao, Zaragoza,
Barcelona

0

Palencia
580

Frontera
Palencia (0+850)
Interior
Vacio

Palencia
580

1
203

Santander
605

239
368Cáceres
850

Frontera
Madrid(239+550=789), Santander(203+605=808) Cáceres(368+850=1218)
Interior
Palencia

Madrid
550

2
Palencia
580
203

Santander
605

239
368

Cáceres
850

299

322

Zaragoza
275Madrid
550
350

Valencia
303

Frontera
Santander(203+605=808), Zaragoza(322+239+275=836), Valencia(350+239+303=892), Cáceres(368+850=1218)
Interior
Palencia, Madrid

3
Palencia
580
203

Santander...