Diskussion:A*-Algorithmus/Archiv/1

nicht mehr relevante Diskussionsbeiträge

Allgemeines

Schöner Artikel, der allerdings noch etwas Straffung gebrauchen kann.Der Abschnitt "Allgemeines" erhält viele Leerfloskeln ("Wie schon oben angedeutet.."), zuviele Einschübe und Wiederholungen ("Der Algorithmus arbeitet hierbei umso zielgerichteter, je besser die Heuristik ist. Hierzu ist es nötig, dass die durch die Heuristik geschätzten Kosten zum Ziel sehr nahe an den tatsächlichen Kosten zum Ziel sind. Das Finden einer guten Heuristik ist somit der wichtigste Schritt, wenn man effizient einen kürzesten Pfad mit Hilfe des A*-Algorithmus finden will.", drei Sätze mit fast gleicher Aussage.) DoopDoop 12:18, 15. Nov 2005 (CET)

Hi! Ist es so besser? Für Hinweise auf weitere Stilblüten bin ich natürlich immer dankbar. Regnaron 12:56, 15. Nov 2005 (CET)

---

Ich finde der Artikel ist schwer zu lesen. Die unter "Sprachliche Katastrophe" angesprochenen Verbesserungsvorschläge sollten konsequenter umgesetzt werden. Schon im Abschnitt "Allgemeines" ist vieles zu umständlich formuliert.

• z.B. "Der Algorithmus arbeitet hierbei umso effizienter, je genauer die von der Heuristik für einen Knoten geschätzten Kosten bis zum Ziel den tatsächlichen Kosten von diesem Knoten zum Ziel entsprechen." Wie wäre es mit: "Der Algorithmus arbeitet umso effizienter, je genauer die Heuristik ist."
• "[...] so kann man beweisen, dass der A*-Algorithmus tatsächlich immer einen kürzesten Weg findet." - unklare Formulierung, ein überflüssiges "tatsächlich" (wird sowieso schon viel zu oft im Artikel verwendet); falls es einen Weg vom Start zum Ziel gibt, findet der A*-Algorithmus den kürzesten Weg; nur falls es mehrere kürzesten Wege gibt, wird ein kürzester Weg gefunden
• "Dies bedeutet jedoch im Umkehrschluss auch, dass der Algorithmus nicht mit Sicherheit den kürzesten Weg zum Ziel findet, falls man eine sehr schlechte Heuristik verwendet." Was ist eine sehr schlechte Heuristik? Wie wäre es mit "Ist die Heuristik nicht monoton, wird unter Umständen eine suboptimale Lösung gefunden (z.B. dritt-kürzester Weg)."
• Im letzten Abschnitt ist der D*-Algorithmus erwähnt: "Eine Abwandlung des A*-Algorithmusses ist der schnellere D*-Algorithmus [...]" Dies ist meines Wissens nach nicht korrekt. D* ist ein zu A* äquivalenter Algorithmus, der durch gewisse Erweiterungen in der Lage ist, auf Graphveränderungen zur Suchzeit zu reagieren. Dies ist z.B. der Fall, wenn ein Roboter sich einen Weg durch unbekanntes Gelände sucht und dabei neue Hindernisse entdecken kann. In diesem Fall ist der Graph zur Suchzeit also unbekannt oder nur teilweise bekannt.

Meine konkreten Änderungsvorschläge sollen Anregungen für eine komplette Überarbeitung sein. Wenn nur einzelne Sätze geändert werden passen sie wohl nicht zum Rest des Artikels.

Ich werde mich in den nächsten Wochen näher mit diesem Artikel beschäftigen. Fürs erste nur Anregungen für den ersten und letzten Abschnitt "Allgemeines" sowie "Andere Verfahren zur Berechnung kürzester Pfade".

--Sargeras 23:20, 22. Aug. 2007 (CEST)

Überarbeitung

Super gemacht! Ich wollte hier auch schon länger mal Hand anlegen, aber das ist sicherlich besser als alles, was ich hätte schreiben können. Aber ich habe auch noch eine Frage. Man liest fast immer noch was von einer closed list, wofür braucht man die? Ich habe schon öfter den A* implementiert (oder auch nicht?!) und habe die Liste nie brauchen können. Ich habe zwar stets eine Entscheidungsmöglichkeit, ob ein Knoten schon besucht wurde, aber wozu so eine closed Liste gut sein soll, ist mir rätselhaft.

Ich vermute, bei der Beschreibung des Algorithmus soll die Aussage "v_min wird aufgelöst" bedeuten, dass er zukünftig nicht mehr betrachtet wird. Dies könnte man etwas genauer ausführen und vielleicht erklären, wann eine closed list dafür gut ist und wann nicht. Ich kann es leider nicht erklären.  :(

Und dann ist IMHO ein kleiner Fehler auch noch drin. "Aufgelöste" Knoten können nämlich wieder aktiv werden, wenn man einen günstigeren Vorgänger gefunden hat, das sollte erwähnt werden!

Gruß, Michael -- 84.150.41.130 22:43, 6. Nov 2005 (CET)

Hi! Danke erst einmal für das Lob :-)

Das mit der Closed List hängt so weit ich weiß von der Heuristik ab welche du verwendest. Wenn du eine Heuristik verwendest die dir garantiert dass der erste gefundene Pfad zu einem Knoten auf jeden Fall ein kürzester Pfad ist, so brauchst du die Closed list nicht. Du musst also garantieren können, dass die Heuristik für einen Knoten n garantiert nicht größer ist als die Kosten um von n zu seinem Nachfolger n' zu kommen plus die Heuristik des Nachfolgers. Die Heuristik muss also in der Form eine monoton steigende Funktion sein. Formal ausgedrückt: heuristik(n) \le; kosten(n,a,n') + heuristik(n').

Wenn deine Heuristik aber nur garantiert den Weg bis zum Ziel nie überschätzt, dann kann es in einem Graph sein dass dein erster gefundener Pfad zu einem Knoten nicht unbedingt ein kürzester Pfad ist, weswegen du in der Liste immer nachgucken musst ob du gerade vielleicht einen besseren Weg zu dem Knoten gefunden hast.

Bei dem Algorithmus kann es durchaus sein dass da noch einiges falsch ist, da ich bisher keine Zeit / Lust (*g*) hatte einen eigenen Algorithmus in Pseudocode zu schreiben, und deswegen das Teil erst einmal aus dem alten Artikel hier rein kopiert habe.

Aber dake für die Frage wegen den Heuristiken. Werde wahrscheinlich wenn ich den Algorithmus mal überarbeite das ganze ohne die Closed List bauen, und dafür dann eine monotone Heuristik verwenden. Dann muss ich halt nur noch einen Abschnitt einbauen was das besondere an monotonen Heuristiken ist. (Aber wird wahrscheinlich eh noch ein oder zwei Tage dauern bis der Artikel soweit fertig ist dass ich ihn ins Review stellen kann, und danach vielleicht zu den Lesenswerten (oder besser). Regnaron 00:04, 7. Nov 2005 (CET) (Unterschrift selbst nachgetragen)

So, habe gerade nochmal den Algorithmusteil fertiggestellt. Wenn du willst kannst du ja schonmal drübergucken. Bin mir eigentlich fast sicher dass ich irgendwo einen Fehler gemacht habe :-) (Der Teil mit der genaueren Beschreibung der Heuristik fehlt leider noch, aber dazu bin ich jetzt echt zu müde *g*) Regnaron 01:22, 7. Nov 2005 (CET)

  insert (start,S);
  while not isEmpty(S)
  {
     current_node := pop(S);
     insert (current_node, N);
     if (current_node == goal) then
        return reconstruct_shortest_path(N, goal);
     else
     {
        successors := expand(current_node, graph);
        forall s in sucessors do 
        {
           f(s);
           insert(s,S);
        }
     }
  }

Also wenn ich mir das so ansehe, liest du N nirgendwo aus (außer am Ende, den Pfad könnte man jedoch auf mit Vorgänger-Zeigern rekonstruieren). Also vermutlich funktioniert der Algorithmus so nur mit einer monotonen Heuristik, oder? Welche Heuristik ist denn überhaupt monoton? Die Luftlinie wohl nicht, da der Weg [distanz(n, n') + heuristik(n')] natürlich länger sein kann als [heuristik(n)], wenn n' in der falschen Richtung liegt. Gruß, Michael -- 84.150.50.196 19:37, 11. Nov 2005 (CET)

Jep. ich arbeite mit einer monotonen Heuristik. Aber die Luftlinie ist in der Tat eine Monotone heuristik. Das was du unten geschrieben hast ist genau das was ist oben geschrieben habe, nur dass du es von links und ich von rechts betrachtet habe :-) der Weg [distanz(n, n') + heuristik(n')] kann natürlich länger sein als [heuristik(n)] Genaugenommen kann es nicht nur so sein, sondern es ist immer so (ok, nicht länger, sondern länger oder gleich ;-)). Das "schlimmste" was dir passieren kann ist dass die Entfernung zwische zwei Städten wirklich genau die Luftlinie ist. Und das ist genau das wichtige einer monotonen Heuristik. (Aber kürzer als die Luftlinie wird die entfernung zwishen zwei beliebigen Städten nie sein => Heuristik überschätzt die Kosten immer => monoton.) Auf die Pfadrekonstruktion mittels Vorgängerzeigern wollte ich verzichten, da ich diese (zugegebenermaßen ineffiziete) Lösung anschaulicher fand. Beim Beispiel habe ich alle Knoten wo der Algorithmus schonmal war grau hinterlegt, und das sind dann auch genau die Knoten die halt in mein N kommen. Außerdem müsste ich bei Vorgängerzeigern halt noch den Code soweit aufblasen, dass ich sobald ich einen Knoten erkunde auch noch diesen Knoten so verändere dass er einen Zeiger auf den Vorgänger speichert. Effizienter, aber ich denke mal für eine Oma schwerer zu verstehen. Regnaron 20:21, 11 November 2005 (CET)

So, noch ein kleiner Nachtrag: Hattest mit dem N natürlich recht: Meine Idee wie ich den Weg am Ende rekonstruieren kann klappt nicht. (wollte alle Knoten nach dem Ziel (und dann rekursiv hoch) durchsuchen. Bei dem Angegebenen Beispiel hätte ich damit aber eventuell eine Suboptimale Route zurückbekommen (eben die lange über Augsburg, da ja das Ziel von dor aus durchaus erreichbar ist)) Habe den Algorithmus jetzt so geändert dass er diese Hilfsstruktur vollkommen außen vor lässt und es direkt über Zeiger macht. Regnaron 23:33, 11 November 2005 (CET) Und meine Idee klappte doch. Man muss nur den Knoten den man am Ende aus der Menge auswählt geschickt wählen. Es müsste zwar auch irgendwie über Pointer möglich sein, den Pfad am Ende zu rekonstruieren, aber irgendwie kamen da dann manchmal doch Probleme auf für die ich auf die Schnell keine Lösung hatte. (wie bestimme ich zum Beispiel den Vater in Schritt 3? Der zuletzt besuchte Knoten ist es ja nicht mehr...) Regnaron 00:19, 12. Nov 2005 (CET)

Also mit Vorgänger-Zeigern geht das mit Sicherheit. Wenn du einen Knoten expandierst, gibt es die Möglichkeit, dass ein Nachbarknoten zum ersten mal erreicht wird oder günstiger als bisher erreicht wird. In diesen Fällen musst du das g vom Nachbarn ändern. Immer mit dem g änderst du natürlich auch den Vorgänger mit. Das hast du alles in deinem expand() drin, ein Außenstehender kann das aber im Moment natürlich kaum erraten. Das g ändern ist irgendwie auch ein Teil, der noch beschrieben werden müsste IMHO. Im Moment entsteht der Eindruck, dass nur bisher nicht erreichte Nachbarn in open rein müssen. Siehe dazu auch:

"here is a main loop that repeatedly pulls out the best node n in OPEN (the node with the lowest f value) and examines it. If n is the goal, then we're done. Otherwise, node n is removed from OPEN and added to CLOSED. Then, its neighbors n' are examined. A neighbor that is in CLOSED has already been seen, so we don't need to look at it (*). A neighbor that is in OPEN is scheduled to be looked at, so we don't need to look at it now (*). Otherwise, we add it to OPEN, with its parent set to n. The path cost to n', g(n'), will be set to g(n) + movementcost(n, n').

(*) I'm skipping a small detail here. You do need to check to see if the node's g value can be lowered, and if so, you re-open it." (http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html)

Gruß, Michael -- 84.150.0.58 10:20, 12 November 2005 (CET)

Hm, also dank der monotonen Heuristik ist sobald ich einen Knoten expandiere ja automatisch der beste Weg zu diesem Knoten gefunden worden. Aber ich habe trotzdem wenn ich nicht dauernd suchen will oder so etwas ein paar Probleme mit den Zeigern. Wenn ich einen Knoten expandiere, dann kann ich die Zeiger der von diesem Knoten aus erreichbaren Knoten auf den aktuellen Knoten setzen. Kein Problem. Aber wenn ich einen Knoten ein weiteres mal finde, worauf soll ich dann den Nachfolger setzen? Dann muss ich erst wieder suchen ob das der kürzeste Weg zu diesem Knoten ist. Denn gefunden werden die Knoten ja immer mehrmals. Im Beispiel wäre München so ein Fall. Zuerst wird der Knoten München von Augsburg aus gefunden, also ist der Vogänger von München noch Augsburg. Dann passiert erst einmal lange Zeit nichts, und irgendwann wird München noch einmal erkundet, nur dieses mal tatsächlich auf einem kürzesten Pfad. Also müsste ich jetzt den Vorgänger updaten. Und den Vorgänger erst setzen wenn der Knoten expandiert wird ist zwar sicher, aber man weiß eben nicht immer was der Vorgänger ist (Siehe übergang von Schritt 3 zu Schritt 4, wo auf einmal bei einem komplett anderen Knoten im Baum weitergemacht wird.) Aber das ändern der f-Kosten ist doch schon beschrieben, oder? Die Kosten werden irgendwo weiter unten durch f(s) für den Knoten s geändert. Etwas genauer ist es noch im Fließtext zum Algorithmus. Aber sehr viel genauer würde ich es eigentlich ungern beschreiben, da es ja Pseudocode ist, und somit nach Definition nicht bis ins letzte Detail spezifiziert. (dazu wäre dann eine eventuelle reale Implementierung in C++, Java oder sonst einer Sprache da) Aber mein Expand hat momentan eigentlich die von dir erdachte Funktionalität nicht. Momentan guckt es echt nur für jeden Knoten im Graph nach welche Knoten von diesem Knoten aus erreichbar sind und holt sich diese Knoten :-) (jedenfalls ist es von mir so gedacht gewesen) Wie gesagt: Der Algorithmus soll in erster Linie simpel sein Regnaron 17:15, 12 November 2005 (CET)

"Aber ich habe trotzdem wenn ich nicht dauernd suchen will oder so etwas ein paar Probleme mit den Zeigern. Wenn ich einen Knoten expandiere, dann kann ich die Zeiger der von diesem Knoten aus erreichbaren Knoten auf den aktuellen Knoten setzen. Kein Problem. Aber wenn ich einen Knoten ein weiteres mal finde, worauf soll ich dann den Nachfolger setzen? Dann muss ich erst wieder suchen ob das der kürzeste Weg zu diesem Knoten ist." Zu prüfen, ob der jetzige Weg zu Knoten x besser ist als der bisher beste, ist trivial. Dazu muss man ja nur g des neuen potenziellen Vorgängers plus Kantengewicht mit f(x) vergleichen. Bzw. wenn du sagst, dass du bei einer monotonen Heuristik immer als erstes den besten Weg findest (glaub ich jetzt einfach mal), dann brauchst du nicht zu vergleichen und kannst den Vorgänger-Zeiger von x unverändert lassen, wenn du bereits einen hast. So kannst du den Pfad am Ende wenigstens in O(Anzahl der Knoten auf dem Pfad) rekonstruieren. Ehrlich gesagt verstehe ich dein Problem mit Vorgänger-Zeigern noch nicht so ganz.

Meinetwegen kann jetzt das bisherige System auch stehen bleiben, aber implementieren tu ich es so nicht.  ;) Vielleicht solltest du aber in diesem Fall kurz erwähnen, dass es auch mit Vorgänger-Zeigern geht, das ist nämlich AFAIK die üblichere Methode.

Hm, gute Frage wo mein Problem war. Ich wusste hat nie ganz wann ich die Vorgängerzeiger schreiben bzw speichern soll, sodass ich garantiert nie einen falschen Vorgänger speichere. Aber wenn ich mir bei den Knoten in der Open List merke von wem aus sie erkundet wurden (also sobald u expandiert wird für alle Nachfolger v_i in der Open List speichere dass sie von u aus erkundet wurden, und dann sobald v_i expandiert wird die entsprechende Information über den Vorgänger im Graph speichere, dann sollte es glaube ich gehen. Da ich immer einen kürzesten Pfad zu einem Knoten finde kann ich damit nur einen Optimalen Pfad abspeichern. Oder habe ich gerade noch etwas übersehen? P.S.: Das es die Übliche Mehtode ist das ganze über Zeiger zu machen wollte ich nie bestreiten, nur irgendwo hatte es bei mir halt gehakt wie das ganze dann gehen soll :-) Falls meine Idee oben klappen sollte schonmal danke fürs beharrliche Nachfragen, sodass ich dann doch noch auf eine vernünftige Lösung kommen musste :-) Regnaron 11:39, 13. Nov 2005 (CET)

So, habe das ganze nochmal entsprechend umgebaut. Könntest du bitte unter [1] nochmal kurz drübergucken obs so stimmt? Dankend Regnaron 12:25, 13. Nov 2005 (CET)

Sorry, ich konnte mich eine Zeit lang nicht melden. Für mich sieht das richtig aus, kann mal wohl so stehen lassen. Gruß, Michael -- 84.150.9.109 18:46, 1. Dez 2005 (CET)

Funktionsweise des A-Stern-Algorithmus

Für mich ist die im Abschnitt "Funktionsweise" erwähnte Gleichung völlig uneinsichtig. Deises Wirwarr aus Abständen von v zum Ziel, zu u, der aktuellen Position usw. ist meiner Meinung nach noch zu überarbeiten. Sicher bin ich mir mit meiner Kritik jedoch nicht....

Hi, danke erstmal für die Meldung. Habe versucht das ganze etwas besser und expliziter zu formulieren, und habe dabei noch festgestellt dass die Gleichung über die du gestolpert bist auch noch falsch war *pfiffel* Kannst du mir mal sagen ob du es nun besser verstehst? Beispiele will ich in dem Abschnitt bewusst noch nicht bringen, weil im nächsten Absatz direkt ein großes Beispiel kommt. Regnaron 20:42, 9. Nov 2005 (CET)

Abgeschlossenes Review vom 7. Nov 2005

Nachdem ich mich letzte Woche mal drangesetzt habe und den Artikel komplett neu geschrieben habe bin ich jetzt mit meinem Wissen zu dem Thema am Ende, und wollte euch mal Fragen was man an dem Artikel noch verbessern kann. Hierbei sind natürlich sowohl Fachfremde (ist der Artikel verständlich) als auch fachkundige Leute gefragt. Insbesondere von den Fachkundigen würde ich mir ein Feedback über den Pseudocode (da gibt es garantiert einen Fehler den ich momentan übersehe) und ein paar Anregungen zum Thema Heuristik wünschen. Würde noch gerne den Unterschied zwischen monotoner Heuristik und zulässiger Heuristik einbauen, da dies den Algorithmus etwas abändert (in allen anderen Wikipedias steht er momentan nur mit einer zulässigen Heuristik (also der schwächeren Form) drin, wodurch der Algorithmus etwas komplexer wird als er hier beschrieben ist. Aber leider weiß ich momentan nicht wirklich wie und wo ich das einbauen soll. Regnaron 18:47, 7. Nov 2005 (CET)

sehr schöner Artikel, ich hab ihn nur noch nicht ganz gelesen. Mir ist nur aufgefallen, dass das komplette Beispiel aus dem Russell-Norvig-Buch stammt. Ich bin mir nicht sicher, inwieweit es zulässig ist, solche Beispiele zu übernehmen. Zumindest sollte noch deutlich die Quelle genannt werden. Später werde ich mir den Artikel genauer anschauen. --Kurt seebauer 23:30, 7. Nov 2005 (CET)

Hi! Jep, habe das Beispiel 1:1 aus dem Russel Norvig Buch übernommen, aber da ich die gesamten Zeichnungen selbst angefertigt habe ging ich nicht davon aus dass das ein Problem wäre. (war halt nur zu faul extra korrekte Entfernungen zwischen Deutschen Städten zu recherchieren und eine eigene Heuristik zu definieren wenn alles schon gegeben ist. Aber ich gehe momentan nicht davon aus dass es ein Problem sein sollte, da ich ja nur die Idee kopiert habe. Und der Beweis dafür dass A* Optimal ist, ist von der Idee her (ok, für den Beweis dürfte das Buch nicht der "Erfinder" sein) auch 1:1 kopiert. Aber ich kann notfalls gerne im Text nochmal erwähnen dass ich das Buch als Vorlage genommen habe. (bei den Bildern habe ich schon bei jedem Bild ein Original Example from: Artificial Intelligence - A modern Approach in die Bildbeschreibung gepackt.) Hast du eine Ahnung wo man in der WP jemanden Fragen kann der sich mit so etwas auskennt? Regnaron 23:59, 7. Nov 2005 (CET)

Nachtrag: habe glaube ich gerade eine passende Seite gefunden: Wikipedia:Urheberrechtsfragen Werde da mal anfragen. Regnaron 00:09, 8. Nov 2005 (CET)

Auch das Nachzeichnen ist nicht unproblematisch bzgl URV. Du argumentierst ja gerade damit, dass es aufwendig wäre die Daten selbst zu recherchieren. Daher dürfte auch auf diesem Teil, der ja nun nicht von dir stammt, ein Urheberrecht liegen, so dass es sich imho um eine URV handelt. Auch wenn es aufwendiger ist (bzw. gerade deshalb) solltest du ein eigenes Beispiel angeben. --Coma 10:44, 8. Nov 2005 (CET)

Hm, ok, die Meldung bei Wikipedia:Urheberrechtsfragen war zwar eher positiver Natur (keine wirkliche Schöpfungshöhe bei den Buchautoren) aber ich werde mich wohl dann mal die Woche dranmachen und mithilfe einiger Routenplaner versuchen eine deutsche Strecke für den Algorithmus zu erstellen. Da sich aber dadurch nur die Namen der Städte und die Zahlen etwas ändern werden ist natürlich auch solange wie das bisherige Beispiel noch drinsteht jegliches Feedback erwünscht :-) Regnaron 17:14, 8 November 2005 (CET)

So, nachdem ich ich nun die selbstgemalten Bilder fertig habe, und den Text entsprechend an das neue Beispiel angepasst habe, habe ich garantiert wieder zig tippfehler, Kommafehler und sonstiges drin. Wäre also klasse wenn jemand mal den Text gegenlesen könnte ;-) (über Sachliche Kritik freue ich mich natürlich ebenso) Regnaron 15:35, 11. Nov 2005 (CET)

/* Besucher */ Also ich finde den Artikel echt klasse, hat mir geholfen das Prinzip ansatzweise zu verstehen. Vorallem die Bäume/Graphen sind klasse. Der Pseudocode ist aber in meinen Augen sehr unverständlich. Auch wäre es schön, wenn man z.B. getPredecessor(); kommentieren würde, und wie man jetzt z.B. den Vorgänger herrausfindet.

Ich habe das jetzt mal selber den Algo. (nach den Bildern) in PHP geschrieben, und die Knoten/Städte werden auch erkannt. Aber wenn ich dann in München angekommen bin, weiß ich jetzt nicht, wie man den Weg zurück verfolgen kann. Wäre schön wenn das noch hinzugefügt wird.

P.S. Erster Beitrag unter Diskussion

Und auch dir erstmal Danke fürs Feedback! Habe versucht den Teil zu getPredecessor im Fließtext zum Pseudocode zu beschreiben. Die dort gewählte Methode ist zwar alles andere als optimal, aber sie ist intuitiver als wenn ich da mit Pointern um mich werfe. Zum Pseudocode: Da ich als Informatiker in dem Punkt leider betriebsblind bin, wäre es nett wenn du mir sagen könntest was genau du an dem Code schwer findest. (habe schon versucht mich nur auf while Schleifen, if-then-else Statements und dergleichen zu beziehen und die Namen für die Funktionen selbsterklärend zu wählen.) Und ich vermute mal nicht dass man ein N := N ∪ s besser versteht als ein insert(s,N), und gegen ein N := N + s streubt sich der Mathematiker in mir :-) Bliebe nur noch die alternative insert s into N Ach so, eine Frage noch: Hast du dich beim Schreiben des Programms an den Algorithmus aus diesem Artikel gehalten, oder hast du es anders (also insbesondere mit zwei Listen wo du Knoten verwaltest) gemacht? Falls du es nämlich so gemacht hast wie in diesem Artikel, und der Code vernüftig kommentiert wurde und schön ist, dann wollte ich fragen ob du den Code nicht mal hier auf der Diskussionsseite posten willst? Dann kann ich mal gucken wie umfangreich er ist, und wir können ihn eventuell als Praxisimplementierung in den Artikel einbauen? (wenn die Definition von Graphen, Knoten, etc nicht zu umfangreich ist) Regnaron 23:04, 11 November 2005 (CET)

Abgeschlossene Lesenswert-Diskussion vom 19. Nov 2005

Der A*-Algorithmus dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er wurde das erste mal 1968 von Peter Hart, Nils Nilson und Bertram Raphael beschrieben.

Nachdem der Artikel nun ca 2 Wochen im Review stand, wo noch das ein oder andere verbessert wurde, denke ich dass er jetzt langsam reif für eine Lesenswert-Kandidatur ist. Als Hauptautor enthalte ich mich natürlich der Stimme. Regnaron 12:48, 19. Nov 2005 (CET)

• pro - da ich ihn bereits vor einiger Zeit (als Zufallsfund) bereits hier vorgeschlagen habe, finde ich ihn natürlich immer noch sehr gut - und vor allem auch verständlich. -- Achim Raschka 13:14, 19. Nov 2005 (CET)
• pro - klasse Arbeit! Sorry, dass im Review kein Kommentar mehr von mir kam. --Kurt seebauer 09:17, 20. Nov 2005 (CET)
•  Pro - sehr schön! -- Jcr 09:32, 20. Nov 2005 (CET)
•  Pro - ist wirklich sehr gut geworden. --Davidl 12:35, 20. Nov 2005 (CET)
•  Pro - wirkt überzeugend, Priwo 14:06, 20. Nov 2005 (CET)
•  Pro - um Welten besser als früher. Gruß, Michael -- 84.150.9.109 18:48, 1. Dez 2005 (CET) Danke für deine Stimme, aber das ganze hier ist nur eine Kopie von der Kandidatenseite, wo das Ergebnis der Abstimmung konserviert wurde. Der Artikel ist bereits erfolgreich zu den Lesenswerten gekürt worden Regnaron 21:17, 1. Dez 2005 (CET)

Kategorie "Suchalgo" korrekt?

A* beschäftigt sich mit dem Problem "kürzeste Wege" und wurde der Kategorie "Suchalgorithmus" zugeordnet. Ist diese Einordnung tatsächlich korrekt?

Suchalgorithmen beschäftigen sich mit der Suche nach Teilstrings oder Mustern in gegebenen Texten.

Falls Suchalgorithmen allgemein für "Die Suche nach einer Lösung für ein Problem" verstanden werden, müssten (fast) alle Algorithmen als Suchalgorithmen eingeordnet werden.

Ich würde diesen Algorithmus unter die Kategorie "Algorithmus" einordnen, weil sich dort bereits eine große Liste von Algorithmen befindet. --Venthur 21:14, 4. Jan 2006 (CET)

Ich gebe zu, dass ich momentan keine genaue Definition des deutschen Begriffes Suchalgorithmus in der Informatik zur Hand habe, aber zumindest in der englischen Literatur werden A*, Dijkstra, BFS und all die anderen unter Search strategies geführt, weswegen ich die beste passende Kategorie als Suchalgorithmen empfinden würde. Um hier noch einmal kurz die Wikipedia selbst zu zitieren: Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht. Hierrunter fällt meiner Meinung nach auch das finden eines Knotens mit bestimmten Eigenschaften in einem Graph. Und ich glaube die Kategorie Algorithmus selbst sollte eher schrumpfen statt wachsen, damit man über die Sinnhaftigkeit von Kategorien mit 200 Einträgen recht gut streiten kann. Immerhin kann man verdammt viel einfach als Algorithmus beschreiben. Regnaron 10:46, 5. Jan 2006 (CET)

Sprachliche Anpassung

Ich mogel mich einfach mal dazu und mach krasse Deutsch-Oberlehrer Korrektur ;-) --Thetawave 18:52, 10. Jan 2006 (CET)

Sei mutig! :-) --jpp ?! 12:09, 11. Jan 2006 (CET)

Abgeschlossenes Review vom 14. Dez 2005

Da der Artikel vor einiger Zeit zu den Lesenswerten gewählt wurde, wollte ich ihn demnächst mal bei den Exzellenten vorstellen, ihm aber vorher nochmal ein zweites "Express-Review" gönnen. Insbesondere würde es mich freuen wenn irgendwer noch was zu den Anwendungsgebieten, welche momentan leider noch sehr mager sind, beisteuern könnte. Regnaron 20:24, 14. Dez 2005 (CET)

Auch wenn es vielleicht egoistisch klingt: ich hasse C, besonders als Beipielcode. Wie wäre es mit Pseudocode, z.B. im Basic- oder Knuth-Stil? --Phrood 20:59, 14. Dez 2005 (CET)

C-Code? Das ist doch schon Pseudocode :-) Regnaron 21:47, 14. Dez 2005 (CET)

Naja nix gegen Ausführlichkeit aber der Artikel ist dem Inhalt nicht angemessen, ein prägnanteres Beispiel und das dann auch _nach_ dem Algorithmus, der nonverbaler (zielgruppengerechter - ein Psychologe liest sich das eh nich durch) formuliert werden sollte. Als Lehrbuchartikel (wikibook) sicher erhaltenswert fpr ein Lexikonartikel aber sicher zu ausufernd. --62.134.176.158 00:58, 24. Dez 2005 (CET)

Hi! Hm, gegen eine Vertauschung Algorithmus <-> Beispiel habe ich nichts, aber du sagst oben dass der Artikel eh nicht von einem Fachfremden gelesen wird, und deswegen ruhig unverständlich sein kann? Also da würde ich auf jeden Fall widersprechen. Nur weil ich kein Biologe bin, erwarte ich von Biologieartikeln trotzdem dass sie mir erklären worum es geht. Wir schreiben hier immerhin eine allgemeine Enzyklopädie, und nicht ein Fachlexikon, dessen Artikel nur die lesen dürfen die im Fach bewandert sind. Und im Abschnitt Algorithmus nutze ich eh schon nicht OMA konforme Begriffe wie Pfadkosten, etc. Zum Thema prägnanteres Beispiel: Was bringt dir ein Beispiel mit drei Knoten, wo der Algorithmus den selben Weg wie Breitensuche, Tiefensuche, oder Dijkstras Algorithmus findet? Das Beispiel sollte schon einen anderen Pfad finden als bei anderen Graphsuchen. Und dafür braucht man numal ein paar Knoten. Ach so, zum Thema nonverbale Beschreibung des Algorithmus: Der Pseudocode ist IMHO schon recht nonverbal :-) Regnaron 00:46, 27. Dez 2005 (CET)

Ich habe mir gerade einmal den Abschnitt Funtionsweise angeschaut. Dabei ist mir aufgefallen

• dass sehr viele Kommas fehlten (in diesem Abschnitt habe ich das gleich korrigiert, aber den Rest sollte man noch einmal kontrollieren)
• und dass die geometrische Idee (gerade im Vergleich zum Dijkstra) nicht klar wird. Ein Komilitone von mir, der sich mit Kürzeste-Wege-Algorithmen beschäftigt hat, hatte immer schöne Grafiken, wo in einem Graphen die vom Algorithmus angefassten Kanten/Knoten markiert waren. Im Vergleich zum Dijsktra würde man sehen, dass letzterer eine "kreisförmige" Suchfront hat, während der A* "in Richtung Ziel" sucht.

Und eine kleine Anekdote zum A*: Früher (Anfang der 90er) fand der Routing-Algorithmus der DB AG eine bestimmte Verbindung von Kiel aus nicht, wo man wegen der Ostseebucht einen großen Umweg fahren muss - da war die benutzte Heuristik offenbar zu schlecht ... Leider erinnere ich mich nicht mehr an die Einzelheiten, aber vielleicht kommt ja jemand aus der Ecke und weiß das noch. --Christian Gawron 01:31, 29. Dez 2005 (CET)

Hi! Zu den Bildern: Meinst du in etwa so wie hier? Falls ja: Sollte kein allzugroßes Problem sein die Bilder entsprechend umzustellen. Zu den Kommas: Jup, irgendwie scheine ich die kleinen dauernd zu boykottieren :-( Regnaron 10:54, 5. Jan 2006 (CET)

Ich dachte eher an eine Abbildung des Straßennetzes in Deutschland, wo die bei der Suche angefassten Knoten/Kanten eingefärbt sind. Deine Abbildungen enthalten für meinen Geschmack zu wenig Knoten. Interessant werden die Unterschiede ja eigentlich erst in großen Netzen - und da kann man dann gut sehen, dass der Dijkstra kreisförmig vom Startpunkt aus sucht, bis er das Ziel erreicht, und der A* eben nicht. Leider ist www.zaik.de gerade nicht erreichbar - dort müsste man eine Veröffentlichung von Stephan Hasselberg mit entsprechenden Darstellungen finden. --Christian Gawron 11:33, 5. Jan 2006 (CET)

Schau Dir mal S. 84 in der Dissertation von Stephan Hasselberg an. Solche Abbildungen meine ich.--Christian Gawron 12:20, 5. Jan 2006 (CET)

Hi! Hm, sicher dass du das Bild auf Seite 84 der Dissertation meinst? Falls ja: Ich bin ein großer Feind von animierten Bilder in der Wikipedia. Sicherlich werden die Karten aussagekräftiger wenn man 20 Knoten nutzt, aber wie willst du das als Bild im Internet darstellen? Selbst mit dem Spielzeugbeispiel von hier läuft man in Probleme, da die Bilder sehr groß werden, wenn man noch etwas darauf erkennen will. Das passt dann einfach platzmäßig nicht mehr in einen Wikipedia Artikel. Wenn die Suche in den Beispielten tatsächlich die Knoten so anordnen würde, wie sie in Deutschland liegen, wäre ich auch glücklich, aber bisher habe ich leider noch nicht rausgefunden, wie man graphviz sagt wo er die Knoten anordnen soll. Falls du mir da einen Tipp geben kannst, werde ich die Karten gerne bei gelegenheit neu kompilieren, sodass Frankfurt dann wirklich nördlich von München liegt. Regnaron 10:21, 7. Jan 2006 (CET)

Nachtrag: Ups, das sind ja eigentlich gar keine Animierten Grafiken, sondern einfach nur so komplexe Grafiken, dass sie beim laden stückweise geladen werden, und dadurch wie animationen aussehen *pfiffel*. Aber das Bild zeigt ja auch nicht wie die einzelnen Algorithmen arbeiten, sondern nur wie die Algorithmen prinzipiell arbeiten, also ob Zielorientiert oder nicht. Frage ist: Woher willst du auf die schnelle eine Datenbank Deutschlands bekommen auf der du automatisiert A* laufen lassen kannst, um dann den Output automatisch durch ein Programm einfärben zu lassen? Per Hand würde ich das ganze nämlich ungern für > 10.000 Knoten berechnen ;-) Regnaron 10:33, 7. Jan 2006 (CET)

Nachtrag: der A* - Algortihmus wird auch GDUS (goal directed unidirectional search) Algorithmus genannt und sollte darueber auch gefunden werden koennen - xy - 13:31, 6. Jan 2006 (CET)

Hi! GDUS ist zwar scheinbar laut Google kein übermäßig bekannter Name für den A* Algorithmus, aber da das Lemma GDUS noch nicht andersweitig verwendet wird, habe ich mal einen Redirect angelegt. Regnaron 10:21, 7. Jan 2006 (CET)

Sprachliche Mängel

Zur Klärung Monotonie => Zulässigkeit -> wurde korrigiert.

Der Satz: "Auf der anderen Seite gibt es extrem schlechte aber dafür sehr einfach zu berechnende Heuristiken. So kann man die Entfernung zwischen zwei Knoten mit Kosten von 0 schätzen, wodurch effektiv gar keine Heuristik mehr verwendet wird, und der A*-Algorithmus alle Knoten blind untersuchen muss, bis er durch Zufall das Ziel findet." ist schlicht falsch (Hinweis: ZUFALL). Der Algo bleibt natürlich deterministisch und entspricht dann vollständig einem anderen sehr bekannt Traversierungsalgorithmus (this is left as an exercise for the reader).

Ausdruck mangelhaft! "Schreibt man diese Überlegungen nun formal auf, so ergibt sich der formale Beweis der Optimalität des A*-Algorithmus:..."

Naja, das er weiterhin deterministisch sucht ist schon klar, aber eben nicht gezielt. Und irgendwann trifft er dann halt mal aufs Ziel. Mir fiel in dem Moment als ich es geschrieben habe kein besserer Begriff als Zufall ein. Falls du einen besser hast: Immer rein damit! :-) (habs inzwische mal ein bisschen entschärft)

Und, dass er ohne Heuristik gleich dem Algorithmus von Dijkstra ist, steht direkt im nächsten Satz.

Ansonsten zum Stil: Tja, bin leider Informatiker und kein Deutschlehrer ;-) Falls du natürlich besser formulieren kannst, gilt auch hier wieder das gute alte: Sei mutig! :-)

P.S.: Habe mir mal erlaubt das ganze der Übersichtlichkeit halber unten unter einer eigenen Überschrift anzufügen.

P.P.S.: Beiträge kannst du mit ~~~~ unterschreiben, so ist es für die anderen einfacher die Beiträge auseinanderzuhalten. Regnaron 19:52, 22. Jan 2006 (CET)

Sprachliche Katastrophe. Lesenswert?

Dieser Artikel sollte noch einmal auf den lesenswert Status überpruft werden. Lesenswert heisst auch gut zu lesen und dafür müssten:

• Nullwörter entfernt werden
• überflüssige Adjektive rausgenommen werden
• geschwätzige Stellen aufs Wesentliche reduziert werden
• aktive Formen verwandt werden.

Ich hoffe ein Graphentheorie Fachexperte kann sich dem annehmen und die Punkte verbessern. --62.134.233.36 21:31, 28. Feb 2006 (CET)

Ja, "Knoten bei dem man den A*-Algorithmus gestartet hat"=Startknoten, usw.

Fehler (26.10.06)

Zeile 12 des Algorithmus ist falsch, es fehlt der Parameter für die h-Funktion!

Stimmt, danke. Habe es gerade korrigiert. Aber gerade bei solch kleinen Fehlern gilt: Trau dich! Und ändere Stellen in Artikeln von denen du meinst dass sie falsch sind einfach :-)

Fehler (21.11.06)

Sowohl auf der deutschen, wie auch auf dewr englischen Wikipedia-Seite steht, daß der A*-Algorithmus dem Algorithmus von Dijkstra entspricht, wenn gilt f(x)=g(x)+0 . Ich bin mir nicht ganz sicher, aber ich glaube, dies ist nicht richtig. Wen f(x)=g(x)+0 ist, dann ist dies der Breitensuche-Algorithmus (siehe "Künstliche Intelligenz" von George F. Luger, Seite 164).

Hi! Nein, die Äquivalenz Dijkstra + Heuristik = A* stimmt schon. Breitensuche betrachtet die Kantengewichte *gar* nicht. Also hier wäre g(x) = d(x) und h(x) = 0 für alle x wobei d(x) der Abstand zum Startknoten ist. Eine Breitensuche kannst du dir auch so vorstellen, dass alle Kanten gewicht 1 haben. Bsp: G=(a,b,c,d, (a,b,1), (b,c,1), (a,d,5)). Breitensuche entdeckt die Knoten in folgender Reihenfolge (starting at a): a, b, d, c. Dijsktra entdeckt die Knoten in der Reihenfolge a, b, c, d, da der Pfad von a nach d teurer ist als der Pfad von a über b nach c. --Regnaron 17:18, 21. Nov. 2006 (CET)

Fehler (1.1.07)

Im Pseudocode steckt glaube ich noch nen Fehler. In der Relaxierung wird d[u] verwendet, aber d wird nirgendwo (ausser intial auf \infty bzw. 0)

Das ist mir auch aufgefallen. Alles in allem fand ich den dargebotenen Code ehr verwirrend. Die Variablen mit einzelnen Buchstaben zu bezeichnen mag zwar mathematisch zackig sein, foerdert aber keinesfalls die Lesbarkeit, da man immer wieder nachsehen muss, was nun eigentlich u und v und g und d usw war. Auf die Bedeutung von d wird praktisch gar nicht eingegangen, es wird fuer alle Knoten auf unendlich gesetzt, und dann niemals mehr veraendert. In der aktuellen Form weiss ich beim besten Willen nicht, wie das laufen soll, da f(u) ja wohl niemals groesser sein kann als ein Term, der d == ∞ beinhaltet. Das Beispiel mit den Staedten ist recht gut, und war auch das brauchbarste bzw verstaendlichste am ganzen Artikel. Die Satzkonstruktionen sind teilweise sehr stark verschachtelt und man muss einen satz oft mehrmals lesen, um ueberhaupt zu verstehen, was einem vermittelt werden soll. Ich hab den Artikel jetzt 3x gelesen und bruete darueber schon gut eine Stunde, und mir ist immer noch nicht alles klar.

Soweit ich den Algorithmus verstanden habe wird die Heuristik nur beim Finden des "Knoten mit geringsten Abstand zum Startknoten" verwendet. Die relax()-Funktion müsste also nur d[] (nicht h[] und/oder f[]) überprüfen und updaten. h[] bzw f[] spielen nur bei der Bewertung der Knoten in der Warteschlange eine Rolle, oder bin ich jetzt total auf dem Holzweg? Auf jeden Fall muss relax() d[] updaten, sonst funktioniert das Ganze nicht. Wormbo 18:08, 12. Mai 2007 (CEST)

Ja, das updaten von d[] fehlt im Pseudocode. f[] muss natürlich aber auch geupdatet und irgendwo gespeichert werden, denn wie soll eine Prioritätswarteschlange funktionieren, wenn Prioritäten nicht gespeichert werden.

Die Zeile "if f[v] > d[u] + w(u,v) + h[v] {" der Relax Funktion ist aber so nicht notwendig, denke ich. Schliesslich gilt beim Aufruf der Funktion doch f[v] = d[v] + h[v] und somit kann man h[v] auf beiden Seiten abziehen und man erhält genau die gleiche Relax Funktion wie bei Dijkstra (mit zusätzlichem Update von f). Entscheidend ist wie Wormbo schon sagt, dass die Prioritätswarteschlange bei der pop() Funktion den Knoten v mit dem geringsten f[v] Wert zurückliefert. Dass die Änderung von f darauf direkten Einfluss hat, ist so recht schwierig zu sehen, finde ich. Vielleicht sollte man da eine Funktion wie decreaseKey() verwenden? Oder habe ich den Algo nicht richtig verstanden? Decay 02:21, 7. Aug. 2007 (CEST)

Fehler (25.04.07)

Fordert man von der Heuristik, dass sie monoton ist, also den tatsächlichen Weg zwischen zwei Knoten nie überschätzt, so kann man beweisen, dass der A*-Algorithmus tatsächlich immer einen kürzesten Weg findet. Dies bedeutet jedoch im Umkehrschluss auch, dass der Algorithmus nicht mit Sicherheit den kürzesten Weg zum Ziel findet, falls man eine sehr schlechte Heuristik verwendet.

Wenn es regnet, ist die Strasse nass. Wenn es also nicht regnet, ist die Strasse nicht nass?

Nur weil $A\Rightarrow B$. gilt, heisst das ja noch lange nicht, dass auch $\neg A\Rightarrow \neg B$ gilt, den letzteres ist schliesslich equivalent zu $B\Rightarrow A$.

169.237.6.179 00:45, 26. Apr. 2007 (CEST)

Fehler im Pseudocode A-Star

Der Algorithmus initialisiert die Abstände zu allen Knoten, ausser dem Start, mit unendlich (Zeile 01). In Zeile 02 werden nun alle Knoten in die Queue gedrückt ("// Füge alle Knoten aus dem Graph in die Warteschlange ein"). Nun soll in Zeile 05 der Knoten mit dem geringsten Abstand zum Startknoten untersucht werden. Dieser ist laut Def des Queues dessen erster. Nur sind alle Abstände unendlich! => Zufall, welcher Knoten als letztes eingefügt wurde. Sollte ich nun den Zielknoten ziehen rufe ich die Rückverfolgung (reconstructShortestPath(g)) auf. Dieser ist es natürlich unmöglich den Pfad zu finden. Ich denke der Fehler liegt in der Füllung der Queue, bzw in dem zugehörigen Kommentar. Ich gehe davon aus, dass alle vom Startknoten aus direkt zu erreichenden Knoten eingefügt werden sollen.

edit: Ok, habe nochmal nachgelesen und festgestellt, dass der Knoten mit dem kleinsten f(v) aus der Queue geholt werden soll. Dies sollte aber auch IMHO in den Kommentaren stehen. Jedoch gibt es hier ebenfalls ein Problem, da f(v) = d(v) + h(v) gilt, jedoch d(v) = unendlich. => f(v) = unendlich. Eine Lösung wäre natürlich d(v) für alle Knoten mit einem ausreichend hohen Wert zu initialisieren.

Der Fehler liegt daran, dass im Pseudocode die Anpassung Abstandsschätzer d[v] fehlt. Wie im Dijkstra muss d[v] beim Relaxieren einer Kante (u,v) auf d[v] = d[u] + w(u,v) gesetzt werden. Im Pseudocode wird nur die Funktion f[] angepasst.

Der Code von relax ist auch falsch: "if f[v] = ∞" Es wird also nur etwas gemacht, wenn der Knoten v zum ersten Mal gefunden wird. Im Beispiel mit den Städten wird aber der Zielknoten München zweimal besucht was mit obigem Code gar nicht geht. --Sargeras 20:02, 17. Nov. 2007 (CET)

Umkehrung der Implikation falsch

Fordert man von der Heuristik, dass sie monoton ist, also den tatsächlichen Weg zwischen zwei Knoten nie überschätzt, so kann man beweisen, dass der A*-Algorithmus tatsächlich immer einen kürzesten Weg findet. Dies bedeutet jedoch im Umkehrschluss auch, dass der Algorithmus nicht mit Sicherheit den kürzesten Weg zum Ziel findet, falls man eine sehr schlechte Heuristik verwendet.

Heißt es nicht. Man kann nichts schließen für den Fall, dass die Heuristik nicht monoton ist. 212.95.112.16 20:30, 22. Mai 2007 (CEST)