Edit:
Vorgängerthemen:
(Weitere Themen folgen dazu nicht. )
Die Zeit drängt, ich muss das mit A Stern noch hinbekommen - darf nicht so flapsig damit umgehen…
static void aStern(Knot from, Knot to) throws InterruptedException, IOException {
LinkedList<Knot> closedlist = new LinkedList<>();
PriorityQueue<Knot> openlist = new PriorityQueue<>();
openlist.add(from);
String s = "";
for (Knot knot : openlist) {
s += "(" + knot.c + ",h=" + knot.h + "), ";
}
jl.setText(s);
Thread.sleep(5000);
nextSeque();
while (!openlist.isEmpty()) {
Knot k1 = openlist.remove();
closedlist.add(k1);
for (Kant kant : k1.n) {
Knot k2 = kant.k2;
if (!closedlist.contains(k2)) {
int newH = k1.h + kant.k;
if (k2.h == 0 || newH < k2.h) { // ?????????????????????????
k2.h = newH;
openlist.add(k2);
s = "";
for (Knot knot : openlist) {
s += "(" + knot.c + ",h=" + knot.h + "), ";
}
jl.setText(s);
Thread.sleep(5000);
nextSeque();
}
}
}
}
}
Wikipedia: A*-Algorithmus – Wikipedia :
// g-Wert für den neuen Weg berechnen: g-Wert des Vorgängers plus
// die Kosten der gerade benutzten Kante
tentative_g = g(currentNode) + c(currentNode, successor)
// wenn der Nachfolgeknoten bereits auf der Open List ist,
// aber der neue Weg nicht besser ist als der alte – tue nichts
if openlist.contains(successor) and tentative_g >= g(successor) then
continue
Problem: aStern
reiht den ersten Knoten ein, und macht anschließend danach gar nix, weil alle anderen hs (mit Luftlinie initialisiert) kleiner sich als newH
…
Man startet doch bei Start und sucht den Weg nach Ziel, oder? Oder hab ich etwas falsch verstanden?
Bei Wikipedia hat der Startknoten nicht den höchsten h-Wert? Mich verwirrt das.
Es wäre bestimmt nur eine kleine Änderung nötig…
Hier nochmal der Graph, gesucht ist der Weg von h nach d, h ist mit der Luftlinie initialisiert, die höheren und tatsächlichen Kosten stehen an den Kanten: