Hallo, wer kann mir den A*-Algorithmus an einem praktischen Beispiel erklaeren?

da will mir wohl wieder jemand eine freizeitbeschäftigung schaffen ;)

ich schreib mal an einem beispiel wie man den algorithmus anwendet,
bei konkreten konzeptionellen fragen nachfragen..



man brauch einen graphen mit bewerteten kanten, implizit oder explizit spielt
keine rolle,

hier ist ein beispiel (aufmalen lohnt sich):

graph mit tatsächlichen entfernungen (auf kurvigen autostrassen, nicht originalgetreu ;) ):

wilster (41) - heide (58) 20 km

itzehoe (38) - wilster 8 km

itzehoe - hohenlockstedt 12 km

itzehoe - glückstadt 17 km

glückstadt (30) - elmshorn 12 km

elmshorn (22) - pinneberg 13 km

pinneberg (6) - stellingen 7 km

hohenlockstedt (34) - norderstedt 25 km

norderstedt (18) - altona 20 km

altona (4) - stellingen (0) 4 km



man möchte von itzehoe nach stellingen fahren in kürzester entfernung

schätzfunktion ist die luftentfernung,
die zahl in klammern bei jeder stadt oben soll geschätzte entfernung
zum ziel stellingen sein



der algorithmus beginnt mit itzehoe, itzehoe wird gewählt,
geschätze entfernung zu stellingen 38 km


randknoten sind wilster, hohenlockstedt und glückstadt,
bewertung dieser knoten:
wilster: weglaenge von itzehoe bis zum ziel= 8km fest + 41 km geschätzt = 49 km bewertet
hohenlockstedt: 12km fest + 34 km geschätzt = 46 km bewertet
glückstadt: 17km fest + 30 km geschätzt = 47 km bewertet


sieht also am günstigsten aus, wenn wir von hohenlockstedt aus weiterschauen,
diesen knoten nehmen wir in die liste der gewählten auf,
neuer randknoten ist norderstedt: 12km+25km fest + 18 km geschätzt = 55 km bewertet
ausserdem ja noch in der rankknotenliste:
wilster: 8km fest + 41 km geschätzt = 49 km bewertet
glückstadt: 17km fest + 30 km geschätzt = 47 km bewertet


günstigster unter den dreien ist nun glückstadt, fahren wir mal dahin,
kommt in die liste der gewählten,
neuer randknoten:
elmshorn: 17km+12km fest + 22 km geschätzt = 51 km bewertet

günstigster randknoten ist nun wilster:
neuer randknoten:
heide: 8km+20km fest + 58 km geschätzt = 86 km bewertet

so geht das immer weiter:
gewählt: elmshorn
neu: pinneberg: 17km + 12km + 13km fest + 6 km geschätzt = 48 km bewertet

gewählt: pinneberg
neu: stellingen: 17km + 12km + 13km + 7km = 49 km fest

ziel gefunden, optimale kürzeste entfernung = 49 km

vorteil gegeüber Dijksta: es werden nicht so viele unnötige knoten gewählt,
wie etwa heide in diesem graphen