Una companyia alemanya vol incloure un cercador de vols a la seva pàgina web per permetre que els seus clients puguin trobar la combinació de vols més barata entre les ciutats on opera. És molt important que el cercador sempre retorni la solució òptima (la més barata) i que el temps que trigui a trobar la solució sigui raonable. 

Per a trobar la solució, es disposa dels preus dels vols que fa la companyia i s'ha definit una heurística que permet estimar el cost aproximat del viatge entre dues ciutats qualsevols a partir de la distància en línia recta entre les ciutats multiplicada per un preu per kilòmetre fix (heurística= (distància en línia recta) x (preu per km)).

A continuació teniu la matriu que mostra els preus dels vols que opera la companyia:

L’equip que està desenvolupant el cercador està considerant implementar l’algorisme A*. Per ajudar a l’equip desenvolupador, s’us demana que feu una simulació de la primera iteració de l’algorisme A* per calcular la ruta entre Stuttgart i Rostock.

Quin és el resultat de la primera iteració?