Von h nach d:
- ol: (h,f=0,g=0),
cl: - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66),
cl: (h,f=0,g=0), - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99),
cl: (h,f=0,g=0), (e,f=143,g=30), - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99),
cl: (h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99),
cl: (h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99), (a,f=216,g=159),
cl: (h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99), - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99), (a,f=216,g=159), (b,f=228,g=192), (d,f=240,g=240), (g,f=294,g=221), (f,f=271,g=220),
cl: (h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99), (a,f=216,g=159), - ol: (
h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99), (a,f=216,g=159), (b,f=228,g=192), (d,f=231,g=231), (g,f=294,g=221), (f,f=271,g=220),
cl: (h,f=0,g=0), (e,f=143,g=30), (j,f=157,g=22), (i,f=164,g=66), (c,f=191,g=99), (a,f=216,g=159), (b,f=228,g=192),
Von c nach d (damit das hier nicht unendlich lang ist):
- ol: (c,f=0,g=0),
cl: - ol: (
c,f=0,g=0), (a,f=117,g=60), (i,f=134,g=36), (e,f=182,g=69),
cl: (c,f=0,g=0), - ol: (
c,f=0,g=0), (a,f=117,g=60), (i,f=134,g=36), (e,f=182,g=69), (b,f=129,g=93), (f,f=172,g=121), (g,f=195,g=122), (d,f=141,g=141),
cl: (c,f=0,g=0), (a,f=117,g=60), - ol: (
c,f=0,g=0), (a,f=117,g=60), (i,f=134,g=36), (e,f=182,g=69), (b,f=129,g=93), (f,f=172,g=121), (g,f=195,g=122), (d,f=132,g=132),
cl: (c,f=0,g=0), (a,f=117,g=60), (b,f=129,g=93), - ol: (
c,f=0,g=0), (a,f=117,g=60), (i,f=134,g=36), (e,f=182,g=69), (b,f=129,g=93), (f,f=172,g=121), (g,f=195,g=122), (d,f=132,g=132), (j,f=241,g=106), (h,f=237,g=102),
cl: (c,f=0,g=0), (a,f=117,g=60), (b,f=129,g=93), (i,f=134,g=36),
Richtiger?
Code:
static void aStern(Knot from, Knot to) throws InterruptedException,
IOException {
LinkedList<Knot> closedlist = new LinkedList<>();
PriorityQueue<Knot> openlist = new PriorityQueue<>();
openlist.add(from);
setText(closedlist, openlist);
while (!openlist.isEmpty()) {
Knot k1 = openlist.remove();
closedlist.add(k1);
setText(closedlist, openlist);
if (k1.equals(to)) {
return;
}
for (Kant kant : k1.n) {
Knot k2 = kant.k2;
if (!closedlist.contains(k2)) {
int newG = k1.g + kant.kosten;
if (!openlist.contains(k2) || newG < k2.g) { // !!!!!!!!!!!!
/* (an dieser Stelle Vorgänger setzen) */
k2.g = newG;
k2.f = newG + k2.h;
openlist.add(k2);
setText(closedlist, openlist);
}
}
}
}
setText(closedlist, openlist);
}
kant.kosten -> tatsächliche Kosten einer Kante
g -> tatsächliche Kosten des Wegs
f -> geschätzte Restkosten?
Es gilt: kosten <= g <= f ???