Wenn es nicht so traurig wäre, hätte ich gelacht:
@Override
public int hashCode() {
int hash = 5;
return hash;
}
@CyborgBeta: ernsthaft?
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!
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.
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…)
2 „Gefällt mir“
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.
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…
1 „Gefällt mir“
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)
Gesucht: Der Weg von “b” nach “h”…
(Bitte mal über die suboptimale Implementierung hinwegsehen.)
Zu rendern mit: dot -O -Tpng baum.txt.
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
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?
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?’
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?:
Gutes Video zum Thema, erklärt sehr detailliert, wie (im Unterschied zu Dijkstra) gerechnet wird:
Ich brauch erst mal 'ne Pause. Der Graphen erstell Algorithmus ist jetzt fertig, aber es ist ein
for-for-while-for-if-if-break-Konstrukt inkls. shuffle… 
Das Problem mit dot konnte ich auch umgehen, indem ich einfach neato stattdessen - denn neato kann man eine Position mitgeben.
###Edit
Mit neato erstelle ich (je nach Parameter) solche Graphen:
und:
b6...
graph ASternGraph {
graph [overlap = false; splines = true;]
a [label="a\nh = 0", pos="6,4!"]
j [label="j\nh = 0", pos="0,9!"]
g [label="g\nh = 0", pos="8,7!"]
c [label="c\nh = 0", pos="1,2!"]
i [label="i\nh = 0", pos="1,4!"]
e [label="e\nh = 0", pos="2,8!"]
f [label="f\nh = 0", pos="9,5!"]
h [label="h\nh = 0", pos="1,10!"]
d [label="d\nh = 0", pos="10,0!"]
b [label="b\nh = 0", pos="7,2!"]
a -- b [label="33"]
a -- f [label="61"]
a -- g [label="62"]
a -- c [label="60"]
a -- d [label="81"]
h -- j [label="22"]
e -- j [label="31"]
i -- j [label="70"]
f -- g [label="33"]
b -- g [label="69"]
c -- i [label="36"]
c -- e [label="69"]
e -- i [label="46"]
h -- i [label="66"]
e -- h [label="30"]
d -- f [label="79"]
b -- d [label="39"]
}
Frage: Schaut euch die Kante von a nach f und von g nach b an. Das Label der Kante ist schwer zu lesen. Wie kann ich neato einstellen, dass Kanten Label nicht zu dicht beieinander sind? Im Internet hab ich nur etwas zu dot und Graph gefunden.
Frage: Gesucht sei der Weg von h nach d. Wie initialisiere ich alle h’s („unsauber“).^^
Ich finde, die Diskussion ist noch nicht tot. Weitere Fragen: Wird A Stern im Navi eingesetzt? Wird A Stern in Spielen eingesetzt? Müssen zu jeder disjunkten Knotenteilmenge der Länge 2 alle hs berechnet werden, damit A Stern eingesetzt werden kann?
Ok, der ganze Schlonz, wie man den Graphen erstellt und illustriert, außen vor. Konkret hab ich zu A Stern 3 Fragen…
- Wenn man als Heuristik nicht die Luftlinie nimmt, muss man A Stern einmal für die bestmögliche Heuristik ausführen?
- Bei der Implementierung auf Wikipedia werden doppelte Knoten in der openlist vermieden. Ist es schlimm, wenn in der openlist doppelte Knote sind? Eigentlich doch nicht, total belanglos, außer vielleicht für Laufzeit.
- Was ist eigentlich mit tentative (
tentative_g) gemeint?
1 - Unsinnsthema
2 - ein korrekter Algorithmus arbeitet auf natürliche Weise korrekt, doppelte Knoten sind Unsinn,
man kann natürlich auch viel Unsinn dabei veranstalten und wohl dennoch zum Ziel kommen, Laufzeit in der Tat ein Thema,
leicht geht bei sowas aber auch viel mehr schief, nicht pauschal zu beantworten
wie schlimm das ist, ist Interpretationssache,
Beurteiler können auch bei unnötigen Kleinigkeiten 0 Punkte vergeben, Kunden 0 Euro bezahlen, usw.
3 - kreative Variablennamen sollten dir nicht fremd sein, die Bedeutung des englischen Worts ist nachschlagbar,
wenn dir Variablenname p lieber ist, dann nimm p…
der Sinn dahinter sollte vom Konzept her klar sein, es kann auf verschiedene Wege zu einem Knoten gekommen werden, verschieden lange Wege sind zu vergleichen
bei dieser Gelegenheit, vorher für ein eigenes Posting zu dämlich:
Wikipedia, Abschnitt Anwendungsgebiete:
das war schwer herauszufinden und fragenswert…
Darum geht es. Ich hab ja schon einmal ~ 0 Punkte bekommen, weil vielleicht das tiefergehende Verständnis fehlte. Das soll sich beim nächsten Mal nicht wiederholen.
[offtopic]Sonst „Kopf ab“. :([/offtopic]
Deswegen hab ich mir hier Anregungen und Antworten erhofft. Und ich finde, im Diskurs kann man mit u. a. am besten lernen…
Alle h-Werte bestimmen… Orientiert hab ich mich an: A*-Algorithmus – Wikipedia . Aber ich hab den Algorithmus mit dieser Methode leicht vereinfacht. Und einmal nicht die optimale Datenstruktur verwendet:
static void setH(Knot knot) {
LinkedList<Knot> closedlist = new LinkedList<>();
PriorityQueue<Knot> openlist = new PriorityQueue<>();
openlist.add(knot);
while (!openlist.isEmpty()) {
Knot k1 = openlist.remove();
closedlist.add(k1);
for (Kant kant : k1.n) {
if (!closedlist.contains(kant.k2)) {
int newH = k1.h + (int) Math.round(dist(k1, kant.k2) * 10.0);
if (kant.k2.h == 0 || newH < kant.k2.h) {
kant.k2.h = newH;
openlist.add(kant.k2);
}
}
}
}
}
Zwischen Zeile 10 und 11 müsste eigentlich noch eine Prüfung stehen. Deswegen meine Frage: Ob er, wenn auch langsamer, trotzdem korrekt arbeitet?
Außerdem können vielleicht in der Prüfung gefragt werden:
h-Werte 1:
h-Werte 2:
Gesucht sei jeweils der Weg von h nach d. Welcher Graph stellt bessere h-Werte (Heuristik) dar, und wieso?
man kann den Algorithmus nach wie vor korrekt implementieren oder ohne jede Not Unsinn hinzufügen,
ich zumindest kann nicht abschließend beurteilen, was das für die Korrektheit bedeutet und will da auch gar nicht noch mehr Zeit drauf verwenden,
100.000 bekommen die Aufgabe A* zu implementieren und machen es auch, fertig,
warum brauchst du tausend Sonderlocken?
allein h neu zusammengesetzt zu berechnen, mal abgesehen vom fraglichen Inhalt, das kommt im Algorithmus schlicht nicht vor,
h ist für alle Knoten von Anfang bis Ende konstant, die einmalige Schätzung zum Ziel, unabhängig von allem anderen
die zweite Frage interessiert mich persönlich auch nicht, genausogut könnte gefragt werden welcher Graph sich besser als Bild im Louvre macht,
vielleicht hast du da einen ernsthaften Hintergrund, was ich bezweifle,
aber wenn dann mir zumindest nicht bekannt und ich kann es nicht weiter beantworten
Icke mal wieder… Ich verstehe noch nicht:
- Wie die Heuristik die Laufzeit verringert,
- Wie die Heuristik „einige“ Knoten von der Betrachtung ausschließt,
Mit der Frage, ob A Stern im Navi und in Spielen eingesetzt wird, sei „keine Industriespionage“ gemeint, sondern,
3. Ist A Stern „Best common/current practice“ für die Wegfindung?
[offtopic]Mit dem Aufzählungsverhalten komme ich auch noch nicht zurecht. 
[/offtopic]
###Edit
Ist es so zu verstehen, dass der Zielknoten erreicht wird, ehe alle Knoten betrachtet sind (bei Dijkstra aber nicht)?
Und, wirklich nochmal die Frage, auch wenn sie infantil klingt, würd Dijkstra alle Knoten kreisförmig um den Startknoten herum untersuchen, bildlich gesprochen?
Und die Nachteile:
4. Sind nicht die Laufzeit, sondern der Speicherplatz (wie im Artikel zu lesen…), das gilt insbesondere für Dijkstra auch so?
Zu 1 und 2: Die Laufzeit wird verringert, weil eine gute Heuristik dafür sorgt, dass irrelevante Pfade nicht betrachtet werden müssen.
Wenn man z.B. einen Pfad von Hamburg nach Berlin berechnen möchte.
Dann kann eine Heuristik sagen, dass die direkte Entfernung 200 km zwischen den Städten beträgt. Fährt man dann tatsächlich auf der Autobahn, werden da dann z.B. durch Kurven etc. 250 km daraus.
AStern wird relativ schnell, den Weg mit 250 km finden. Und wenn man diesen kurzen Pfad dann einmal gefunden hat, und man nun einen Weg über Paris in betracht ziehen wollte, was ca. 1000 km von Berlin entfernt ist (Heuristik), dann sieht man gleich dass das nichts mehr werden kann, weil jede tatsächliche Route von Paris aus länger als 1000 km ist und kann die weiter Berechnung abbrechen.
Die Heuristik muss kleiner gleich der tatsächlichen Entfernung sein, aber trotzdem gut genug um irrelevante Pfade auszuschließen. Erst dann funktioniert AStern gut.
Andere Algorithmen sind teilweise leichter zu implementieren, würden aber auch versuchen Pfade über Paris zu berechnen. Dort wird also auch viel im nachhinein unnützes berechnen und haben daher höhere Komplexität und damit in vielen Szenarien eine höhere Laufzeit.
Beim Einsatz im Navi, wird man noch andere Dinge berücksichtigen müssen, da man manchmal nicht die kürzeste sondern die schnellste oder effizienteste Route haben möchte. Zudem wird man wohl auch den Suchraum im vorhinein etwas verkleinern wollen. Bei einer innereuropäischen Route wird man wohl kaum Anfangen Heuristiken für alle Punkte in Amerika und Australien zu berechnen.
UPS z.B. hat für ihre Routenberechnung einen Algorithmus verwendet, der das Linksabbiegen möglichst vermeidet, da dies in der Regel mit hohen Wartezeiten beim Abbiegen verbunden ist und dadurch Einsparungen in Millionenhöhe erwirtschaftet.