Wann garantiert A* einen optimalen Pfad?

Wenn die Heuristik die wahren Restkosten nie überschätzt (zulässig) und, bei effizienten Umsetzungen mit konsistenter **h**, Gleichstände korrekt behandelt werden. Manhattan ist zulässig auf dem 4-nachbarschaftlichen einheitlichen Gitter; oktil passt zu diagonalen Zügen der 8-Nachbarschaft.

Wodurch unterscheidet sich die gierige Bestensuche von A*?

Die gierige Suche expandiert Knoten nur nach **h** und ignoriert **g**, daher kann sie durch teures Gelände auf das Ziel zurasen. **A*** wichtet bereits gezahlte Kosten **g** und die Restschätzung **h** über **f = g + h**.

Wozu offene und geschlossene Menge ansehen?

Die offene Menge ist die Front der Kandidaten; die geschlossene ist bereits expandiert. Ihr Wachstum zeigt, welchen Anteil der Karte jedes Verfahren erkundet, bevor der Pfad festliegt.

A* und Dijkstra (Gitter)

Gitter 40×28: A*, Dijkstra oder gierige Suche; Heuristiken, 4- und 8-Nachbarschaft, Wände und teure Zellen; Färbung der offenen und geschlossenen Menge.

Zum Modell

**A* und Dijkstra suchen auf einem Gitter einen Weg geringer Kosten vom Start zum Ziel auf einer Karte 40×28. Verglichen werden der Algorithmus von Dijkstra (einheitliche Kosten), A* mit f = g + h und die gierige Bestensuche, mit den Heuristiken Manhattan / oktil / euklidisch und 4- oder 8-Nachbarschaft. Wände und teure Zellen zeichnet man von Hand; sichtbar wachsen offene und geschlossene Menge. A* ist optimal effizient unter den optimalen Verfahren, wenn h zulässig ist; Dijkstra ist der Fall h = 0; die gierige Suche folgt nur h** und kann schnell, aber suboptimal sein. Diskrete Suche auf dem Gitter, ohne nachträgliche Pfadreparatur, Sprungpunktsuche und stetige Sichtbarkeitsgraphen. Algorithmus, Heuristik und Nachbarschaft ändern das Expansionsbild und die Pfadkosten.

Für wen: Algorithmen und Pfadplanung: A*, Dijkstra, Heuristiken auf dem Gitter.

Wichtige Begriffe

a*-suche
dijkstra-algorithmus
heuristik
offene menge
wegsuche auf dem gitter
zulässige heuristik

So funktioniert es

Auf dem Gitter 40×28 wird ein Weg vom Start zum Ziel gesucht. Dijkstra expandiert nach den Kosten g, A* nach f = g + h, die gierige Suche nur nach h. Heuristiken Manhattan, oktil und euklidisch; 4- oder 8-Nachbarschaft. Auf dem Schirm: offene und geschlossene Menge und der gefundene Pfad.

Wichtige Gleichungen

A*: f(n) = g(n) + h(n), open := min-heap by f

Manhattan h = |Δr| + |Δc|; Octile h = max + (√2−1)·min

Häufige Fragen

Wann garantiert A* einen optimalen Pfad?: Wenn die Heuristik die wahren Restkosten nie überschätzt (zulässig) und, bei effizienten Umsetzungen mit konsistenter h, Gleichstände korrekt behandelt werden. Manhattan ist zulässig auf dem 4-nachbarschaftlichen einheitlichen Gitter; oktil passt zu diagonalen Zügen der 8-Nachbarschaft.
Wodurch unterscheidet sich die gierige Bestensuche von A*?: Die gierige Suche expandiert Knoten nur nach h und ignoriert g, daher kann sie durch teures Gelände auf das Ziel zurasen. A* wichtet bereits gezahlte Kosten g und die Restschätzung h über f = g + h.
Wozu offene und geschlossene Menge ansehen?: Die offene Menge ist die Front der Kandidaten; die geschlossene ist bereits expandiert. Ihr Wachstum zeigt, welchen Anteil der Karte jedes Verfahren erkundet, bevor der Pfad festliegt.

Machen Sie mit verwandten Themen in dieser Kategorie weiter — oder alle 48 in „Ingenieurwesen“.

Ganze Kategorie →

NeuSchule

Labyrinthe und A*

Simulation starten

Ideale Labyrinthe auf dem Gitter 40×28: rekursiver Rückverfolger, Wilson, Eller oder zufälliger Prim; Lösung mit A* (Manhattan, 4-Nachbarschaft). Wände nachzeichnen und Start sowie Ziel versetzen.

NeuSchule

Minimaler Spannbaum (Prim und Kruskal)

Simulation starten

Zufällige Punkte in der Ebene, vollständiger Graph mit euklidischen Gewichten: Prim schrittweise von der Wurzel oder Kruskal mit Union-Find; Vergleich der Gesamtgewichte.

NeuSchule

RRT-Pfadplaner (Gitter)

Simulation starten

Dieselbe Wandkarte 40×28: zufällige Proben, nächster Knoten, Schritt mit Kollisionsprüfung, Verschiebung der Stichprobe zum Ziel; Taste zum Vergleich mit A*.

NeuSchule

Balkenbiegung: Einheitslastverfahren

Simulation starten

Gelenkig gelagerter Euler-Bernoulli-Balken mit Kraft P und Streckenlast w: analytische Durchbiegung gegen das Integral der virtuellen Arbeit ∫Mm/EI dx.

NeuSchule

Dünnwandiger Druckbehälter

Simulation starten

Membranspannungen in Zylinder und Kugel: Umfangsspannung σθ, Längsspannung σz, Vergleichsspannung nach von Mises, Prüfung r/t und Sicherheit gegen Fließen.

NeuSchule

Planetengetriebe

Simulation starten

Sonne, Planeten, Hohlrad: Willis-Gleichung; halten Sie Hohlrad, Sonnenrad oder Steg fest und vergleichen Sie die Übersetzungen.

A* und Dijkstra (Gitter)

Zum Modell

So funktioniert es

Wichtige Gleichungen

Häufige Fragen

Ähnliche Simulationen

Labyrinthe und A*

Minimaler Spannbaum (Prim und Kruskal)

RRT-Pfadplaner (Gitter)

Balkenbiegung: Einheitslastverfahren

Dünnwandiger Druckbehälter

Planetengetriebe

A* und Dijkstra (Gitter)

Zum Modell

So funktioniert es

Wichtige Gleichungen

Häufige Fragen