A* Spinoff

[mgaeckler]

@Dravere Richtig implementiert heißt:

• Die Heuristic muß einen vernünftigen Wert liefern, beim Routing auf einer Straßenkarte kann das z.B. die Luftlinie sein + die bekannte Länge der bisherigen Route.
• Der geschätzte Wert darf niemals schlechter sein wie der tatsächliche Wert.
• Die erste gefundene Route heißt, wenn der gewünschte Zielknoten am Anfang der PriorityQueue steht. Es heißt nicht, wenn der gewünschte Zielknoten vom aktuellen Knoten direkt erreichbar ist.

Hoffe jetzt sind alle Klarheiten beseitigt.

VG Martin

[LeMace]

@mgaeckler sagte in Problem mit Set:

Der geschätzte Wert darf niemals schlechter sein wie der tatsächliche Wert

*als

[mgaeckler]

@LeMace sagte in Problem mit Set:

@mgaeckler sagte in Problem mit Set:

Der geschätzte Wert darf niemals schlechter sein wie der tatsächliche Wert

*als

Der durchschnittlich gebildete Preiß sollte meinen Satz auch ohne Deine Übersetzung lesen können.

[TGGC]

@mgaeckler sagte in Problem mit Set:

Die erste gefundene Route heißt, wenn der gewünschte Zielknoten am Anfang der PriorityQueue steht

Das ist falsch.

[Th69]

@TGGC: Was soll daran falsch sein?

[Dravere]

@Th69 sagte in Problem mit Set:

@TGGC: Was soll daran falsch sein?

Ich kann nur mutmassen bei einer so kurzen Aussage.

Aber rein von der Theorie geschaut, wenn der Algorithmus läuft, ist es möglich, dass der Zielknoten am Anfang in der Priority Queue eingefügt wird und dies noch nicht, die beste Route darstellt. Erst wenn alle Nachbarn abgearbeitet worden sind und der nächste Knoten aus der Priority Queue entnommen wird und dieser dem Zielknoten entspricht, dann haben wir die beste Route gemäss der Heuristik gefunden. Es ist somit wichtig, den Zeitpunkt zu betrachten, wann der Zielknoten im Verlauf des Algorithmus am Anfang der Priority Queue steht. Nur weil irgendwann einmal der Zielknoten am Anfang steht reicht noch nicht.

Es ist etwas pingelig.

[TGGC]

Wie bereits gesagt: Der Knoten wird anhand seiner Route in die Priority Queue sortiert. Wie soll also ein Knoten, zu dem noch keine Route bekannt ist, dort am Anfang stehen? Knoten mit unbekannter Route, stehen wenn überhaupt hinten mit inf Entfernung.

[Th69]

Du scheinst etwas anderes in den Satz hineininterpetiert zu haben, das da gar nicht steht.

Der A*-Algorithmus terminiert, sobald der Knoten mit dem geringsten Kostenwert (f) der Zielknoten ist (also am Anfang der PriorityQueue steht):

// Knoten mit dem geringsten f-Wert aus der Open List entfernen
currentNode := openlist.removeMin()
// Wurde das Ziel gefunden?
if currentNode == zielknoten then
    return PathFound

Und dies ist dann die "erste gefundene Route" (Rückwärts vom Zielknoten aus die Vorgängerknoten bis zum Startknoten verfolgen bzw. um umgekehrt den Hinweg zu haben, vertauscht man Start- und Zielknoten bei der Suche)...

[TGGC]

@Th69 sagte in Problem mit Set:

Und dies ist dann die "erste gefundene Route"

Falsch.

[mgaeckler]

@TGGC Bist Du Dir sicher, daß Du den A*-Algorithmus verstanden hast?

[mgaeckler]

@TGGC sagte in Problem mit Set:

@Th69 sagte in Problem mit Set:

Und dies ist dann die "erste gefundene Route"

Falsch.

Hast Du auch eine Begründung?

[TGGC]

@mgaeckler sagte in Problem mit Set:

@TGGC Bist Du Dir sicher, daß Du den A*-Algorithmus verstanden hast?

Ja bin ich. Begründungen kannst du nachlesen.

[mgaeckler]

@TGGC sagte in Problem mit Set:

@mgaeckler sagte in Problem mit Set:

@TGGC Bist Du Dir sicher, daß Du den A*-Algorithmus verstanden hast?

Ja bin ich. Begründungen kannst du nachlesen.

Wo? Hier hab ich noch keine gefunden.

[TGGC]

Dann kann ich dir leider nicht weiterhelfen.

[mgaeckler]

@TGGC Das betrachte ich nicht als Verlust.

[Columbo]

@TGGC @Dravere etc. keine Ahnung was das hier werden soll, aber es sieht immer peinlich aus, wenn Computerwissenschaftler sich erfolglos darüber streiten, was irgendeine völlig vage Phrase wie 'erste gefundene Route' in einem Algorithmus bedeutet (sie ist vage—auch wenn ich spüre, wie TGGC bereits seinen Widerspruch aufschreibt, weil er ja unbedingt die Zweckmässigkeit seiner Tiraden verteidigen muss....). Es geht in einer Wissenschaft nicht um die Bedeutung von Begriffen, sondern um die Wahrheit von Aussagen. Die Aussage war hier einfach nicht sinnvoll artikuliert. Naechstes mal @TGGC produktivere Beitraege zur Diskussion liefern, bitte. Closed.