Heuristische Baumsuche erklärt
Heuristische Baumsuche baut Teillösungen Schritt für Schritt auf und lässt sich dabei von einer Schätzung des Restwegs leiten, statt alles zu prüfen. Das durchgehende Beispiel ist ein Pfadproblem auf einem Straßen- oder Lagernetz mit Hindernissen: Start unten links, Ziel oben rechts, die Luftlinie zum Ziel als Heuristik. Die Suche steht damit zwischen der exakten Suche (vollständig, mit Schranken) und den Metaheuristiken, die vollständige Lösungen verändern (siehe die Trajektorien-Metaheuristiken). In der Praxis ist eine Wegesuche meist ein Baustein der Tourenplanung, nicht deren Ziel.
Von der Wurzel (Greedy Best-First, schnell aber kurzsichtig) gehen drei Antworten aus: A* berücksichtigt die Pfadkosten und wird optimal, Beam Search hält mehrere Kandidaten parallel, Monte Carlo Tree Search verzichtet ganz auf die Heuristik. A* führt zu IDA*, das den Speicher spart, Beam Search zu Monobeam (mehr Breite schadet nie), Diverse Beam Search (mehrere verschiedene Routen) und, zusammen mit A*, zu Beam Stack Search als Konvergenzpunkt. Jedes Stück misst zuerst, dann behauptet es: mehrere Vorab-Hypothesen wurden von den eigenen Messungen widerlegt, nicht nur bestätigt.
In short: Covers heuristic tree search: greedy best-first search, A*, IDA*, beam search and Monte Carlo tree search. Interactive demos run these methods on a path-finding problem and show where each one reaches its measured limit.
Hintergrund zum Thema: Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
A* verständlich erklärt
Warum die Summe aus bisherigem Weg und geschätztem Restweg den kürzesten Weg findet und wie viel vom Tempo der reinen Zielsuche dabei bleibt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die acht Stücke im Überblick
Von der Wurzel (Greedy Best-First) führen drei Kanten aus: zu A*, zu Beam Search und, als gestrichelte Kontrastkante, zu Monte Carlo Tree Search, das keine Heuristik braucht. A* führt weiter zu IDA*, Beam Search zu Monobeam und zu Diverse Beam Search.
Beam Stack Search ist der Konvergenzpunkt (Doppelrahmen): eine Kante von Beam Search (mit Rücksprung statt ohne Zurück) UND eine von A* (Optimalität mit begrenztem Speicher).
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- Zusammenfluss mehrerer Stränge
Die gestrichelte Kante (Greedy Best-First → Monte Carlo Tree Search) ist ein Kontrast, kein Fix: MCTS ersetzt die Heuristik, statt sie zu verbessern. Der Doppelrahmen (Beam Stack Search) markiert die Konvergenzkante.
Verwandt in anderen Linien
- Kürzeste Wege — Uniform-Cost, die Vergleichsbasis ohne Heuristik in dieser Linie, ist Dijkstra: die Dijkstra-Demo der Kürzeste-Wege-Linie zeigt ihn auf wachsenden Stadtnetzen. Mit h ≡ 0 reproduziert A* die Expansionsreihenfolge von Uniform-Cost exakt; A* steht deshalb nur hier und wird in der Kürzeste-Wege-Linie verlinkt.
- Reinforcement Learning — Monte Carlo Tree Search plant bei jedem Zug neu durch simulierte Rollouts und trägt keine wiederverwendbare gelernte Werte- oder Politikfunktion zwischen Entscheidungen weiter. Es ist verwandt, aber nicht dasselbe wie das dortige Q-Learning, das genau eine solche Funktion über viele Episoden hinweg lernt.
- Adversarische Suche — MCTS ist eine von zwei Baumsuche-Familien für Zwei-Spieler-Gegnerspiele; die Selbstspiel-Demo der Adversarische-Suche-Linie kombiniert stattdessen klassisches Alpha-Beta mit einer per Selbstspiel gelernten Bewertungsfunktion (das AlphaZero-Prinzip, aber mit Baumsuche statt MCTS).
Greedy Best-First Search auf einem Netz mit Hindernissen
Verfolgen Sie, wie die Greedy-Suche in jedem Schritt den Knoten untersucht, der nach der Luftlinie zum Ziel am besten aussieht, und nie zurückgeht. Ein Vergleich mit Uniform-Cost zeigt live den Tausch: im Standardfall nur ein Fünftel der Expansionen, aber ein um 16,52 % zu langer Weg. Überraschend ist die Lücke auf offenem Feld am größten (22,1 %) und sinkt mit mehr Hindernissen.
Demo starten →A* auf demselben Netz
Sehen Sie, wie A* den nächsten Knoten nach bisherigem Weg plus geschätztem Restweg wählt und so die Optimalität zurückbringt, die der Greedy-Suche fehlte, solange der Restweg nie überschätzt wird. Ein Vergleich mit Greedy und Uniform-Cost zeigt live den Haken: A* behält im Standardfall nur 32 % des Effizienzvorsprungs der Greedy-Suche, weil die Luftlinie auf Vierer-Rastern den wahren Weg locker unterschätzt.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →IDA* auf demselben Netz
Verfolgen Sie, wie IDA* die große Merkliste offener Knoten von A* durch wiederholte, tiefenbegrenzte Tiefensuchen mit wachsender Schwelle ersetzt und nur den aktuellen Pfad speichert. Ein Größen- und Hindernis-Regler zeigt den Tausch: rund 3x weniger Speicher, aber rund 705x mehr Expansionen, und der Zeitpreis wächst mit der Rastergröße um Größenordnungen.
Demo starten →Beam Search auf demselben Netz
Sehen Sie, wie Beam Search in jeder Schicht nur die k besten Kandidaten weiterverfolgt und den Rest ohne Zurück verwirft. Ein Breitenregler zeigt live, wie die Lücke zum Optimum mit der Breite schrumpft, aber auch den Haken: Ein schmaler Strahl scheitert bei 15 % Hindernissen in 20 % der Läufe ganz, und bei manchen Instanzen ist ein breiterer Strahl sogar schlechter.
Demo starten →Monobeam auf demselben Netz
Verfolgen Sie, wie Monobeam die Strahlplätze nacheinander aus einem gemeinsamen Kandidatenpool füllt, damit ein breiterer Strahl nicht mehr schlechter werden kann. Ein Vergleich mit Beam Search zeigt live den Preis dieser Garantie: Bei gleicher Breite war Monobeam nie besser, und alle fünf Instanzen sind erst bei Breite 24 optimal (Beam Search: Breite 8).
Demo starten →Beam Stack Search auf demselben Netz
Sehen Sie, wie Beam-Stack Search Beam Search einen Rückweg gibt: Ein Stapel merkt sich beschnittene Kandidaten, zu denen das Verfahren später zurückspringt, bis das Optimum bewiesen ist. Ein Breitenregler zeigt live, was dieser Beweis kostet: Bei der schmalsten Breite braucht er im Median 87,5-mal so viele Expansionen wie A*, und der Speichervorteil verschwindet ab Breite 6.
Demo starten →Diverse Beam Search auf demselben Netz
Verfolgen Sie, wie Diverse Beam Search das Strahlbudget in Gruppen teilt und jede Gruppe bestraft, wenn sie Zustände früherer Gruppen wählt, sodass mehrere verschiedene Routen entstehen. Ein Vergleich mit Beam Search gleicher Gesamtbreite zeigt live: drei Routen mit Überlappung 0,37 statt zweier Beinahe-Duplikate (0,91), aber keine bessere beste Lösung, in keiner der Vergleichsinstanzen.
Demo starten →Monte Carlo Tree Search auf demselben Netz
Sehen Sie, wie Monte Carlo Tree Search die handgemachte Heuristik durch zufällige Läufe bis zum Ziel ersetzt und den Suchbaum dort ausbaut, wo die Läufe Gutes versprechen. Ein Umschalter für einen von der Heuristik geführten Zufallslauf zeigt den Haken: Reines MCTS findet auf dem Standardraster in keinem Lauf die optimale Route (Lücke im Median 17,1 %), mit geführtem Lauf sinkt sie auf 2,4 %: großenteils geliehenes Wissen.
Demo starten →Welche heuristische Suche passt zu meiner Aufgabe?
Der Entscheidungsbaum führt durch die acht Verfahren, von der Frage nach einer brauchbaren Heuristik bis zur Frage nach mehreren Routen. Alle Antworten stützen sich auf Messungen in den Demos.
Welches Verfahren für welche Anforderung?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Monte Carlo Tree Search braucht auf einem bekannten, deterministischen Netz Größenordnungen mehr Aufwand als Uniform-Cost oder A* (Größe 12: 121 Expansionen gegen rund 81 000 Knotenbesuche, verschiedene Einheiten); es gehört in Spiele und Simulatoren. Beam Stack Search schnitt auf diesem Raster deutlich besser ab als IDA* (Größe 8: 9,1x gegen 705x A*), IDA* braucht dafür keine Breite.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.