A _Star einführen
A_Star-Algorithmus („A Stern“ oder englisch „a star“, auch _Star-Suche) gehört zur Klasse der informierten Suchalgorithmen.
A-Star 算法是一种常用的路径查找和图形遍历算法，起初发表于1968年，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。
对比Dijkstra 算法的优点，在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径。基于评估函数。
Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten.
两个点： zwei Knoten
der A_Star-Algorithmus eine verwendet Schätzfunktion (Heuristik),um zielgerichtet zu suchen und damit die Laufzeit zu verringern. Der Algorithmus ist vollständig und optimal.
A_Star 算法总是先研究最可能快速到达目标的节点。
Der A_Star-Algorithmus untersucht immer die Knoten zuerst, die wahrscheinlich schnell zum Ziel führen.
f(x) = g(x)+h(x)
节点：der Knoten
x ist ein Knoten,
g(x) [g von x] ist die bisherigen Kosten vom Startknoten.
h(x) ist die geschätzten Kosten von x bis zum Zielknoten.
Die verwendete Heuristik darf die Kosten nie überschätzen. Für das Beispiel der Wegsuche ist die Luftlinie eine geeignete Schätzung: Die tatsächliche Strecke ist nie kürzer als die direkte Verbindung.
使用的启发方法绝对不能高估成本，对于寻路例子，直线是一个很好的估计，因为实际距离永远不会比直接连接更短。
Die Knoten werden während der Suche in drei verschiedene Klassen eingeteilt:
节点在寻找过程中会被分配给三个集合。
1.unbekannte Knoten ：Diese Knoten wurden während der Suche noch nicht gefunden.
2.bekannte Knoten ：Zu diesen Knoten ist ein (möglicherweise suboptimaler) Weg bekannt.
Alle bekannten Knoten werden zusammen mit ihrem f-Wert in der sogenannten Open List gespeichert.
3.abschließend untersuchte Knoten： Zu diesen Knoten ist der kürzeste Weg bekannt. Die abschließend untersuchten Knoten werden in der sogenannten Closed List gespeichert, damit sie nicht mehrfach untersucht werden.
Jeder bekannte oder abschließend besuchte Knoten enthält einen Zeiger auf seinen (bisher besten) Vorgängerknoten. Mit Hilfe dieser Zeiger kann der Pfad bis zum Startknoten rückverfolgt werden.
每一个已知的或者结束被寻找的节点，都有一个指向其前一个点的指针，通过这个指针，可以找到一个到达起始点的路径。
Wird ein Knoten x abschließend untersucht (auch expandiert oder relaxiert), so werden seine Nachfolgeknoten in die Open List eingefügt und x in die Closed List aufgenommen.
Für neu eingefügte Nachfolgeknoten werden die Vorgängerzeiger auf x gesetzt. Ist ein Nachfolgeknoten bereits auf der Closed List, so wird er nicht erneut in die Open List eingefügt und auch sein Vorgängerzeiger nicht geändert.
对于新插入的后继节点，先前的指针设置为 x。 如果后继节点已经在关闭列表中，则不会再次将其添加到打开列表中，也不会更改其前驱指针。
Ist ein Nachfolgeknoten bereits auf der Open List, so wird der Knoten nur aktualisiert (f-Wert und Vorgängerzeiger), wenn der neue Weg dorthin kürzer ist als der bisherige.
如果继任节点已经在开放列表中，如果那里的新路径比以前的短，该节点才会被更新(f值和继任指针)。
Es gibt zwei Möglichkeiten, diesen Algorithmus zu terminieren.
Falls der Zielknoten abschließend untersucht wird, terminiert der Algorithmus. Der gefundene Weg wird mit Hilfe der Vorgängerzeiger rekonstruiert und ausgegeben.
Falls die Open List leer ist, gibt es keine Knoten mehr, die untersucht werden könnten. In diesem Fall terminiert der Algorithmus, da es keine Lösung gibt.
Beispiel
地图介绍 Landkarte einführen
Landkarte als Graph
weiß: noch nicht gefunden
grau: gefunden, befindet sich auf der Open List
schwarz: untersucht, befindet sich auf der Closed List
其中 h 是每一个城市到目标点的直线距离， 权值是实际距离。
Das Diagramm zeigt eine kleine Auswahl an Städten und Wegen. Die Kantenbeschriftung entspricht den Kosten, um von einer Stadt zur nächsten zu kommen. Jeder Knoten enthält die geschätzte Entfernung zum Zielknoten (Wert der h-Funktion). Als Heuristik wird hier die Luftlinie verwendet.
h: geschätzte Entfernung
Schritt 1
从起始点出发，开始计算 f 值,
$f_{kl}$ = g(Sa)+Gewichtung(70)+h(158) = 228 Kaiserslautern wird in die Open List eingefügt.
$f_{ka}$ = g(Sa)+Gewichtung(145)+h(140) = 285 Karlsruhe wird in die Open List eingefügt.
Saarbrücken hat nur zwei Niederlassungen.Und die alle haben auf Saarbrücken hingewiesen.
Saarbrücken 只有两个分支，并且全部指向Saarbrücken。 则把Saarbrücken 放入 Closed List。
Der Knoten Saarbrücken ist nun abschließend betrachtet und wird auf die Closed List gesetzt.
openList = [ $f_{kl}$=228 , $f_{ka}$=285 ]
closeList = [ Saarbrücken ]
Schritt 2
Die Open List enthält nun zwei Punkte.
openList = [ $f_{kl}$=228 , $f_{ka}$=285 ]
closeList = [ Saarbrücken ]
$f_{kl}$ ist kleiner. Da Kaiserslautern den geringeren f-Wert hat, wird nun Kaiserslautern als Nächstes untersucht und seine Nachfolgeknoten betrachtet.
- Saarbrücken ist bereits auf der Closed List und wird nicht weiter betrachtet.
- Frankfurt wird mit $f_{F}$=g(KL)+c(KL,F)+h(F)=70+103+96=269 in die Open List eingefügt. Kaiserslautern wird als Vorgängerknoten gespeichert.
- Ludwigshafen wird mit $f_{LU}$=g(KL)+c(KL,LU)+h(LU)=70+53+108=231 in die Open List eingefügt. Kaiserslautern wird als Vorgängerknoten gespeichert.
- Kaiserslautern wird auf die Closed List gesetzt.
openList = [ $f_{ka}$=285 ,iserslautern]
Schritt 3
Der Knoten mit dem geringsten f-Wert ist Ludwigshafen.
openList = [$f_{ka}$=285 , $f_{F}$=269 , $f_{LU}$=231 ]
closeList = [ Saarbrücken,Kaiserslautern ]
- Kaiserslautern ist bereits auf der Closed List und wird nicht weiter betrachtet.
- Der Zielknoten Würzburg wird gefunden, aber noch nicht als Lösung ausgegeben, sondern zunächst in die Open List eingefügt. Ludwigshafen wird als Vorgängerknoten gespeichert.
- Ludwigshafen wird auf die Closed List gesetzt.
openList = [ $f_{ka}$=285 , $f_{F}$=269 , $f_{Wür}$=306 ]
closeList = [ Saarbrücken,Kaiserslautern,Ludwigshafen]
Schritt 4
openList = [ $f_{ka}$=285 , $f_{F}$=269 , $f_{Wür}$=306 ]
closeList = [ Saarbrücken,Kaiserslautern,Ludwigshafen ]
Frankfurt wird erkundet. Als einziger Nachfolgeknoten, der sich noch nicht auf der Closed List befindet, wird Würzburg gefunden. Als f-Wert wird 289 berechnet, was geringer als der bisherige f-Wert für Würzburg ist. Dies bedeutet, dass der Weg über Frankfurt kürzer ist als der zuerst gefundene Weg über Ludwigshafen. Daher wird der f-Wert von Würzburg geändert. Außerdem wird als Vorgängerknoten nun Frankfurt gespeichert.
Frankfurt wird auf die Closed List gesetzt.
openList = [ $f_{ka}$=285 , $f_{Wür}$=306 ]
closeList = [ Saarbrücken,Kaiserslautern,Ludwigshafen,Frankfurt ]
Schritt 5
openList = [ $f_{ka}$=285 , $f_{Wür}$=306 ]
closeList = [ Saarbrücken,Kaiserslautern,Ludwigshafen,Frankfurt ]
Da Karlsruhe nun den kleinsten f-Wert hat, wird dieser Knoten als Nächstes untersucht. Heilbronn wird in die Open List eingefügt und Karlsruhe auf die Closed List gesetzt.
openList = [ $f_{Wür}$=306 , $f_{Heilbronn}$ =316 ]
closeList = [ Saarbrücken,Kaiserslautern,Ludwigshafen,Frankfurt,Karlsruhe ]
Schritt 6
openList = [ $f_{Wür}$=306 , $f_{Heilbronn}$ =316 ]
closeList = [ Saarbrücken,Kaiserslautern,Ludwigshafen,Frankfurt,Karlsruhe ]
Jetzt hat Würzburg den geringsten f-Wert und wird untersucht: Das Ziel ist gefunden und der kürzeste Weg ist: Saarbrücken–Kaiserslautern–Frankfurt–Würzburg.
A wird auf B zeigen: A 将会指向B
