Diskussion:A*-Algorithmus

Alte oder nicht mehr zur aktuellen Version des Artikels passende Beiträge sind im Archiv zu finden.

A vs. A*

Was bedeutet der * in A*? Danke, --Abdull 22:42, 4. Mär 2006 (CET)

Ich habe in der Vorlesung gelernt, dass der hier beschriebene Algorithmus eigentlich A-Algorithmus (ohne Stern) heißt, also in der allgemeinen Form

• f(v) = g(v) + h(v).

Wenn die Funktion h(v) zusätzlich folgende Eigenschaft aufweist, spricht man vom A*-Algorithmus:

• h(v) <= h*(v)

wobei h*(v) die Bewertung eines optimalen Pfades von v zu einer Lösung darstellt.

Ich habe das Buch gerade nicht zur Hand aber laut Vorlesungsskript soll das wohl im Russel/Norvig so definiert sein.

--Cerno 23:03, 5. Nov. 2006 (CET)

Hm, ok, dann will ich mal versuchen etwas dazu zu schreiben: Also zuerst einmal: So weit ich weiß wird in AIAMA (Russel / Norvig) nie von einem Algorithmus namens "A search" gesprochen. Wenn du mir eine Seitenzahl geben kannst wo es stehen soll, kann ich gerne nochmal genauer nachgucken.

wobei h*(v) die Bewertung eines optimalen Pfades von v zu einer Lösung darstellt. Was meinst du mit Bewertung eines optimalen Pfades (h*(v))? Falls du damit die tatsächlichen Kosten um zum Ziel zu kommen meinst, dann ist die von dir beschriebene Eigenschaft nichts anderes als die im Artikel genannte Zulässigkeit. (die geschätzte Entfernung zum Ziel darf die tatsächliche Entfernung zum Ziel nie überschätzen). Außerdem verwundert mich dein zu einer Lösung etwas: Es dürfte im allgemeinen recht schwierig werden eine Heuristik zu finden, welche für mehrere verschiedene Lösungen gleichmäßig gültig ist. (Bsp Roadmap: Wenn ich von Frankfurt nach München oder Hamburg will, was soll die Heuristik mir sagen? Soll ich nach Norden oder nach Süden?) --Regnaron 20:14, 6. Nov. 2006 (CET)

Die oben angeführte Bedingung $h(v)\leq h^{*}(v)$ entspricht wie schon von Regnaron gesagt der Definition für eine zulässige Heuristik.

Zu A vs. A*: In der englischen Wikipedia steht zu diesem Thema, dass der Algorithmus ursprünglich nur Algorithmus A hieß. Da der Algorithmus optimal ist, wenn die verwendete Heuristik bestimmte Bedingungen erfüllt (ich nehme mal an: Monotonie), nannte man ihn A*. Ich stelle mal weitere Vermutungen an: Im unter Literatur angegebenen Paper von 1968 wurde der Algorithmus A vorgestellt (in der allgemeinen Form $f=g+h$). Im ebenfalls genannten Paper von 1972 (Corrections to ...) wurde die Monotonie-Bedingungen der Heuristik vorgestellt und der Algorithmus in A* umbenannt. Weiß jemand wo man diese Paper herbekommen könnte?

Tauscht man die Zulässigkeits Bedingung gegen die Monotonie Bedingung aus, würde meine Vermutung ja der von Cerno aufgestellten Behauptung entsprechen...

--Sargeras 17:11, 11. Dez. 2007 (CET)

@Ragnaron: Eine Heuristik für die geographische Wegsuche die immer gültig ist, ist die Euklidische Entfernung. Da man niemals schneller sein kann als die "Luftlinie". --2001:470:7B1D:FF:B6B6:76FF:FE94:9CFB 17:48, 29. Apr. 2014 (CEST)

Formulierung f / f(x)

Es ist beschrieben, dass allen bekannten Knoten ein Wert f zugeordnet wird. Es ist aber nicht ein Wert, sondern jeweils ein Wert. Das jedem bekannten Knoten n ein Wert f(n) zugeordnet wird, wäre klarer formuliert. (nicht signierter Beitrag von Cryogen (Diskussion | Beiträge) 13:57, 5. Jan. 2008)

Sei mutig! Formulierung ist nun verbessert. --Sargeras 23:00, 8. Jan. 2008 (CET)

Fehler im Artikel

Ist der Algorithmus wirklich optimal?

"Der Algorithmus ist vollständig und optimal. Das heißt, dass immer eine optimale Lösung gefunden wird, falls eine existiert. " Dieser Satz widerspricht der Aussage aus diesem Paper, wo A* explizit als nicht optimal beschrieben wird. "a best-first search algorithm, which can handle the shortest path search with a faster time but not always optimum" (https://ieeexplore.ieee.org/abstract/document/9190342) (nicht signierter Beitrag von 46.223.163.72 (Diskussion) 18:56, 19. Feb. 2023 (CET))

Beispiel: fehlerhaft

Ist im Beispiel nicht ein eklatanter Fehler? "Die verwendete Heuristik darf die Kosten nie überschätzen. Für das Beispiel der Wegsuche ist die Luftlinie eine geeignete Schätzung: Die tatsächliche Strecke ist nie kürzer als die direkte Verbindung." ist meiner Meinung nach ein Widerspruch zu "Die tatsächlichen Kosten von Ludwigshafen nach Würzburg weichen deutlich von der Schätzung ab, da in diesem Beispiel nur Autobahnen verwendet werden sollen." Also geschätze Länge: 183km, echte Länge nun nur noch 75km (nicht signierter Beitrag von 89.244.164.182 (Diskussion) 03:40, 25. Jun. 2012 (CEST))

Bei Schritt 2 heißt es z.B. auch "Der Weg über Kaiserslautern ist mindestens 228 km lang". Das müsste dann höchstens heißen und der ganze Satz macht keinen Sinn mehr. (nicht signierter Beitrag von 31.17.30.4 (Diskussion) 01:02, 5. Mär. 2015 (CET))

Comment: Sargeras

Die angesprochenen Fehler wurden im Zuge meiner Komplett-Überarbeitung inzwischen verbessert. Sobald ich genügend Zeit habe, will ich den Artikel noch ein wenig erweitern (Baumsuche, Graphsuche) und ihn erneut auf den 'Lesenswert' Status überprüfen lassen. --Sargeras 17:55, 19. Dez. 2007 (CET)

Heuristik: zulässig - monoton

diesen Abschnitt habe ich im Artikel mittlerweile verbessert --Sargeras 11:56, 9. Dez. 2007 (CET)

Die Aussage "Zulässige Heuristiken dürfen zwar nie die Kosten bis zum Ziel, aber sehr wohl die Kosten von einem Knoten zum nächsten, überschätzen." ist falsch oder zumindest irreführend.

Beim A*-Algorithmus werden nie die Kosten zum Nachbarknoten geschätzt, sondern immer nur zum Zielknoten. Da sowohl eine zulässige als auch eine monotone Heuristik die Kosten bis zum Ziel nie überschätzt wären die beiden Typen also austauschbar! (Wenn man die Verwendung als Heuristik im A*-Algorithmus beschränkt.)

Ich werde den entsprechenden Abschnitt gründlich überarbeiten, sobald ich ein passendes Beispiel gefunden habe, an dem der Unterschied zwischen zulässig und monoton deutlich wird.

--Sargeras 21:41, 17. Nov. 2007 (CET)

Bei Deiner Änderung hast Du diesen Abschnitt entfernt, den ich für sinnvoll halte. Sollte diese Information zur Wahl der Heuristik nicht wieder rein? --Mathemaduenn 16:54, 9. Dez. 2007 (CET)

Den Abschnitt in seiner Gesamtheit finde ich nicht sinnvoll, da viel geredet wird, ohne etwas auszusagen. Aber ich hab ihn auf meiner Seite archiviert, um die sinnvollen Elemente später wieder in den Artikel zu integrieren.

--Sargeras 21:13, 9. Dez. 2007 (CET)

Zeitkomplexität

Die angegebene Abschätzung der Laufzeit ist recht wertlos:

• Wenn eine Abschätzung der Worst-Case Laufzeit gemacht wird, kann man dabei keine amortisierten Laufzeiten von Fibonacci-Heap Operationen verwenden.
• Es stimmt zwar, dass ein Element in einem Fibonacci-Heap (wie auch in vielen anderen Implementationen einer Prioritätswarteschlange) sehr effizient verschoben werden kann (nachdem die Priorität bzw. der f-Wert geändert wurde), aaaber das teure an dieser Operation wird hier einfach unterschlagen: Das entsprechende Element ist meist nur mit linearer Laufzeit zu finden!

siehe Fibonacci-Heap:

Die Operationen remove und decreaseKey setzen voraus, dass man die Position der entsprechenden Elemente im Heap kennt. Im Allgemeinen ist es nämlich nicht möglich effizient ein Element im Heap zu suchen.

--Sargeras 11:56, 9. Dez. 2007 (CET)

Und was ist wenn ich beherzige was in Fibonacci-Heap nach dem von Dir zitierten steht und einen Zeiger mitführe z.B. mit der closed list zusammen ? --Mathemaduenn 16:35, 9. Dez. 2007 (CET)

Dieses Zeiger mitführen war mir auf den ersten Blick suspekt, allerdings kann ich erst jetzt genauer sagen, warum das nicht bzw. nur sehr eingeschränkt möglich ist. Erstens ändert sich die Position der Elemente im Heap ständig, was man noch dadurch kompensieren kann, dass der Zeiger entsprechend geupdatet wird. Aber zweitens muss auch das aufrufende Programm irgendwann eine beträchtliche Menge an Zeigern verwalten, was im Allgemeinen nicht in konstanter Zeit geht. Das Ganze funktioniert nur, wenn die Daten z.B. mit natürlichen Zahlen indiziert sind, deren Bereich bekannt ist. Dann können die Zeiger-Daten-Paare in einem Array mit konstanter Zugriffszeit gespeichert werden. --Sargeras 00:33, 1. Feb. 2008 (CET)

Dann gehts schneller als linear :-) Nein, im Ernst: Der Abschnitt Zeitkomplexität stammt noch aus dem alten Artikel. Ich wollte hier nur eine Begründung liefern, warum ich den Abschnitt überarbeiten muss. Auch mit dem angesprochenen Zeiger kann man die Laufzeit der Suchoperation nicht einfach unter den Tisch fallen lassen, wenn der Zeiger kostenlos wäre, würde man den ja immer benutzen. Ich bin ich der Meinung, dass der Artikel an dieser Stelle viel zu ungenau ist. Mit einem Verweis auf den Fibonacci-Heap wurde da die gesamte Laufzeitanalyse erschlagen. --Sargeras 22:20, 9. Dez. 2007 (CET)

Der Abschnitt Zeitkomplexität ist nun komplett neu. Es kommt auch fast das gleiche Ergebnis raus. Ganz zufrieden bin ich damit aber noch nicht - weil immer noch zu ungenau... Ich finde diese ganze worst-case Abschätzung ist sowieso nicht aussagekräftig. Kommentare dazu sind willkommen! --Sargeras 21:37, 11. Dez. 2007 (CET)

Es kommt halt im Wesentlichen auf die Genauigkeit der Heuristik an da kann man aber imho schlecht Zahlenwerte dazu aufschreiben und muß mehr beschreiben. Grüße --Mathemaduenn 20:55, 12. Dez. 2007 (CET)

Ich bin der Meinung, dass die Implementierung der Open List mindestens genauso wichtig ist. Wie würdest du die Zeitkomplexität genauer beschreiben bzw. welche Punkte fehlen dir in meiner Beschreibung? --Sargeras 15:21, 18. Dez. 2007 (CET)

Hallo, ich habe auch nochmal drüber nachgedacht. Man will doch eigentlich immer nur das erste Element der Warteschlange finden. Dies kann dann extrahiert werden. So das mMn kein Finden notwendig ist. Grüße --Mathemaduenn 22:12, 5. Feb. 2008 (CET)

Doch, manchmal müssen Elemente in der Warteschlange gesucht werden, um die Priorität ändern zu können. Im Beispiel passiert das in Schritt 4 mit dem Knoten Würzburg. --Sargeras 22:59, 5. Feb. 2008 (CET)

Man könnte aber Mehrfacheinträge des gleichen Knotens zulassen und diesem ein "ist bereits entwickelt" - bit verpassen so das man mitbekommt falls man den gleichen Knoten nochmals entwickeln möchte. So muß man den Wert nicht ändern --Mathemaduenn 21:11, 6. Feb. 2008 (CET)

Interessante Idee. Allerdings ist dann die Anzahl der Elemente im Heap nicht durch die Anzahl der Knoten begrenzt und theoretisch beliebig groß. Welcher Ansatz bei welchem konkreten Fall besser ist, müsste jemand testen.

Ob solche Implementierungsdetails das Verständnis des Algorithmus fördern? (Die Anmerkung zur indirekten Implementierung der Closed List ist auch so ein Implementierungsdetail. Das ist im Artikel drin, weil scheinbar viele der Meinung sind, dass man die Closed List einfach weglassen kann, denn sie haben den Algorithmus erfolgreich ohne Closed List implementiert.) --Sargeras 14:46, 10. Feb. 2008 (CET)

Unterschied im Pseudo Code zur englischen Version

Der Pseudo Code ist nicht gleich wie in der englischen Version der Wikipedia. Dort wird untersucht ob der G-Kosten des Knotens niedriger sind als die neu berechneten:

 elseif tentative_g_score < g_score[y]
   tentative_is_better := true

In der deutschen Version werden die F-Kosten verwendet:

 if openlist.contains(successor) and f > openlist.find(successor).f then
   continue

Ist das Absicht und wenn ja, was ist der Unterschied, wie wirkt er sich aus? -- 81.26.172.73 10:19, 27. Aug. 2010 (CEST)

In der englischen Version wird g mit g verglichen, in der deutschen Version f mit f. Der Unterschied ist nur, dass in der deutschen Version auf beiden Seiten der Ungleichung noch jeweils h dazugezählt wird. Es gilt: f = g + h. Die Addition des selben Wertes auf beiden Seiten einer Ungleichung ändert aber nichts. Die Funktionsweise ist also identisch. -- Sargeras 15:30, 27. Aug. 2010 (CEST)

Es gibt doch einen minimalen Unterschied: Falls mehrere Wege zu einem Knoten gefunden werden, die alle gleich lang sind, dann wird in der deutschen Version der zuletztgefundene Weg ausgewählt, in der englischen Version der zuerstgefundene. (Falls die Ungleichung eine Gleichung ist, wird der gerade gefundene Weg in der deutschen Version weiterbenutzt, in der englischen Version aber verworfen. Solche Implementierungsdetails sind in der Antwort zu "Anfängerfrage - mehrere optimale Lösungen" gemeint.) -- Sargeras 15:46, 27. Aug. 2010 (CEST):

Ich sehe noch einen weiteren Unterschied: In der englischen Version wird für neuberechnete Kosten die günstiger sind als die alten G-Kosten eines Knoten alle Werte für diesen Knoten angepasst, sowohl F,G als auch H (H sollte allerdings gleich bleiben). Da G verwendet wird um die Knoten der Nachfolgeknoten zu berechnen, können die Kanten in der Lösung hier alte Kosten bekommen. Theoretisch kann je nach Wahl von H so ein Fall auftreten. Es ist nicht einfach aus dem Stehgreif so ein Beispiel zu konstruieren, aber ich hatte in meiner Beispielanwendung nur mit der Version der englischen Wikipedia erfolg. Kann natürlich aber auch an meiner Implementierung liegen. -- 81.26.172.73 19:21, 27. Aug. 2010 (CEST)

Ich glaube ich habe 'dein' Problem gefunden: Im Pseudo-Code der deutschen Wikipedia hat die Zeile gefehlt, in der der g Wert des Nachfolgeknotens gesetzt wird. Wenn man das vergisst, ergibt g[currentNode] immer 0 (natürlich nur, falls die Werte im Array von der verwendeten Programmiersprache auch mit 0 initialisiert werden). Ich habe den Code verbessert. Damit die Verwirrung in Zukunft nicht mehr so groß ist, habe ich auch die Ungleichung so geändert, dass sie nun der Version in der englischen Wikipedia entspricht. Ich hoffe geholfen zu haben. -- Sargeras 11:03, 11. Sep. 2010 (CEST)

Anfängerfrage - mehrere optimale Lösungen

Ich bin warhaftig kein Informatiker, aber war macht der Algorithmus eigentlich wenn zwei Wege exakt gleich gut bewertet werden? Djchrisi 22:56, 25. Nov. 2007

Dann wird einer dieser zwei Wege ausgegeben. Welcher davon ausgegeben wird hängt vom Zufall von Implementierungsdetails ab. Irgendwann müssen in diesem Fall zwei Knoten mit gleichem f Wert in der Open List sein, und davon ist halt einer am Anfang der Prioritätswarteschlange. Sobald ein Zielknoten expandiert wird, wird dieser als Lösung ausgegeben. Der Algorithmus garantiert nur, dass es keinen besseren Weg gibt. --Sargeras 10:41, 27. Nov. 2007 (CET)

Abschnitt Verwandte Algorithmen

Die Beschreibung, dass bei "dem" Greedy-Algorithmus g=0 unf f=h gilt, halte ich insofern für falsch, da es zum einen nicht "den" Greedy-Algorithmus gibt und zum anderen gerade f=g einem Greedy-Algorithmus entspricht. Der Dijkstra selbst wird in der Wikipedia als Greedy-Algorithmus bezeichnet, was meiner Meinung nach auch korrekt ist. Somit ist die Beschreibung im besagten Abschnitt inkonsistent mit der des Dijkstra-Algorithmus. --Gero 14:21, 24. Jan. 2008

Ich gebe dir Recht, dass es nicht "den" Greedy-Algorithmus gibt. Insofern ist die Formulierung verbesserungswürdig.

Aber deine Behauptung f=g wäre ein Greedy-Algorithmus ist meiner Meinung nach falsch. Ich habe den (ebenfalls falschen) Absatz im Dijkstra-Algorithmus Artikel, auf den du dich beziehst, mit entsprechender Begründung (Diskussion:Dijkstra-Algorithmus) gelöscht.

War der Dijkstra Artikel die einzige Quelle, die f=g als Greedy-Algorithmus bezeichnet?

--Sargeras 12:37, 29. Jan. 2008 (CET)

Ich habe dies in der Wikipedia nur beim Dijkstra-Algorithmus gelesen. Allerdings ist ein Greedy-Algorithmus meiner Meinung nach einer, der möglichst kurzsichtig handelt. Die Klassifizierung auf den A*-Algorithmus angewandt halte ich daher für relativ schwammig. Ich sehe jedenfalls keinen Grund, warum f(x)=h(x) greedy ist und f(x)=g(x) nicht.

--Gero 11:09, 5. Feb. 2008 (CET)

Mein Verständnis, was ein Greedy-Algorithmus ist, ist mit dem, was in Wikipedia steht, wohl nicht vereinbar. Allerdings ist auch Wikipedia nicht konsistent. Überall steht, dass Dijkstra ein Greedy-Algorithmus wäre, aber nirgendwo wird A* als solcher bezeichnet. Beide Algorithmen sind aber abgesehen von der Bewertungsfunktion äquivalent, sodass entweder beide greedy sein müssten, oder keiner. Ich bin verwirrt...

(Der Vollständigkeit halber auch noch hier der Link zu meinem Vergleich von A*, Dijkstra und Greedy.)

--Sargeras 23:14, 5. Feb. 2008 (CET)

Weiterführende Literatur / andere Algorithmen

Es gibt eine Verbesserung des A* von Tony Stentz. Sollte vieleicht ich die Linkliste aufgenommen werden. Einen passenden Wiki-Eintrag habe ich schon online gestellt. Orginal-publikation: http://www.frc.ri.cmu.edu/~axs/doc/icra94.pdf

Originalartikel

Ist es rechtlich in Ordnung das Originalpaper von Peter E. Hart and Nils J. Nilsson and Bertram Raphael im A*-Artikel zu verlinken? Das gibt es zum Beispiel hier:[1] (nicht signierter Beitrag von 129.217.189.10 (Diskussion | Beiträge) 17:40, 15. Feb. 2010 (CET))

http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf ist ein Link von Seite der Publikationen von Nils J. Nilsson der Standford University --Miracle173 (Diskussion) 08:15, 1. Jul. 2018 (CEST)

Start und Zielknoten vertauschen

"Bedingt durch die Vorgängerzeiger wird der gefundene Weg vom Ziel ausgehend rückwärts bis zum Start ausgegeben. Um den Weg in der richtigen Reihenfolge zu erhalten kann z. B. vor der Wegsuche Start und Ziel vertauscht werden. Somit wird vom eigentlichen Ziel zum Start gesucht und die Wegausgabe beginnt beim ursprünglichen Startknoten."

In meinen Augen ist das Quatsch. Diese Vorgehensweise funktioniert nur im ungerichteten Graphen, was aber eher nicht die Regel ist. Das sollte man erwähnen. (nicht signierter Beitrag von 79.214.17.84 (Diskussion | Beiträge) 14:03, 14. Apr. 2010 (CEST))

Anmerkung uneindeutig formuliert

Die Anmerkung ist uneindeutig formuliert. "Wird keine Closed List benutzt, muss anderweitig sicher gestellt werden, dass Knoten nicht mehrfach untersucht werden." Das gilt doch nicht, wenn sie wie beschrieben indirekt implementiert wird? Der Abschnitt sollte etwas klarer strukturiert werden. (nicht signierter Beitrag von 88.77.118.0 (Diskussion) 02:25, 5. Jun. 2010 (CEST))

Schritt 6 - Bild fehlerhaft

Hallo! Im 6. Schritt der Schritt-für-Schritt-Anleitung ist euch ein Fehler unterlaufen. "Heilbronn" muss dort auch auf die "Closed List" gesetzt werden, oder nicht? Der kürzeste Weg dorthin ist ja bekannst.

-- Springfreaky 15:52, 8. Nov. 2010 (CET)

In Schritt 5 sind Heilbronn und Würzburg auf der Open List. In Schritt 6 wird Würzburg untersucht und der Algorithmus bricht mit "Aha Ziel gefunden" ab. Heilbronn verbleibt in der Open List und muß nicht untersucht werden. --Mathemaduenn 20:37, 8. Nov. 2010 (CET)

Heuristiken

Ich finde es unpassend, dass der Begriff einer Heuristik so umfassend im Artikel des A*-Algorithmus erklärt wird. Speziell für monotone und zulässige Heuristiken sollte es wie in der englischen Wikipedia auch eigene Artikel geben. Ich schlage daher vor, die beiden Abschnitte (5.1 und 5.2) auszugliedern. Johannes Simon 13:51, 1. Dez. 2010 (CET)

Derzeit (1.7.2018) kann ich in der englischsprachigen Wiki keinen Eintrag für monotone oder zulässige Heuristiken finden. Es würde mir auch nicht sehr sinnvoll erscheinen. Das sind einfach zwei Terme, die im Rahmen der Beschreibung des A*-Algorithmus von den Autoren erstellt wurden. Das ist durchaus üblich in der Mathematik. Vermutlich werden sie auch von anderen Autoren übernommen, die über den A*-Algorithmus schreiben. Darüber hinaus werden sie vermutlich nicht verwendet. Also ein eigener Wikieintrag wäre da eher verwirrend und unpassend.

--Miracle173 (Diskussion) 12:08, 1. Jul. 2018 (CEST)

h(x) woher?

Im Artikel wird mit keinem Wort beschrieben, woher der h-wert der Knoten genau kommt. Im Beispiel ist schon vorrausgesetzt, dass jeder Knoten eine geschätze entfernung zum Zielknoten kennt! Woher das ganze kommt, wird dabei nicht erklärt. (nicht signierter Beitrag von 78.42.61.165 (Diskussion) 14:23, 24. Mai 2011 (CEST))

Die verwendeten Heuristiken stammen aus der zu Grunde liegenden Modellierung der ursprünglichen Problemstellung als Graph und sind daher nicht Teil des eigentlichen Algorithmus (und daher auch nicht relevant für den Artikel). Das Beispiel der Luftlinie für Abstandsmaße ist sogar schon genannt worden, in einem HMM zur automatischen Spracherkennung werden dagegen bestimmte Produkte bedingter Wortwahrscheinlichkeiten verwendet werden usw. Es ist also gar nicht möglich hier allgemeingültig anzugeben, woher diese Schätzungen stammen.

-- 82.119.29.173 04:24, 19. Feb. 2013 (CET)

Klassifizierung als Best-first search

In der englischsprachigen Wikipedia wird korrekterweise darauf hingewiesen, dass der A* eine spezielle Form der best-first search ist. Manche nennen diese im deutschen "Bestensuche". Ob die Übersetzung so korrekt ist, ist fraglich, aber es ist der meiner Meinung nach passenste deutsche Begriff. Ich habe auch bereits den englischen Artikel zur best-first search als Bestensuche in die d. Wikipedia übersetzt.

Nun ist die Frage: Ist die Bezeichnung "Bestensuche" als Übersetzung sinnvoll? Wie würdet ihr die best-first search im Deutschen bezeichnen? Wenn wir uns da einigen können, kann auch der A* als solche in der d. Wikipedia klassifiziert werden. -- Johannes Simon 04:55, 25. Aug. 2011 (CEST)

Zunächst zu deiner Frage: Wenn es keine gebräuchliche Übersetzung für "best-first search" bzw. "best-first-Suche" (so kenne ich diesen Begriff aus einer Vorlesung), dann sollte hier auch nicht krampfhaft eine eingeführt werden.

Jetzt zu dem dahinter stehenden Sachverhalt: So weit mir bekannt ist (aus besagter VL), ist der A* kein Spezialfall von best-first sondern eine Verallgemeinerung: Nur dann, wenn man die Schätzfunktion $h$ als konstant 0 annimmt, was die Kosten ja nun wahrlich nicht überschätzt, expandiert A* immer nur den (bisher) vielversprechendsten Knoten.

Möglicherweise unterscheidet sich aber auch einfach die Auffassung des entsprechenden Dozenten von der, der in der englischen Wikipedia zitierten Autoren, das ist ja in der Algorithmik nicht ungewöhnlich.

-- 82.119.29.173 03:56, 19. Feb. 2013 (CET)

monoton nicht immer zulässig

Entgegen der Behauptung im Artikel kann eine monotone Bewertung ungültig sein, wenn der Zielknoten eine Bewertung größer null hat.

Ich weiß allerdings nicht, wie ich das im Artikel geschickt formulieren könnte, mag jemand anderes das korrigieren?

--Mrwonko (Diskussion) 08:32, 22. Jan. 2014 (CET)

Funktionsweise - Animation

Ich habe Zweifel an der Korrektheit der Animation. Nachdem der A* das Hindernis erreicht hat, beginnt er die Knoten zu untersuchen die nahe am Startpunkt liegen, obwohl diese einen viel höheren "h(x)"-Anteil haben sollten als die bereits gefundenen Knoten direkt am Hindernis. Das gezeigte Verhalten kann vorkommen, wenn g(x) größer ist als h(x) prognostiziert hat. (nicht signierter Beitrag von 185.44.151.4 (Diskussion) 17:57, 29. Apr. 2014 (CEST))

Es ist zwar richtig das die Knoten beim Startknoten einen höheren h(x)-Anteil haben als die Knoten am Hindernis, aber das ist für den Algorithmus irrelevant. Der Algorithmus entscheidet aufgrund der Gösse von f(x), das ist g(x)+h(x), wobei g(x) die Länge des kürzesten Pfades com Startknoten zu x ist, der derzeit bekannt ist. Für einen Knoten in der nähe des Startknotens ist f(x) ungefähr gleich h(x), also der euklidische Abstand des Knotens zum Ziel. Kürzer geht es nicht.

-Miracle173 (Diskussion) 11:54, 1. Jul. 2018 (CEST)

Algorithmus ist falsch beschrieben

Ich habe mir den Artikel genauer angeschaut, weil ich vorhabe, den Algorithmus in Python zu implementieren. Und ich war schon ziemlich verwirrt. Letztlich habe ich den Artikel von Peter E. Hart, Nils J. Nilsson und Bertram Raphael gelesen, um den Algorithmus zu verstehen.

• Gleich zu Beginn des Artikels steht "Der A*-Algorithmus (...) dient (...) der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. (...) (und) verwendet (...) eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen(...). Der Algorithmus ist vollständig und optimal." Das ist eigentlich das, was ich erwartet habe.

• Dann wird "Die Idee des Algorithmus" kurz beschrieben und die Funktionen f,g und h werden erwähnt, und weiters "h(x) bezeichnet die geschätzten Kosten von x bis zum Zielknoten. Die verwendete Heuristik darf die Kosten nie überschätzen." Das h die im zweiten Satz erwähnte Heuristik ist, sollte vielleicht explizit erwähnt werden, mir ist das aber klar gewesen. Das h durch die die erwähnte Eigenschaft zu einer sogenannten "zulässigen" Heuristik wird, wie sie dann ziemlich weit unten im Artikle definiert wird, wird nicht erwähnt. Jedenfalls nimmt man nun also an, dass es sich im Folgenden bei h um eine solche zulässige Heuristik handelt.

• Im Abschnitt "Funktionsweise" wird behauptet, dass für die "abschließend untersuchten" Knoten gilt, dass der kürzeste Weg bekannt ist. Das ist aber nicht der Fall. Der Algorithmus wird falsch beschrieben. Ein Knoten, der in der CloseList ist, kann in dieser Beschreibung nicht mehr aus dieser in die OpenList wechseln. Das ist aber falsch. Das kann durchaus passieren. Es wird nicht erklärt warum das ganze funktionieren soll. Implementationsdetails, z,B, OpenList wird als Priority Queue, brauchen in der Beschreibung der Funktionsweise eigentlich nicht vorhanden sein. Das erhöht nur unnötig die Komplexität der Beschreibung.

• Der Pseudocode ist genauso falsch wie die vorhergehende Beschreibung. Er enthält wiederum unnötige technische Details. Fast jede Zeile Pseudocode ist durch ein oder zwei Zeilen Kommentar erklärt. Das ist nicht der Sinn von Pseudocode.

Den Rest habe ich mir nicht mehr genauer angeschaut.

Weitere Anmerkungen

• in der englischsprachigen Wiki steht der gleiche Pseudocode, anscheinend vom selben Autor. Dort wird nach dem Code angemerkt, das für den Algorithmus vorausgesetzt wird, das die Heuristik monoton und nicht nur zulässig ist. Ich glaube aber, dass auch das nicht ausreicht.

• Hier wird der A* Algorithmus auch beschrieben, und hier werden Elemente der ClosedList, die nur indirekt existiert, wieder auf die OpenList gesetzt.

• Ich habe mir die Vorgängerversion des Pseudocodes angeschaut 03:22, 22. Nov. 2007. Die ist auch falsche. Hier wird ein Knoten nur einmal modifiziert, d.h. selbst wenn er auf der OpenList ist, wird er nicht mehr modifiziert, selbst wenn ein besserer Pfad gefunden wird. Ich habe mir noch ältere Versionen des Pseudocodes angeschaut und die sind alle mehr oder weniger falsch.

• --Miracle173 (Diskussion) 15:33, 3. Jul. 2018 (CEST) Möglicherweise reicht die Monotonie einer Heuristik tatsächlich aus, das ein geschlossener Knoten nicht mehr geöffnet werden muss. In 'P. E. Hart, N. J. Nilsson, B. Raphael: Correction to „A Formal Basis for the Heuristic Determination of Minimum Cost Paths' wird darauf hingewiesen.

--Miracle173 (Diskussion) 08:16, 1. Jul. 2018 (CEST)

"Besucht" und "untersucht"

Im Abschnitt "Funktionsweise", unter der Auflistung der Knotenklassen, heißt es: "Jeder bekannte oder abschließend besuchte Knoten enthält einen Zeiger..." An jeder anderen Erwähnung in diesem Abschnitt wird von "abschließend untersuchten Knoten" gesprochen. Gibt es einen Grund, hier anstattdessen das Wort "besucht" zu benutzen oder ist das ein Versehen und es gehört auch hier "untersucht" hin? --Perfektionismus (Diskussion) 12:35, 29. Jul. 2019 (CEST)

Seite mit minimalem Code, die auf echten Daten routet?

Möglicherweise passt https://www.netzwolf.info/osm/routing/routing.html in die Link-Liste. Ich würde es aber als Spam ansehen, wenn ich einen Link auf eine eigene Seite setze. (Bitte einfach löschen, wenn es nicht passt.) (nicht signierter Beitrag von Wolfgang Stanglmeier (Diskussion | Beiträge) 23:35, 9. Okt. 2022 (CEST))

Aussagen über Closed List sind irreführend

Der Artikel erweckt den Anschein, dass eine Closed List verwendet werden muss, um die Korrektheit des Algorithmus zu garantieren. Für den Fall, dass die Heuristik admissible, aber nicht consistent ist, würde der Algorithmus, wie auf diesen Artikel beschrieben, keine korrekte Lösung liefern. Für solche Heuristiken ist es notwendig, Knoten mehr als einmal zu besuchen. Im englischen Artikel ist diese Einschränkung nicht vorhanden. --2003:E6:FF29:1700:AC13:C8CD:BE7C:998B 14:40, 25. Nov. 2024 (CET)