A* implementieren

CyborgBeta · 14. März 2017 um 07:53

Hallo, meine Kenntnisse sind etwas eingerostet. Ich möchte:

10 bis 20 Knoten “zufällig” erstellen,
mit 2 Knoten A* darauf ausführen, sprich implementieren,
alle “wichtigen” Zwischenschritte in linearisierter Schreibweise ausgeben,
vielleicht eine grafische Illustration der Knoten und Zwischenschritte rendern.

Ich hab leider keine Ahnung, wie ich das “durchziehen” kann. Besonders Schritt 3. wäre mir wichtig. Vielleicht passt das Thema auch in den Bereich Hausaufgaben.

Jeder Hinweis ist mir gern willkommen. (Ich wollte das erst unter einem neuem Benutzer schreiben, aber das Thema ist mir dann doch zu wichtig, als dass es einfach weg wäre. Der “Neuebenutzertest” ist bis auf Weiteres verschoben.)

Crian · 14. März 2017 um 12:59

Du bist doch wirklich lange genug dabei. Kein Code? Gar keiner?

ionutbaiu · 14. März 2017 um 13:00

Am besten Schritt für Schritt. Es gibt ja immer verschiedene Vorgehensweisen und da es ja Richtung Hausaufgaben geht, kann man ja auch mal was neues/anderes ausprobieren.
z.B. direktes visuelles Feedback.

An der Stelle würde ich erstmal die Knoten generieren. Als nächsten Schritt würde ich die Knoten grafisch darstellen, z.B. in Swing in ein Koordinatensystem zeichnen.
Der nächste Schritt wäre dann Kanten zu generieren, also die Verbindungen von Knoten zu Knoten. Und dies wiederum grafisch darstellen.

Dann braucht es einen Start und ein Ziel. das ganze kann man dann durch eine andere Farbe oder Form grafisch darstellen.

Als nächstes nimmt man ja erstmal alle Knoten, die man vom Start aus erreichen kann und tut diese in ein Set. Könnte man also auch wieder farblich markieren.
Dort sucht man sich den Knoten aus, der mittels der Bewertungsfunktion am nächsten dran ist am Ziel. Das könnte man dann wiederum Farblich markieren.

Das treibt man solange fort, bis man den gesamten A* implementiert hat und hat nebenbei gleich die Illustration des Algorithmus.

TMII · 14. März 2017 um 13:27

War mir auch zu blöd auf das Thema zu antworten.
Zugegebenermaßen findet man über die Forensuche kaum was über “A*” oder “A star” weil der Suchbegriff echt beschissen ist obwohl wir das Thema bereits zu genüge hatten.
Aber im Internet ist A* praktisch der einzige bekannte Wegfingunsalgorithmus und der wahrscheinlich populärste Algorithmus der letzten 100 Jahre.

CyborgBeta · 14. März 2017 um 13:48

Bitte ernstgemeinte Antworten, und nicht so etwas:

Ich fange gerade erst an, Code kann ich nachreichen. Aber ich weiß nicht, ob ich einfach Teile aus einem Script dafür nehmen darf.

Nochmal: Besonders Punkt 3 ist mir wichtig, eine Ausgabe der Zwischenschritte. Sinnvolle und wichtige Zwischenschritte.

BTW: Bei google muss man nach A Stern suchen, A* liefert keine Ergebnisse, vielleicht ist das hier auch so.

Vielleicht fange ich wirklich so an: Knoten generieren (2D), Kanten genieren, zufällig Kanten mit langer (und kurzer) Distanz rausschmeißen, damit A* auch etwas zu tun hat. Dann müssen Kanten ja auch noch „gewichtet“ werden, ist das richtig?

Ach, ehrlich, ich hab keinen Plan von A*.

Vielleicht, zur Motivation, jemand kann nochmal kurz etwas zu den Einsatzgebieten von A* sagen (gern auch vs. andere Verfahren).

CyborgBeta · 14. März 2017 um 16:59

Wie versprochen, hier ist der Anfang:

Code...

/**
 * @author
 */
public class AStern {

    public static void main(String[] args) {
        List<Knot> knots = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            knots.add(new Knot((char) ('a' + i)));
        }
        Collections.shuffle(knots);

        Random r = new Random();
        for (int i = 0; i < 15; i++) {
            Knot k1 = knots.get(r.nextInt(knots.size()));
            Knot k2 = knots.get(r.nextInt(knots.size()));
            if (k1.equals(k2) || k1.n.contains(k2)) {
                continue;
            }
            int k = (r.nextInt(10) + 1) * 10;
            k1.n.add(k2);
            k1.k.add(k);
            k2.n.add(k1); // ungerichtet
            k2.k.add(k);
        }

        // h ???????????????????????????????????????????????????????????????????

    }
}

class Knot {

    char c;
    int h;
    List<Knot> n = new LinkedList<>();
    List<Integer> k = new LinkedList<>();

    Knot(char c) {
        this.c = c;
    }

    @Override
    public int hashCode() {
        int hash = 5;
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        return c == ((Knot) obj).c;
    }

    @Override
    public String toString() {
        String s = "";
        for (int i = 0; i < n.size(); i++) {
            if (c < n.get(i).c) {
                s += "\"" + c + "\\nh = " + h + "\" -- \"" + n.get(i).c + "\\nh = " + n.get(i).h + "\" [label=\"" + k.get(i) + "\"]\n";
            } else {
                s += "\"" + n.get(i).c + "\\nh = " + n.get(i).h + "\" -- \"" + c + "\\nh = " + h + "\" [label=\"" + k.get(i) + "\"]\n";
            }
        }
        return s;
    }
}

Liefert auch bereits etwas:

"Karte"...

Gesucht sei der Weg von “i” nach “j”…

SlaterB · 14. März 2017 um 17:28

kein Code wäre vielleicht doch besser…,
so muss man ja zum Schutz aller, die potentiell über das Internet hierher finden könnten, dann doch etwas schreiben…

Liste von Knoten und Liste von ‘Label’ getrennt dazu ist doch ein klassischer Feher,
besonders schlimm wenn noch in zwei verschiedenen Knoten separat gespeichert,

ein einzelnes Objekt Kante oder so mit zwei Knoten und ‘Label’-int-Wert, das ist doch ganz simpel,
jeder Knoten kann sich gerne Liste von Kanten merken,

das monströse toString() wäre dann auch schon weit entschärft, und viel mehr bisher ja auch noch nicht vorhanden…

kompliziertes equals/ hashCode brauchst du nicht, nur Code-Wüsten,
wenn zwei Knoten mit gleichen Bezeichner vorhanden wären, dann wäre das so oder so Problem,
einfacher ==-Vergleich reicht hier bisher

die ‘Karte’ hat genau was mit dem Code zu tun/ zu ‘liefern’?
ein Beispielergebnis irgendwo anders ausgegeben?

in solchen Fällen wäre zumindest Random mit festen Startwert nützlich, damit wiederholt und überall dasselbe Beispiel herauskommt,
sonst deine Karte ja nicht weiter relevant: überall, auch bei dir beim nächsten Durchlauf, anders

manuelles Zusammenbauen eines guten Beispiels

a = ..; b = ..; makeKante(a, c, 50);
ist auch nicht verkehrt

fertige A* finden sich wie Sand am Meer, auch mit google-Suche A*…

erstes Suchergebnis der Wiki-Artikel natürlich

auch mit Einsatzgebieten, Nennung anderer Verfahren und wer weiß was du dir alles noch an seitenlangen fertigen Referaten von anderen wünschst…

CyborgBeta · 14. März 2017 um 17:56

LinkedList hast du noch nicht erwähnt… Wäre natürlich auch nicht das Optimum.

Also nochmal, es geht mir insbesondere um sinnvolle und wichtige Zwischenschritte (also fast alle) … und, um eine Diskussionsgrundlage zu habn, hab ich erst mal mit der Erstellung des Graphen angefangen. Den Seed weiß ich jetzt natürlich nicht mehr, aber stimmt, daran hätte ich denken können.

Aber leider ist das bei der Frage so, ich möchte was am Getriebe ändern, dann muss ich leider den Motor, das Getriebe, das Fahrwerk und die Räder (sprich das komplette Auto) auch ändern.

cmrudolph · 14. März 2017 um 18:17

Wenn es nicht so traurig wäre, hätte ich gelacht:

    @Override
    public int hashCode() {
        int hash = 5;
        return hash;
    }

@CyborgBeta: ernsthaft?

CyborgBeta · 14. März 2017 um 22:44

Also, nochmal zur Motivation, den Einsatzgebieten und Vergleich zu anderen Verfahren… Leider ist das auf Wikipedia völlig unzureichend…

A Stern. Wieso heißt es A Stern? Weil “es” sich sternförmig ausbreitet? Das ist nicht korrekt, Dijkstra breitet sich sternförmig aus, A Stern entlang einer Geraden des kürzesten Wegs.
Vergleich: Ist A Stern schneller als Dijkstra durch die Zusatzinformationen?
Begrifflichkeiten und Verständnis: Ich hab eine Liste mit Listen als Wege? Also:
b,d,c <- das wäre ein Weg / eine Liste in einer Liste (von Listen), richtig?
Kürzeste Wege zu jedem Knoten, mit dem Unterschied zu Dijkstra, nur relevante kürzeste Wege zu jedem Knoten, richtig?
So langsam fange ich an, das zu verstehen…
Implementierung… Völlig unzureichend auf Wikipedia, Kommentare schaden mehr als es nützt, eine (Pseudo-)Funktion sollte nie mehr als 10 Zeilen sein, guter PHP-style…
“Fazit”: A Stern umfasst sowohl Dijkstra als auch A Stern, alsbald alle h’s auf 0 gestellt werden? Das ist doch widersprüchlich zur Entstehungszeit vor ~ 100 Jahren.

Beantwortet einfach Frage 3) dann hab ich’s geklickert, und frage nicht mehr.^^ Frage 3) steht auch in dem Zusammenhang, wie die Schreibweise wäre!

Marco13 · 15. März 2017 um 02:02

Die Frage (und andere, die du kürzlich gestellt hast), klingen stark nach Uni/Schulaufgaben. Was aber mit Fragen, wie der nach dem Namen bezweckt werden soll, ist nicht ganz klar. Der Code ist gewohnt grauslig. Versuch’ mal etwas geradliniger zu fragen, sonst muss man solche Threads einfach zumachen.

SlaterB · 15. März 2017 um 07:32

man kann nicht gleichzeitig

A* implementieren wollen bzw. daran scheitern, eine einfache Aufgabe für Uni-Anfänger,
diese ALLEINE zu lösen bzw. nur mit fester, nicht antwortender Literatur, ist der ganze Lernzweck und die Auszeichnung des Vorhandenseins von Intelligenz

zumindest sehr weit alleine zu kommen außer Dummy-Klassen und Random-Code zu erstellen,
hättest du einen laufenden Algorithmus und nur noch Detailfragen zu ‘welches f+g ist minimal’ usw., könnte man noch drüber reden

und 2) auch noch komplizierte Hintergrundfragen nach Namen, Vergleich mit anderen Algorithmen, stellen,
das passt nicht in einen Thread,

über letzteres können sich nur Experten unterhalten, die etwa als absolutes Minimum alle Algorithmen kennen/ bereits erfolgreich implementiert haben… (eigentlich noch einige Stufen höher)

wie immer ist in solchen Threads am besten gar nichts/ sehr viel weniger zu schreiben,
nur dadurch dass sie öffentlich stehen, und andere unbedarfte Menschen auf der Suche zu A* hier vorbeikommen könnten, muss etwas Relativierung dazustehen

(edit: aber inzwischen steht wohl genug Hinweise, falls wer bis hier alles liest, im Weiteren kann dann Unsinn unkommentiert bleiben…, im nächsten Posting noch nicht ganz geschafft, aber wohl bald…)

CyborgBeta · 15. März 2017 um 07:36

Da steht es, das war meine Verständnisschwierigkeit. A Stern ist eine Verbesserung von Dijkstra. Demzufolge kann „es“ nicht ~ 100 Jahre alt sein, weil Dijkstra auch nicht 100 Jahre alt ist.

Ich möchte verstehen, wie A Stern funktioniert. Ich möchte verstehen, wie die closedList aufgebaut ist, und was exemplarisch in der closedList steht. Ich weiß inzwischen, dass die tatsächlichen Kosten an den Kanten stehen, und die geschätzten Kosten an den Knoten. Das wusste ich vorher nicht.

SlaterB · 15. März 2017 um 07:43

zu den 100 Jahren steht allein bei Wikipedia, bzw. hier im Thread in der Vorschau angezeigt:

…

hast du diese Idee nur aus

?
Star Wars ist auch der populärste Film der letzten 100 Jahre, was bedeutet das für seine Entstehungszeit?

tatsächliche Kosten und geschätze Kosten steht bei Wiki im aller ersten Absatz zur ‚Idee des Algorithmus‘, f(x) = g(x) + h(x) ,
wo sie stehen ist nicht gerade der entscheidende Punkt, wobei natürlich selbstverständlich,
konkrete Kosten betreffen einen konkreten Übergang, was sonst,
geschätze Kosten sind unbestimmt bei einem Knoten, wo sonst,

aber das kann man ja mal übersehen…, genau wie der Wiki-Code und alle Infos dort, von hunderten Menschen optimiert, von vielleicht 100.000den erfolgreich gelesen und gelernt, natürlich deiner Ansicht nach unzureichend ist und du hier eine exklusive neue Erklärung haben möchtest…

CyborgBeta · 15. März 2017 um 08:04

Erstmal möchte ich noch etwas nachreichen:

Code...

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * @author
 */
public class AStern {

    public static void main(String[] args) {
        List<Knot> knots = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            knots.add(new Knot((char) ('a' + i)));
        }
        // Collections.shuffle(knots);

        Random r = new Random(6);
        for (int i = 0; i < 15; i++) {
            Knot k1 = knots.get(r.nextInt(knots.size()));
            Knot k2 = knots.get(r.nextInt(knots.size()));
            if (k1.equals(k2) || k1.n.contains(k2)) {
                continue;
            }
            int k = (r.nextInt(10) + 1) * 10;
            k1.n.add(k2);
            k1.k.add(k);
            k2.n.add(k1); // ungerichtet
            k2.k.add(k);
        }

        // h ???????????????????????????????????????????????????????????????????
        System.out.println("graph ASternGraph {");
        HashSet<String> hss = new HashSet<>();
        for (Knot knot : knots) {
            String s = knot.toString();
            String[] split = s.split("\n");
            for (String string : split) {
                if (!hss.contains(string)) {
                    hss.add(string);
                    System.out.println(string);
                }
            }
        }
        System.out.println("}");
    }
}

class Knot {

    char c;
    int h;
    List<Knot> n = new LinkedList<>();
    List<Integer> k = new LinkedList<>();

    Knot(char c) {
        this.c = c;
    }

    @Override
    public int hashCode() {
        int hash = 5;
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        return c == ((Knot) obj).c;
    }

    @Override
    public String toString() {
        String s = "";
        for (int i = 0; i < n.size(); i++) {
            if (c < n.get(i).c) {
                s += "\"" + c + "\\nh = " + h + "\" -- \"" + n.get(i).c + "\\nh = " + n.get(i).h + "\" [label=\"" + k.get(i) + "\"]\n";
            } else {
                s += "\"" + n.get(i).c + "\\nh = " + n.get(i).h + "\" -- \"" + c + "\\nh = " + h + "\" [label=\"" + k.get(i) + "\"]\n";
            }
        }
        return s;
    }
}

(brauchbares)

Ergebnis...

Gesucht: Der Weg von “b” nach “h”…

(Bitte mal über die suboptimale Implementierung hinwegsehen.)

Zu rendern mit: dot -O -Tpng baum.txt.

SlaterB · 15. März 2017 um 08:27

mal eine brauchbare Info, wiederum aus Wiki:

in deinem Graphen sind ja beliebige Verbindungen belieber Kosten möglich,
es gibt keine Abschätzung, keine Heuristik

such dir vielleicht lieber ein Landkartenbeispiel,
setze die Knoten an bestimmte 2D-Koordinaten (1,1), (5,3) usw.,
die Abschätzung zum Ziel ist der Luft-Abstand/ mathematische Entfernung,
als tatsächliche Kosten nimm den Abstand zwischen zwei Knoten + einen Zufallswert,

oder auch einfach alles konkret vorgeben, mit Zufall zu arbeiten kann auf Dauer aufwendiger sein…,
wenn konkrete Landkarte mit Stadt-Beispielen, wie wiederum im Wiki zu sehen, dann viel anschaulicher, Fehler eher zu erkennen, als nur A, B, C,

wenn mit anderen darüber zu reden vielleicht exakt das Saarbrücken-Würzburg-Beispiel…,
bzw. selber im Wiki verfolgen, wie der korrekte Ablauf ist, mit deinem Programm vergleichen,
hat eben alles seinen schon lange bekannten Sinn

CyborgBeta · 15. März 2017 um 11:24

Den (x, y)-Ansatz finde ich auch schön. Frage: Gegeben sei ein zufällig genierter Punkt (x, y)… Wie bestimme ich alle Punkte im Umkreis und füge eine Kante mit einer gewissen Wahrscheinlichkeit hinzu? + um den Realismus zu erhöhen, Wege sind steinig und schwer, und nicht immer gradlinig… Wie füge ich Kanten mit einer Länge von 100 bis 150 % der Luftlinie hinzu?

Desweiteren… kann ich Start- und Zielknoten (oder Quelle und Senke…) manuell bestimmen und einmal Dijkstra darauf ausführen, um Maximalwerte für die Schätzung/Heuristik h zu erhalten… Ziehe ich diese Maximalwerte dann manuell herunter, damit A Stern nicht sofort den optimalen Weg findet?

Das alles möchte ich möglichst so wie ein Prüfungsfragentrainer habn. Sorry für die Formulierung… Quasi ein Programm, dass eine Prüfung generiert und mich dann abfragt.

Und dann noch eine Frage BTW… Wieso darf eine Schätzung sich nicht überschätzen? Stichworte: Konsistent und Zulässig. Bedeutet zulässig, „alles“ ist konsistent?

SlaterB · 15. März 2017 um 11:35

nur nochmal, falls auf mich gewartet:
ich habe kein Interesse neben bzw. statt A* nun auch noch ein kompliziertes Programm zur Erstellung von zufälligen Graphen zu schreiben,

und zu ‘Konsistent und Zulässig’ brauchst du eigentlich auch nicht nachdenken, nimm solche Theorie so wie sie ist hin oder interessiere dich dafür gar nicht erst (durchaus wie 95%+ derer, die A* implementieren),
von der Implementierung A* mit Standardheuristiken wie Luftlinenabstand weitgehend unabhängig,

oder wenn es dich doch selber interessiert bzw. du tiefere Uni-Aufgaben dazu hast, dann musst du schon bisschen mehr selber dazu nachdenken…,
man kann nicht zu allen Dingen beliebige Fragen stellen ‘warum ist der Himmel blau?’

CyborgBeta · 15. März 2017 um 18:17

Das Programm zur Erstellung von zufälligen Graphen, ist wirklich nicht leicht. Aber ich habs hinbekommen, s. d. jeder Knoten z. B. 3 Kanten hat. (das geht auf, wenn man für die letzten 3 Knoten nicht mehr genau 3 Kanten verlangt).

Aber dann mache ich eigentlich etwas „dummes“, ich kenne die (x, y)-Werte… ABER übergebe dot nur die Kanten, damit es genau dieses Layout findet…

[details=Graph…]graph ASternGraph {
graph [overlap = false; ]
„a\nh = 0“ – „b\nh = 0“ [label=„22“]
„a\nh = 0“ – „f\nh = 0“ [label=„32“]
„a\nh = 0“ – „g\nh = 0“ [label=„36“]
„b\nh = 0“ – „d\nh = 0“ [label=„36“]
„b\nh = 0“ – „f\nh = 0“ [label=„36“]
„c\nh = 0“ – „i\nh = 0“ [label=„20“]
„c\nh = 0“ – „e\nh = 0“ [label=„61“]
„c\nh = 0“ – „j\nh = 0“ [label=„71“]
„d\nh = 0“ – „f\nh = 0“ [label=„51“]
„d\nh = 0“ – „g\nh = 0“ [label=„73“]
„e\nh = 0“ – „h\nh = 0“ [label=„22“]
„e\nh = 0“ – „j\nh = 0“ [label=„22“]
„g\nh = 0“ – „h\nh = 0“ [label=„76“]
„g\nh = 0“ – „i\nh = 0“ [label=„76“]
}[/details]

Das lustige ist, dot benutzt eine Heuristik, damit die Rechenzeit nicht unendlich wird… Genau diese Heuristik verhindert jetzt aber das Nichtüberschneiden genau einer Linie - UND: ich kann diese Heuristik nicht deaktivieren.

Jemand einen Tipp?:

Graph 2...

Landei · 15. März 2017 um 20:35

Gutes Video zum Thema, erklärt sehr detailliert, wie (im Unterschied zu Dijkstra) gerechnet wird: