A*-Implementierung ist fehlerhaft


#1

Edit:
Vorgängerthemen:





(Weitere Themen folgen dazu nicht. :wink: )


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: https://de.wikipedia.org/wiki/A*-Algorithmus#Funktionsweise :

        // 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:


#2

wie schon früher: warum ein völlig anderes Beispiel und nicht genau das aus Wiki mit Saarbrücken & Co. manuell zusammengebaut?
dann könnte jeder, auch du selber, jeden Schritt exakt nach bekannter Korrektheit verfolgen,

“Karlsruhe wird mit 0 + 145 + 140 = 285 eingetragen”, alles Werte die du nachvollziehen musst, perfekt einzeln korrekt vorgegeben,
so mit neuer Karte hast du (und andere, die dir helfen sollen!) unnötig neue Komplexität, tausend mögliche Fehler die dir unbekannt entgehen können


und wie schon früher: ‘newH = k1.h + kant.k’ ist falsch,
tentative_g ist der Weg vom Start aus, Kantenwert + bisheriger Weg, hat nichts mit h zu tun,

freilich gibt es auch noch f, die angepasste Schätzung des Wegs insgesamt pro Zwischenknoten, nicht nur dessen der Heuristik-Wert h, sondern auch der (beste) Weg dorthin


“Bei Wikipedia hat der Startknoten nicht den höchsten h-Wert?”
im Saarbrücken-Beispiel schon, aber was macht schon eine unbegründete unsinnige Aussage mehr oder weniger…,
das berechnete f der Zwischenknoten ist freilich höher als h am Anfang, ganz normal, dafür muss man den Algorithmus verstehen…

wobei es auch nicht schlimm wäre, wenn andere höheren h-Wert hätten,
in größeren Beispielen wäre das für alle Knoten in die falsche Richtung der Fall,
etwa wenn die Karte mit Saarbrücken nach Würzburg auch noch paar französische Städte im Westen hätte, nichts verwirrend dran,
hohes h zeigt nur dass dann nicht unnötig nach dort zu schauen, wie Dijkstra es machen würde


#3

Hab es doch noch hinbekommen, jetzt rennt er :blush: :

    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 = "openlist: ";
        for (Knot knot : openlist) {
            s += "(" + knot.c + ",h=" + knot.h + "), ";
        }
        s += "closedlist: ";
        for (Knot knot : closedlist) {
            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 (!openlist.contains(k2) || newH < k2.h) { // !!!!!!!!!!!!
                        k2.h = newH;
                        openlist.add(k2);

                        s = "openlist: ";
                        for (Knot knot : openlist) {
                            s += "(" + knot.c + ",h=" + knot.h + "), ";
                        }
                        s += "closedlist: ";
                        for (Knot knot : closedlist) {
                            s += "(" + knot.c + ",h=" + knot.h + "), ";
                        }
                        jl.setText(s);
                        Thread.sleep(5000);
                        nextSeque();

                    }

                }
            }
        }

        s = "openlist: ";
        for (Knot knot : openlist) {
            s += "(" + knot.c + ",h=" + knot.h + "), ";
        }
        s += "closedlist: ";
        for (Knot knot : closedlist) {
            s += "(" + knot.c + ",h=" + knot.h + "), ";
        }
        jl.setText(s);
        Thread.sleep(5000);
        nextSeque();

    }

Ich musste die Bedingung einfach nur verneinen, also: Mache nur etwas, wenn Nachfolger nicht in der opnelist ist ODER wenn (er da schon drin ist und) newH kleiner ist als das schonmal berechnete h des Nachfolgers.

Dann setze h usw.

Animation:

(Vielleicht GIF downloaden und Frame/Sequenz für Sequenz abspielen… falls möglich)


Anmerkung: Das wird nicht die beste in Java existierende Implementierung sein, aber ich kann die Schritte endlich mal nachvollziehen. :slight_smile:


#4

Einzelne Schritte nochmal in Textform, mit Farben - vom Forum nicht erlaubt - wäre es übersichtlicher:

  1. openlist: (h,h=135), closedlist:
  2. openlist: (h,h=135), closedlist: (h,h=135),
  3. openlist: (h,h=135), (j,h=157), closedlist: (h,h=135),
  4. openlist: (h,h=135), (j,h=157), (e,h=165), closedlist: (h,h=135),
  5. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), closedlist: (h,h=135),
  6. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), closedlist: (h,h=135), (j,h=157),
  7. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), closedlist: (h,h=135), (j,h=157), (e,h=165),
  8. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), closedlist: (h,h=135), (j,h=157), (e,h=165),
  9. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201),
  10. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234),
  11. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234),
  12. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294),
  13. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294),
  14. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294),
  15. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294),
  16. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=375), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294),
  17. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=375), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327),
  18. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327),
  19. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355),
  20. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356),
  21. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366),
  22. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), (d,h=366),
  23. openlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), closedlist: (h,h=135), (j,h=157), (e,h=165), (i,h=201), (c,h=234), (a,h=294), (b,h=327), (f,h=355), (g,h=356), (d,h=366), (d,h=366),

Distanz Knotens auf der openlist kann sich aktualisieren… Eines auf der closedlist aber nicht.
Den Übergang von Schritt 20. zu 21. verstehe ich nicht nicht, d wird der closedlist hinzugefügt, aber nicht der openlist entfernt?
Schritt 22. und 23. ist identisch


#5

für den Fall dass weniger Antworten von anderen weil ich zuerst geantwortet hatte noch einen Beitrag:
was ist die Liste 1-23?
durchgestrichene Angaben oder überhaupt früherer Inhalt der Listen geben die Ausgaben im Code nicht her,

hast du das selber zusammengestellt?, aber auf welche Grundlage, warum sollte man da an Korrektheit glauben?


der Code gibt nicht viel her, zumal Rest unbekannt,
unbrauchbar das Forum zukleisternd über mehrere Threads verteilt vielleicht,
aber auch dort ja selten aktuell und sucht niemand zusammen,

generell, zum 1000. Mal für dich erwähnt, kann man aber natürlich jeden Code debuggen,
du musst nur mehr Ausgaben einbauen,
"entferne nun Knoten … aus openList, openList ist danach: … "
"untersuche n Kanten zu Knoten … "
“untersuche Kante Nummer … Kante = …”
“zweiter Knoten in Kante ist … ist in closedList enthalten? true/ false”

“füge Knoten … nun (mit neuen h … ) in openList ein, openList ist nun …”
usw., keine Frage zum aktuellen Ablauf kann offen bleiben


davon abgesehen ist der Algorithmus weiterhin im Moment unbrauchbar,
h wird bei A* einfach nie neuberechnet,

was wäre überhaupt die Aussage am Ende? welcher Weg, welche Kosten?
du hast zu Weg aus Nachfolge-Knoten usw. noch gar nichts eingebaut,
nur beliebig Listen gefüllt und geleert und bedeutungsloses h berechnet,

mit A* hat das noch nicht viel zu tun,
bisschen wie bei DNA: so wie man mit 99% der DNA des Menschen einen Delphin oder was auch immer haben kann,
kann man auch einen Algorithmus mit openList und closedList bauen und bei etwas völlig anderen als A* landen


#6

Bist du dir da sicher? IICS/if I understand correctly, darf der h-Wert überschrieben werden, während des Algorithmuses:

        // 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)
        g(successor) = tentative_g

h ist quasi der obige g-Wert.


Mit dem/den Vorgänger-Knoten hast du recht:

        successor.predecessor := currentNode

Das ist eine Zeile einzubauen… Aber er funktioniert auch so prächtig, alle relevanten Zwischenschritte berechnet er (nur der eigentliche Weg, der gesucht werden soll, ist unwichtig. :wink: )

Mir geht es um die Zwischenschritte.


Das wäre zu welcher Weg, jetzt zu welche Kosten… MMn. findet er zwar den kürzesten Weg, aber nicht auf Basis der echten Kosten. Also ist der h-Wert quasi ein Phantasiewert, höher der tatsächlichen Kosten.

Der Weg und die tatsächlichen Kosten ließe sich berechnen, wenn man einmal den Vorgängern folgt (also in (n) oder sogar (1), sozusagen).


Fällt dir noch etwas auf? Danke für alle Beobachtungen. :slight_smile:

Anmerkung: Zukleistern wollte ich es nicht, ich füge, der bessern Übersicht wegen, Verlinkungen zu den anderen Themen in den ersten Beitrag nachträglich ein.


#7

Ich denke mal, das Slater dir nur sagen will, dass sich die Abstände/Kosten (h) zwischen den einzelnen Stationen (Knoten) ja nicht ändern. Du aber speicherst immer die errechneten Gesamtkosten einer Strecke (newH) in einem Knoten (kn.h). Btw. nichtmal in einer Kante, was, wenn überhaupt, eigentlich der Fall sein müsste, weil Knoten (Punkte) nunmal keine Länge haben.


#8

‘h ist quasi der obige g-Wert.’ sagt es durchaus, unnötig mit h vom Startknoten begonnen pro Kante erhöht speicherst du nur noch den bisherigen Weg (durchaus im Knoten abzulegen),
damit verwendest du keine Heuristik mehr, sondern breitest dich die Dijkstra aus, erster Knoten in openList ist immer der mit kleinen Weg vom Start aus,
nicht mit bester Abschätzung zum Ziel für Gesamtweg (bisheriger bekannter Weg + Heuristik-Abschätzung)

dahingehend sind Beispiele ohne großen Suchraum, auch in die entgegengesetzte Richtung, wie deins aber genauso auch Saarbrücken in Wiki, gefährlich,
man sieht falsches Vorgehen nicht so gut, im Wiki steht es zumindest auch mit dran:

“Dieses Beispiel dient lediglich dem Verständnis der Funktionsweise des Algorithmus. Die Besonderheit des zielgerichteten Suchens wird hier nicht deutlich, da alle Knoten im Bereich der direkten Verbindungslinie Saarbrücken–Würzburg liegen.”


‘h wie g’ wäre sowieso schlecht, warum nicht g g lassen und h h lassen sondern alles zur Unkenntlichkeit vermischen?


#9

Von h nach d:

  1. ol: (h,f=0,g=0),
    cl:
  2. 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),
  3. 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),
  4. 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),
  5. 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),
  6. 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),
  7. 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),
  8. 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):

  1. ol: (c,f=0,g=0),
    cl:
  2. 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),
  3. 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),
  4. 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),
  5. 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 ???


#10

aus den Zahlenkolonnen kann ich nichts herauslesen,
der Algorithmus ist nun schon ziemlich nahe am Wiki, fast 1:1 alle Befehle, das hättest du schon vorher haben können,

das Hinzufügen zur openList ist im Wiki aber bedingt, schau es dir nochmal an,

auch ist nicht zu erkennen ob bei dir openlist sich in der Priorität nach f richtet


#11

Das tut es:


    @Override
    public int compareTo(Knot o) {
        if (f == o.f) {
            return c - o.c;
        }
        return Integer.compare(f, o.f);
    }

(Bin später wieder zurück…)


Welche Variablen wären denn wichtig für die Zwischenschritte?


#12

was f ist usw. steht auch im Wiki unter ‘Idee des Algorithmus’, sollte eigentlich vor Implementierung klar sein…,

an Nebenthemen wie ‘wichtig für Zwischenschritte’ möchte ich mich so wenig wie möglich beteiligen,
wie auch schon Graph-Darstellung, Zufallserstellung von Graph und was du alles dazu erfindest…


#13

Bitte schau dir diesen Beitrag nochmal an:

Ich konnte die Ausgabe wesentlich kürzen, h ändert sich ja nicht - und nur am Ende der while bedarf es einer Ausgabe.

Von h nach d: Weglänge: 231 bei mir
Von c nach d: Weglänge: 132
(Das sind Zufallswerte, manuell hab ich da nix gemacht :wink: auch reproduzierbar)


Frage wäre jetzt: Hab ich irgendwo einen groben Schnitzer gemacht

UND, wenn jemand so eine Ausgabe hinlegen würde, könnte man dann davon ausgehen, der Algorithmus sei von demjenigen verstanden?


#14

warum auch immer ich mir das antue:
im zweiten Beispiel ist (i,f=134,g=36) viel zu knapp, nur ganz knapp über Endweg 132,
dabei ist g nach i richtig 36, h dort aber 131, wieso nicht f = Summe = 167?
Ursache kann ich im Code nicht erkennen, edit: ok, in der ‘Animation’ schon wieder andere h-Werte…


selbst mit diesem verwegenen Wert wird i immer noch vor d selber aus openList gewählt,
das deutet darauf hin dass die PriorityQueue nicht umsortiert wenn man einen Wert ändert, was ja auch klar ist

dass du zum Einfügen einen ‘Schnitzer’ hast hatte ich ja eh schon gesagt,
so umso mehr geschnitzt, der Wiki-Code ist vollumfänglich zu beachten


Verständnis nach Zwischenschritten wäre für mich deutlicher in Beschreibungen wie im Wiki-Beispiel Saarbrücken,
ganze Sätze “Die Open List enthält nun zwei Punkte. Da Kaiserslautern den geringeren f-Wert hat, wird nun Kaiserslautern als Nächstes untersucht”,
das würde dir auch selber beim Verständnis helfen

nun freilich kann man das Wiki-Beispiel nicht mehr nehmen sondern ein anderes…

sinnvollere Knotennamen als a, b, c, sowieso ungünstig überschneidend, ‘Knoten h mit h = …’, allein schon Wechsel auf Großbuchstaben, wären dabei Ausdruck von Intelligenz, aber alles Interpretationssache


#15

Ob jemand etwas verstanden hat bekommt man als Gesprächspartner sehr schnell heraus. Ein Programm zeigt aber, dass man sich mit dem Algorithmus auseinander gesetzt hat.


#16

Also gut, wo fang ich an? :blush:



UND:

Ich bin mir nicht sicher, was mit doppelten Elementen geschieht, wenn es sie gibt,
ABER die Ausgabe erfolgt in “zufälliger” Reihenfolge, das wäre kein Fehler.

BTW


Großbuchstaben, Lesbarkeit, Verwechselbarkeit… deswegen hab ich doch Kommata geschrieben, und einzelne Großbuchstaben können auch mit Bundesstraßen oder Autobahnen (Wegen!) verwechselt werden.


Karte (B wegen besserer Lesbarkeit leicht verschoben, aber Position steht dran):

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);

            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;
                        if (openlist.contains(k2)) {
                            openlist.remove(k2);
                        }
                        openlist.add(k2);
                    }
                }
            }

            setText(closedlist, openlist);

        }
    }

Ausgabe:

  1. ol: (C,f=0,g=0),
    cl:
  2. 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),
  3. 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),
  4. 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),

Fazit vielleicht:

(I,f=134,g=36) setzt sich zusammen aus: g und h (36 + 98 = 134), wobei f=134 nicht kleiner als der optimale Weg ist… nur dicht dran


#17

Unter der Annahmen, dass .contains() etwas (mehr) kostet, hier noch eine Verbesserung:

    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);

            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)) {
                        if (newG < k2.g) {
                            openlist.remove(k2);
                            /* (an dieser Stelle Vorgänger setzen) */
                            k2.g = newG;
                            k2.f = newG + k2.h;
                            openlist.add(k2);
                        }
                    } else {
                        /* (an dieser Stelle Vorgänger setzen) */
                        k2.g = newG;
                        k2.f = newG + k2.h;
                        openlist.add(k2);
                    }
                }
            }

            setText(closedlist, openlist);

        }
    }

Dann… Wenn man sich zwei Kreise denkt, sieht man, dass sich bei C und I (ein Nachteil bei Großschreibung, ist es jetzt ein i oder ein l oder eine 1?) die Radien (Luftlinien) nur minimal unterscheiden. Ich hab das mal gezeichnet (nen Kreis hätte man auch schöner Zeichnen können…):

(Minimale Abweichungen der Kreisbögen da Rundungen). Ich denke, damit ist der f-Wert von 134, nahe am Optimum, zu erklären.

Weitergedacht: Würd I vor Ziel(-Knoten) untersucht werden, würd es ja nur eine Sackgasse finden.


So - das Thema ist bitte als [gelöst] zu betrachten. @SlaterB , kannst du einen Beitrag als Lösung auswählen - i-wie kann ich mich nicht festlegen.


Weitere Themen folgen wie bereits erwähnt nicht - denn ich denke, ich hab das jetzt gecklickert. Vielleicht wäre ein eigener Blogbeitrag dafür in Erwägung zu ziehen…


#18

Code-Verdopplung ist immer abzulehen, besonders von fachlichen Code wie f-Berechnung, Vorgänger setzen,
das contains kann auch 1x ausgeführt in eine boolean-Variable


ich zumindest würde es begrüßen, wenn du auf ständige Zusatzkommentare wie ‘Thema als gelöst betrachten’/ ‘weitere Theman erfolgen nicht’ usw. verzichten würdest,

niemand sonst schreibt sowas, ok, fast niemand, und neue Forum-Software ist gewisse Entschuldigung…,
falls du zur Forum-Bedienung eine Frage hast, gibt es gewiss eine Area dafür, ansonsten einfach nichts schreiben auch immer gute Variante


#19

Off-topic:

(vor 10h)

On-topic:

Ich werd das alles nochmal neu schreiben, bin mir aber wegen der grafischen (animierten) Repräsentierung unsicher. Hättet ihr noch ein paar Tipps?