Uninformierte und informierte Suche

Ein Suchproblem beschreibt Wahlmöglichkeiten, bevor ein Algorithmus beginnt, Entscheidungen zu treffen. Seine Formulierung bestimmt sowohl, was eine Lösung bedeutet, als auch, wie viele Möglichkeiten der Algorithmus berücksichtigen muss.

Definiere das Problem

Es gibt sechs Bestandteile:

• Zustände beschreiben die möglichen Situationen.
• Der Anfangszustand ist der Ausgangspunkt der Suche.
• Aktionen sind die in einem Zustand verfügbaren Wahlmöglichkeiten.
• Das Übergangsmodell, $\text{ERGEBNIS}(s,a)$, gibt den Zustand nach Aktion $a$ an.
• Der Zieltest erkennt einen akzeptablen Zustand.
• Die Aktionskostenfunktion, $c(s,a,s^{\mathrm{\prime }})$, weist jedem Schritt Kosten zu.

Alle Aktionskosten sind hier positiv. Eine Lösung für ein Wegfindungsproblem ist eine Aktionsfolge, die zu einem Ziel führt. Addiere ihre Aktionskosten, um ihre Pfadkosten zu erhalten. Eine kostenoptimale Lösung minimiert diese Summe. Allein das Ziel zu nennen, sagt einem Agenten nicht, wie er es erreichen kann.

Formuliere das 8-Puzzle

Ein Brett enthält acht nummerierte Kacheln und ein leeres Feld. Erfasse alle neun Positionen als Zustand. Der Anfangszustand ist die vorgegebene Anordnung; das Ziel ist „1 2 3 / 4 5 6 / 7 8 leer“. Eine Aktion bewegt das leere Feld nach links, rechts, oben oder unten, sofern der Zug auf dem Brett bleibt. Der Übergang vertauscht das leere Feld mit der benachbarten Kachel, und jeder Zug kostet 1. In einer Ecke sind zwei Aktionen möglich; in der Mitte vier.

Eine Lösung ist eine Folge wie „Links, oben, rechts“, sofern diese Züge zulässig sind und zum Ziel führen. Da jeder Zug gleich viel kostet, bedeutet die Minimierung der Kosten, die Anzahl der Züge zu minimieren.

Wähle den Zustandsraum

Stelle dir Zustände als Ecken eines gerichteten Graphen und Aktionen als mit Kosten beschriftete Kanten vor. Eine Straße in beide Richtungen ergibt zwei gerichtete Kanten. Bei der Wegfindung kann ein Zustand der aktuelle Ort sein und die Kosten eines Schritts können der Straßenentfernung in Kilometern entsprechen.

Abstraktion lässt irrelevante Einzelheiten weg. Die Musik im Auto muss nicht Teil eines Routenzustands sein. Eine abstrakte Lösung muss sich weiterhin ausführen lassen. Wenn du eine Einzelheit entfernst, die bestimmt, welche Aktionen zulässig sind, veränderst du das Problem, statt nur seine Beschreibung zu vereinfachen.

Die Formulierung kann mehr Arbeit sparen als eine schnellere Warteschlange. Setzt man acht Damen auf beliebige freie Felder, ergeben sich $64\times 63\times \cdots \times 57\approx \mathrm{1,8}\times {10}^{14}$ mögliche geordnete Platzierungsfolgen. Setzt man jede nächste Dame in die am weitesten links liegende freie Spalte auf ein nicht angegriffenes Feld, bleiben 2.057 erreichbare Zustände. Dies sind unterschiedliche Konstruktionen derselben Zielbedingung.

Erzeuge Möglichkeiten nach Bedarf

Das 8-Puzzle hat von einem festen Start aus $9!\mathrm{/}2=181.440$ erreichbare Zustände. Das 15-Puzzle hat $16!\mathrm{/}2\approx \mathrm{1,05}\times {10}^{13}$. Eine vollständige Darstellung des 8-Damen-Problems mit einer Dame pro Spalte hat $8^8=\mathrm{16.777.216}$ Zustände.

Solche Räume werden meist implizit vorgegeben: Die Suche erhält einen Anfangszustand und Verfahren für Aktionen und Übergänge. Sie erzeugt den relevanten Teil während ihrer Ausführung. Halte bei einem Pfadproblem die Aktionsfolge fest. Bei einem Optimierungsproblem wie der Platzierung von Damen kann die endgültige Anordnung selbst die Antwort sein.

Der Zustandsraum beschreibt, was möglich ist. Der Suchbaum hält die Pfade fest, die der Algorithmus ausprobiert hat. Mehrere Knoten können denselben Zustand beschreiben, weil sie ihn über unterschiedliche Pfade erreicht haben.

Speichere einen Pfad in einem Knoten

Ein Knoten speichert einen Zustand, seinen Elternknoten, die Aktion von diesem Elternknoten aus und die Pfadkosten $g(n)$. Auch die Tiefe kann gespeichert werden. Die Wurzel hat keinen Elternknoten und Pfadkosten von 0. Beim Expandieren eines Knotens wird jede zulässige Aktion auf seinen Zustand angewandt und seine Kindknoten werden erzeugt.

Auf einer Karte mit Straßen in beide Richtungen enden die Pfade „S, A“ und „S, B, C, A“ im selben Zustand, ergeben aber unterschiedliche Knoten. Selbst eine endliche Karte kann einen unendlichen Suchbaum erzeugen: „S, A, S, A, …“ erzeugt immer längere Pfade.

Die Suchfront, auch Randmenge genannt, enthält erzeugte Knoten, die auf ihre Expansion warten. Die Menge der erreichten Zustände erfasst erzeugte Zustände und den jeweils besten dafür gefundenen Knoten. Sie umfasst sowohl Zustände, die noch in der Suchfront liegen, als auch bereits expandierte Zustände. Eine abgeschlossene Menge oder Menge der expandierten Zustände bezeichnet meist nur expandierte Zustände.

Führe das allgemeine Bestensuchverfahren durch

1. Lege die Wurzel in die Suchfront und die Tabelle der erreichten Zustände.
2. Ist die Suchfront leer, gib Misserfolg zurück.
3. Entnimm den Knoten mit dem kleinsten Bewertungswert $f(n)$.
4. Ist sein Zustand ein Ziel, gib diesen Knoten zurück.
5. Expandiere ihn. Füge jeden neuen Zustand hinzu; ersetze bei einem zuvor erreichten Zustand den gespeicherten Knoten nur, wenn der neue Pfad günstiger ist.
6. Wiederhole ab Schritt 2.

Ein günstigerer Pfad zu einem bereits expandierten Zustand kann erfordern, ihn wieder zu öffnen. Eine Rückkehr zu gleichen Kosten bringt keine Verbesserung. Bei einem Heap kann ein alter Eintrag physisch vorhanden bleiben; er muss beim Entnehmen als veraltet erkannt und übersprungen werden.

Die Regel für die Suchfront bestimmt die Strategie. Eine FIFO-Warteschlange wählt für die Breitensuche Knoten mit geringer Tiefe aus. Ein LIFO-Stapel wählt für die Tiefensuche Knoten mit großer Tiefe. Nach $g$, $h$ und $g+h$ geordnete Prioritätswarteschlangen ergeben uniforme Kostensuche, gierige Bestensuche und A*-Suche.

Verfolge die Knoten auf der Straßenkarte

Verwende diese Straßen in beide Richtungen, mit Entfernungen in Kilometern: S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 und D–G 2. Starte bei S und suche G. Löse Gleichstände alphabetisch auf.

Beim Expandieren von S entstehen A mit Kosten von 2, B mit Kosten von 3 und D mit Kosten von 9. Jeder hat S als Elternknoten. Die Suchfront enthält A, B und D; die Tabelle der erreichten Zustände enthält außerdem S. Später kann C über A zu Kosten von 6 oder über B zu Kosten von 4 erreicht werden. Das sind zwei Knoten für einen Zustand, und der günstigere sollte C repräsentieren.

Um eine Lösung wiederherzustellen, folge den Elternverweisen des zurückgegebenen Zielknotens rückwärts und kehre die Aktionen um. Würden die Kosten aktualisiert, ohne den Elternknoten zu aktualisieren, stimmte der verbleibende Pfad nicht mit seinen angegebenen Kosten überein.

Entscheide, was gespeichert wird

Die Graphensuche merkt sich erreichte Zustände, um wiederholte Arbeit zu vermeiden. Die Baumsuche hat keine globale Tabelle der erreichten Zustände; sie verwirft möglicherweise nur Zyklen auf dem aktuellen Pfad. Sie spart Speicher, kann aber denselben Zustand über viele Pfade erzeugen.

Das allgemeine Verfahren prüft Ziele beim Entnehmen. Die Breitensuche kann beim Erzeugen prüfen, weil die Erzeugung nach Tiefe geordnet erfolgt. Kostenbasierte Suche muss bis zum Entnehmen warten: Das zuerst erzeugte Ziel kann einen teureren Pfad haben als ein später gefundenes Ziel.

Ein Algorithmus kann zuverlässig und dennoch zu aufwendig für die Ausführung sein. Beurteile seine Garantien getrennt von seinem Ressourcenbedarf und prüfe dann, ob diese Garantien zum tatsächlich zu lösenden Problem passen.

Stelle vier verschiedene Fragen

Vollständigkeit bedeutet, eine Lösung zu finden, wann immer eine existiert. In einem endlichen erreichbaren Raum kann das Ausschöpfen aller Möglichkeiten auch den Misserfolg nachweisen. Ein unendlicher Raum ohne Lösung kann selbst von einem vollständigen Algorithmus ewig durchsucht werden.

Kostenoptimalität bedeutet, eine Lösung mit den geringsten Pfadkosten zurückzugeben. Sie sagt nichts darüber aus, wie schnell der Algorithmus läuft. Ein Verfahren kann zuverlässig eine Lösung finden und dabei eine teure Route zurückgeben.

Die Zeitkomplexität zählt erzeugte oder expandierte Knoten. Gib beim Vergleich von Messungen an, welche Anzahl verwendet wird. Die Speicherkomplexität misst die maximale Anzahl gleichzeitig gespeicherter Knoten, einschließlich der Suchfront und gespeicherter Suchinformationen.

Bestimme die Parameter

Für einen impliziten Suchraum verwende:

Bei einem bereits explizit im Speicher vorliegenden Graphen sind die Anzahlen der Ecken und Kanten meist nützlicher. Eine Durchlaufschranke in $\mathrm{\mid }V\mathrm{\mid }$ und $\mathrm{\mid }E\mathrm{\mid }$ beantwortet eine andere Frage als eine Schranke für das Erzeugen eines noch nicht bekannten Baums.

Erkenne, warum Tiefe aufwendig ist

Ein vollständiger Baum bis zur Tiefe $d$ enthält

Knoten für $b\mathrm{\ne }1$. Bei Verzweigungsfaktor 10 und Tiefe 5 sind das 111.111 Knoten einschließlich der Wurzel. Eine Erhöhung der Tiefe um eins fügt eine Schicht mit zehnmal so vielen Knoten wie in der vorherigen Schicht hinzu.

Bei einer Million Knoten pro Sekunde und 1 Kilobyte pro Knoten ändern sich die Größenordnungen schnell:

Dies sind dezimale Speichereinheiten: 1 GB sind ${10}^9$ Byte. Der Speicherbedarf kann eine Suche ausschließen, lange bevor ihre Laufzeit unangemessen erscheint.

Lies Garantien zusammen mit ihren Bedingungen

Die Breitensuche erreicht bei endlichem Verzweigungsfaktor schließlich jede endliche Tiefe. Die Tiefensuche kann ewig auf einem unendlichen Zweig bleiben und ein nahe gelegenes Ziel nie ausprobieren. Dieser Unterschied erklärt ihre Ergebnisse zur Vollständigkeit.

Die Breitensuche findet einen Pfad mit den wenigsten Aktionen. Kostet eine Route mit zwei Schritten 11 km und eine Route mit drei Schritten 9 km, ist die Route mit geringerer Tiefe nicht kostenoptimal. Gleiche Schrittkosten lassen Tiefe und Kosten übereinstimmen; unterschiedliche Kosten können sie auseinanderfallen lassen.

Eine O-Schranke für den schlechtesten Fall sagt nicht jeden Ablauf voraus. Zwei Verfahren mit derselben Schranke können sich in Konstanten, im Umgang mit Duplikaten und in der Anzahl nützlicher Zweige unterscheiden. Eine Heuristik kann einen typischen Ablauf stark verbessern, ohne den exponentiellen schlechtesten Fall zu beseitigen.

Die Breitensuche untersucht den Raum in Schichten. Als Nächstes expandiert sie den noch wartenden Knoten mit der geringsten Tiefe, sodass jeder Pfad mit einer Aktion betrachtet wird, bevor ein Pfad mit zwei Aktionen expandiert wird.

Halte die Warteschlange in Ordnung

Die Suchfront arbeitet nach dem FIFO-Prinzip: Entnimm vorne und füge Kindknoten hinten an. Erfasse Zustände, wenn sie erzeugt werden. Wurde der Zustand eines Kindknotens bereits erreicht, überspringe ihn; andernfalls könnten zwei verschiedene Elternknoten denselben Zustand in die Warteschlange aufnehmen.

Prüfe den Anfangszustand vor der Suche. Für spätere Knoten kann die Breitensuche einen frühen Zieltest beim Erzeugen anwenden. Das erste erzeugte Ziel hat minimale Tiefe, weil der Algorithmus Kindknoten Schicht für Schicht erzeugt. Die Reihenfolge innerhalb einer Schicht kann zwischen Lösungen gleicher Tiefe entscheiden, aber keine tiefere Lösung zuerst erscheinen lassen.

Vollziehe den Ablauf auf der Beispielkarte nach

Die Straßen in beide Richtungen sind S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 und D–G 2 km. Starte bei S, suche G und erzeuge Nachbarn alphabetisch. In der Tabelle steht der als Nächstes zu entnehmende Knoten links.

Wenn B expandiert wird, sind C und D bereits erreicht. Sie wechseln nicht auf neue Positionen in der Warteschlange. Wenn D den Knoten G erzeugt, lautet dessen Elternkette G–D–S. Kehre sie um, um S–D–G mit zwei Straßen und einer Gesamtentfernung von $9+2=11$ km zu erhalten.

C wurde bereits erzeugt, aber noch nicht expandiert. Seine Route zu G hätte drei Straßen. Die Breitensuche kann anhalten, ohne sie zu untersuchen, weil drei Straßen die Anzahl der Aktionen einer Lösung mit zwei Straßen nicht verbessern können.

Erkenne, was das Ergebnis minimiert

Die Breitensuche ist bei endlichem Verzweigungsfaktor vollständig, selbst wenn der Raum unendlich ist: Jede endliche Schicht wird vor der nächsten bearbeitet. Sie ist kostenoptimal, wenn alle Aktionen gleich viel kosten. Bei einem Schiebepuzzle mit Kosten von 1 pro Zug ist eine Lösung mit geringster Tiefe auch eine günstigste Lösung.

Auf dieser Straßenkarte kostet S–B–C–G $3+1+5=9$ km. Die Breitensuche gibt die 11 km lange Route zurück, weil die Entfernung nicht ihre Ordnungsregel ist. „Kürzester Pfad“ braucht daher eine Einheit: Die wenigsten Straßen und die wenigsten Kilometer sind unterschiedliche Ziele.

Berücksichtige den Speicherbedarf

Mit frühem Zieltest benötigt die Breitensuche $O(b^d)$ Zeit und Speicher. Sie kann nahezu jeden Knoten bis zur Zieltiefe erzeugen und die Suchfront sowie Informationen über erreichte Zustände speichern. Werden Ziele erst beim Entnehmen geprüft, kann das Expandieren anderer Knoten in Tiefe $d$ die Tiefe $d+1$ erzeugen. Daraus ergibt sich für diese Version die übliche Schranke $O(b^{d+1})$.

Bei Verzweigungsfaktor 10 und 1 Kilobyte pro Knoten benötigt die Speicherung eines Baums bis Tiefe 10 etwa 11 TB. Die Breitensuche ist für Probleme mit geringer Tiefe und gleichen Kosten nützlich, wenn genügend Speicher verfügbar ist, etwa für Netzwerkpfade mit den wenigsten Zwischenstationen oder Puzzles mit den wenigsten Zügen. Eine FIFO-Warteschlange nutzt die numerischen Kantenkosten nicht, selbst wenn sie am Graphen stehen.

Die uniforme Kostensuche ordnet Pfade nach den bereits angefallenen Kosten. Sie kann ein nahe gelegenes, aber teures Ziel übergehen, während sie längere Routen aus günstigen Schritten untersucht.

Entnimm den günstigsten Pfad

Setze $f(n)=g(n)$ und verwende eine Prioritätswarteschlange. Findet eine Expansion einen günstigeren Pfad zu einem erreichten Zustand, aktualisiere sowohl seine Kosten als auch seinen Elternknoten. Ein Pfad mit gleichen Kosten verbessert den Eintrag nicht. Die uniforme Kostensuche ist die Suchform des Dijkstra-Algorithmus und hält an, wenn sie ein Ziel entnimmt.

Der späte Zieltest ist entscheidend. Das Erzeugen eines Ziels beweist, dass eine Route existiert. Wird dieses Ziel als günstigster Knoten der Suchfront entnommen, beweist das bei positiven Aktionskosten, dass keine noch unvollständige günstigere Route es übertreffen kann.

Vollziehe den Ablauf auf der Beispielkarte nach

Verwende die Straßen in beide Richtungen S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 und D–G 2 km. Löse Kostengleichstände alphabetisch auf. Die folgenden Einträge der Suchfront zeigen Zustand und Pfadkosten.

Das Ersetzen von C ist entscheidend: $3+1=4$ ist besser als $2+4=6$. Der Elternknoten von G ist C, der von C ist B und der von B ist S. Die zurückgegebene Route S–B–C–G kostet 9 km. D wird nur wegen der alphabetischen Gleichstandsregel vor G entnommen.

Würde eine direkte Straße S–G von 12 km hinzugefügt, erzeugte S sofort ein Ziel. Ein früher Test gäbe 12 km zurück, bevor die 9 km lange Route entdeckt wird. Die Prioritätswarteschlange kann die Optimalität nicht schützen, wenn die Abbruchregel sie umgeht.

Erkläre die Garantie

Bei endlichem Verzweigungsfaktor und Aktionskosten von mindestens einem bestimmten $ϵ>0$ passen nur endlich viele Pfadschritte unter eine feste Kostenschranke. Die uniforme Kostensuche entnimmt daher schließlich ein Ziel, wann immer eines existiert. Positive Kosten stellen sicher, dass das Erweitern eines Pfads ihn nicht günstiger machen kann, was den Optimalitätsbeweis stützt.

Bei Kosten von null ist Vorsicht nötig. Baumsuche kann immer wieder einen Zyklus ohne Kosten durchlaufen. Graphensuche verwirft Rückkehrschritte zum selben Zustand bei gleichen Kosten, aber eine unendliche Kette verschiedener Zustände mit beschränkten Gesamtkosten kann ein Ziel dennoch ewig verzögern. Negative Schrittkosten entkräften das übliche Optimalitätsargument der uniformen Kostensuche.

Verstehe den Aufwand

Die übliche Schranke für Zeit und Speicher im schlechtesten Fall ist $O(b^{1+\lfloor C^{\ast }\mathrm{/}ϵ\rfloor })$. Auf dieser Karte gilt $C^{\ast }=9$ und $ϵ=1$, was $O(b^{10})$ ergibt. Dies ist eine grobe Schranke, nicht die tatsächliche Anzahl der auf der Karte mit sechs Zuständen expandierten Knoten.

Viele günstige Pfade in Sackgassen können die uniforme Kostensuche zu erheblicher Arbeit zwingen, bevor sie eine teure nützliche Aktion ausführt. Wenn alle Schrittkosten gleich sind, ergibt ihr später Zieltest die bekannte Schranke $O(b^{d+1})$. A* mit $h=0$ führt genau dieselben Prioritätsvergleiche wie die uniforme Kostensuche durch.

Die Tiefensuche folgt einem Zweig, bevor sie dessen Alternativen ausprobiert. Das kann den Speicherbedarf stark verringern, doch ein ungünstig gewählter Zweig kann alle anderen Möglichkeiten verzögern.

Folge einem tiefen Zweig

Die Tiefensuche verwendet einen Stapel nach dem LIFO-Prinzip. Verwirf in einer baumartigen Version Zustände, die bereits auf dem aktuellen Pfad liegen, um unmittelbare Zyklen zu vermeiden. Speichere den aktuellen Pfad und die noch nicht expandierten Geschwisterknoten entlang dieses Pfads. Um Nachfolger mit einem Stapel alphabetisch auszuprobieren, lege sie in umgekehrter alphabetischer Reihenfolge auf den Stapel.

Starte auf der Karte mit Straßen in beide Richtungen S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 und D–G 2 km bei S und suche G. Wenn Nachbarn alphabetisch ausprobiert und Ziele beim Entnehmen geprüft werden, ergibt sich S, A, C, B, D, G. Bei C ist B der erste Nachbar, der noch nicht auf dem Pfad liegt. Die zurückgegebene Route S–A–C–B–D–G kostet $2+4+1+6+2=15$ km.

Die Tiefensuche ist nicht kostenoptimal. In einem endlichen Raum mit Zyklusprüfung entlang des Pfads ist sie vollständig, kann aber einem unendlichen Zweig ewig folgen. Ihre Zeitkomplexität im schlechtesten Fall beträgt $O(b^m)$, und die gespeicherten Pfade und Geschwisterknoten benötigen $O(bm)$ Speicher. Backtracking, das jeweils einen Kindknoten erzeugt, verringert den Speicherbedarf auf $O(m)$. Bei Verzweigungsfaktor 10 und maximaler Tiefe 12 umfasst die Speicherung von Pfad und Geschwisterknoten etwa 120 Knoten, gegenüber ungefähr einer Billion bei der Breitensuche bis Tiefe 12. Eine globale Tabelle der erreichten Zustände benötigte zusätzlichen Speicher.

Beschränke die Tiefe

Die tiefenbeschränkte Suche beendet die Expansion bei Tiefe $\mathrm{\ell }$. Ein Ziel dort kann weiterhin erkannt werden. Sie unterscheidet drei Ergebnisse:

• Eine Lösung wurde gefunden.
• Abbruch wegen Tiefenbeschränkung: Die Tiefenschranke verhinderte eine vollständige Suche.
• Misserfolg: Die relevanten Möglichkeiten wurden ohne Ziel oder Abbruch wegen Tiefenbeschränkung ausgeschöpft.

Ein Abbruch wegen Tiefenbeschränkung beweist nicht, dass keine Lösung existiert. Liegt das Ziel mit der geringsten Tiefe in Tiefe 7, kann eine Beschränkung auf 5 es nicht erreichen. Zeit- und Speicherkomplexität im schlechtesten Fall betragen $O(b^{\mathrm{\ell }})$ und $O(b\mathrm{\ell })$.

Erhöhe die Beschränkung schrittweise

Die Suche mit iterativer Vertiefung führt tiefenbeschränkte Suchen mit den Beschränkungen 0, 1, 2 und so weiter durch. Sie findet eine Lösung mit geringster Tiefe, ohne eine Suchfront wie bei der Breitensuche zu speichern. Bei endlichem Verzweigungsfaktor ist sie vollständig; bei gleichen Aktionskosten ist sie kostenoptimal. Die Zeitkomplexität beträgt $O(b^d)$ und die Speicherkomplexität $O(bd)$.

Die meisten Knoten eines breiten Baums liegen in der letzten Schicht, sodass das Wiederholen der oberen Schichten oft wenig Aufwand verursacht. Zähle für $b=10$ und $d=5$ die erzeugten Knoten unterhalb der Wurzel:

Die Breitensuche erzeugt bis Tiefe 5 insgesamt 111.110 solcher Knoten. Die Suche mit iterativer Vertiefung erzeugt etwa 11 % mehr Knoten und benötigt dabei nur den Speicher einer Tiefensuche. Die wiederholten Besuche der Wurzel sind in diesen beiden Zählungen nicht enthalten.

Bei Verzweigungsfaktoren größer als 1 nähert sich der Mehraufwand im breiten Baum dem Faktor $b\mathrm{/}(b-1)$ an. Dieser Vorteil ist bei einer schmalen Kette geringer, wo wiederholte Anfangsabschnitte überwiegen. Die Suche mit iterativer Vertiefung ist eine nützliche uninformierte Wahl, wenn die Lösungstiefe unbekannt ist und eine vollständige Suchfront nicht in den Speicher passt. In Räumen mit vielen Wegen zum selben Zustand kann das Fehlen einer globalen Menge der erreichten Zustände zu erheblicher wiederholter Erzeugung führen.

Eine nützliche Strategie passt zum benötigten Ergebnis und zu den verfügbaren Ressourcen. Die uninformierte Suche nutzt die Problemdefinition ohne eine Schätzung der verbleibenden Entfernung. Sie kann trotzdem systematisch und sorgfältig geordnet vorgehen.

Vergleiche unter gleichen Bedingungen

Nimm einen endlichen Verzweigungsfaktor und die Bedingungen positiver Kosten für die uniforme Kostensuche an. Die Zeile zur Breitensuche verwendet einen frühen Zieltest; die Zeile zur Tiefensuche verwendet Zyklusprüfungen entlang des Pfads und keine globale Tabelle der erreichten Zustände.

Breitensuche und Suche mit iterativer Vertiefung minimieren die Kosten auch dann, wenn die Kosten allein eine monoton nicht fallende Funktion der Tiefe sind. Das Wort „allein“ ist wichtig: Für diese allgemeinere Bedingung müssen alle Pfade einer bestimmten Tiefe dieselben Kosten haben. Positive Kantenkosten allein machen die Breitensuche nicht kostenoptimal.

Suche von beiden Enden

Die bidirektionale Suche arbeitet vorwärts vom Start und rückwärts vom Ziel. Treffen sich die Suchen nahe der Mitte, erreicht jede ungefähr die Tiefe $d\mathrm{/}2$. Der Aufwand beträgt dann ungefähr $2b^{d\mathrm{/}2}$ statt $b^d$. Bei Verzweigungsfaktor 10 und Lösungstiefe 6 ergibt der Vergleich der jeweils größten Schicht etwa 2.000 gegenüber 1.000.000 Knoten.

Dafür braucht sie einen expliziten Zielzustand und eine Möglichkeit, Vorgänger zu erzeugen. Umkehrbare Straßen in beide Richtungen erleichtern die Rückwärtsexpansion. Eine Zieleigenschaft wie „Alle Damen sind sicher“ kann zu viele Zielzustände beschreiben, um einen geeigneten rückwärtigen Ausgangspunkt zu bieten.

Bei Breiten- oder kostenbasierten Suchen können geeignete Regeln für das Zusammentreffen und Beenden Vollständigkeit und Optimalität erhalten. Halte auf einer gewichteten Karte erst an, wenn keine günstigere Verbindung mehr möglich ist. Die erste Überschneidung der beiden Suchen muss nicht die günstigste Verbindung sein.

Wähle passend zum Problem

Für die wenigsten Züge in einem kleinen Schiebepuzzle ist bei gleichen Zugkosten die Breitensuche geeignet, wenn reichlich Speicher vorhanden ist. Für die kürzeste Reiseentfernung bei unterschiedlichen Straßenlängen und ohne Heuristik wähle die uniforme Kostensuche. Bei einem riesigen Puzzle mit gleichen Kosten und unbekannter Lösungstiefe vermeidet die Suche mit iterativer Vertiefung eine riesige Suchfront. In einem endlichen Raum mit vielen tief liegenden Zielen, bei dem jede Lösung genügt, kann die Tiefensuche praktisch sein. Sind Start und Ziel bekannt und die Aktionen umkehrbar, lohnt es sich, bidirektionale Suche zu erwägen.

Beim Speicherbedarf muss berücksichtigt werden, was die gewählte Version speichert. Eine Tiefensuche mit globaler Tabelle der erreichten Zustände hat nicht mehr dasselbe Speicherprofil wie baumartige Tiefensuche. Der Ablauf einer Breitensuche mit spätem Zieltest sollte nicht mit einer Komplexitätsschranke für den frühen Zieltest verglichen werden, als wären die Versionen identisch.

Selbst die beste uninformierte Wahl kann auf exponentielles Wachstum stoßen. Sind nützliche Kenntnisse über das Problemgebiet verfügbar, kann eine Heuristik unnötige Exploration verringern. Wenn nur eine endgültige Konfiguration zählt, kann lokale Suche auf die Speicherung eines Suchbaums verzichten.

Eine Heuristik weist einem Zustand eine Schätzung der geringsten verbleibenden Kosten bis zu einem Ziel zu. Schreibe sie als $h(n)$ für den Zustand im Knoten $n$. Sie hängt vom Zustand ab, nicht vom Pfad, auf dem er erreicht wurde, und ist an einem Ziel null.

Schätze den verbleibenden Aufwand

Die Luftlinienentfernung schätzt die verbleibende Straßenentfernung. In einem Gitter mit horizontalen und vertikalen Zügen der Länge eins addiert die Manhattan-Distanz die Koordinatendifferenzen:

Von Zelle (1, 1) zu (4, 5) ergibt das $3+4=7$ Züge. Die Luftlinienentfernung zwischen denselben Koordinaten beträgt $\sqrt{3^2+4^2}=5$. Die Schätzungen beantworten unterschiedliche Fragen zu relaxierten Bewegungsmöglichkeiten. Eine Heuristik muss zu den Einheiten der Kosten passen, die sie schätzt; Kilometer schätzen ohne ein geeignetes Umrechnungsmodell nicht unmittelbar die Reisezeit.

Informierte Suche nutzt eine Schätzung, um die Expansion zu steuern. Die Schätzung muss dem Algorithmus nicht sagen, welche Aktion er ausführen soll. Sie bewertet die Zustände, die durch die zulässigen Aktionen entstehen, und die Regel für die Suchfront entscheidet, welcher ausstehende Pfad als Nächstes untersucht wird.

Folge der kleinsten Schätzung

Die gierige Bestensuche setzt $f(n)=h(n)$. Ihre Prioritätswarteschlange entnimmt den Zustand, der dem Ziel am nächsten zu liegen scheint, und ignoriert die bereits angefallenen Kosten.

Verwende die Straßen in beide Richtungen S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 und D–G 2 km. Die heuristischen Schätzungen bis G betragen für S 8, A 7, B 5, C 4, D 2 und G 0 km.

1. Expandiere S. Die Suchfront enthält A mit Schätzung 7, B mit 5 und D mit 2.
2. Entnimm D, weil 2 am kleinsten ist. Beim Expandieren von D entsteht G mit Schätzung 0. Die Pfadkosten bis G betragen $9+2=11$ km.
3. Entnimm G und gib S–D–G zurück.

Nur S und D wurden expandiert. Die 9 km lange Route S–B–C–G war verfügbar, aber die Schätzung 5 für B sah schlechter aus als die 2 für D. Die gierige Suche bezog die bereits bis D zurückgelegten 9 km nie in ihren Vergleich ein.

Unterscheide Orientierung und Garantien

Selbst eine Heuristik, die nie überschätzt, macht die gierige Suche nicht kostenoptimal. Die Schätzungen im Beispiel sind zulässig, dennoch ist die zurückgegebene Route zu teuer. Die gierige Suche nutzt nur die verbleibende Schätzung und kann daher zu viel bezahlen, bevor sie einen vielversprechenden Zustand erreicht.

Graphensuche ist in einem endlichen Zustandsraum vollständig, wenn sie Duplikate richtig behandelt. Baumartige gierige Suche kann bei attraktiv erscheinenden wiederholten Zuständen in eine Schleife geraten, und ein unendlicher Raum kann immer wieder irreführende niedrige Schätzungen bieten. Zeit- und Speicherkomplexität im schlechtesten Fall betragen $O(b^m)$, obwohl eine nützliche Schätzung einen tatsächlichen Ablauf kurz halten kann.

Ein Ort kann in Luftlinie nahe an einem Ziel liegen, aber einen langen Umweg um einen Fluss erfordern. Kleine heuristische Werte garantieren keine guten Gesamtrouten. Auch die Berechnung der Heuristik benötigt Zeit: Weniger Expansionen helfen nur, wenn die Berechnung der Schätzungen die Einsparung nicht aufzehrt.

A* bewertet die gesamte vorgeschlagene Reise: die bereits angefallenen Kosten plus eine Schätzung der verbleibenden Kosten. Seine Priorität ist

Verwende eine Prioritätswarteschlange, ersetze teurere Pfade und prüfe ein Ziel beim Entnehmen. An einem Ziel gilt $h=0$, sodass seine Priorität seinen tatsächlichen Pfadkosten entspricht.

Vollziehe die Regel aus Kosten und Schätzung nach

Die Straßen in beide Richtungen sind S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 und D–G 2 km. Die heuristischen Schätzungen bis G sind S 8, A 7, B 5, C 4, D 2 und G 0. Löse Gleichstände alphabetisch auf.

A wird wegen der Gleichstandsregel vor G entnommen. A* expandiert vier Nichtzielknoten und nie D. Die uniforme Kostensuche auf derselben Karte expandiert auch D. Setzte man alle heuristischen Schätzungen auf null, entfiele diese Orientierung und man erhielte die uniforme Kostensuche.

Erkläre, warum eine optimistische Schätzung funktioniert

Eine zulässige Heuristik übersteigt nie die tatsächlichen Restkosten $h^{\ast }(n)$. Für A* mit Wiederöffnen garantiert Zulässigkeit Kostenoptimalität; baumartiges A* hat unter den Suchbedingungen mit positiven Kosten dieselbe Garantie.

Angenommen, ein schlechteres Ziel mit Kosten $C>C^{\ast }$ stünde kurz vor der Entnahme. Ein Knoten auf einem optimalen Pfad muss noch ausstehen. Für seinen Anfangsabschnitt auf dem optimalen Pfad gilt:

Die Warteschlange muss diesen Knoten vor dem schlechteren Ziel auswählen. Das widerspricht dem angenommenen Abbruchzeitpunkt. Das Wiederöffnen ist wichtig, weil ein später entdeckter günstigerer Anfangsabschnitt durch einen bereits expandierten Zustand weiterverfolgt werden können muss.

Eine konsistente Heuristik sorgt dafür, dass $f$ entlang von Pfaden monoton nicht fällt. Sie stellt sicher, dass bei der ersten Expansion eines Zustands ein günstigster Pfad dorthin verwendet wird. A* kann expandierte Zustände dann dauerhaft abschließen. Bei bloßer Zulässigkeit kann eine dauerhafte abgeschlossene Menge eine entscheidende Verbesserung verwerfen.

Verstehe die Beschneidung und ihre Grenzen

Bei Konsistenz expandiert A* jeden relevanten Knoten, für den $f<C^{\ast }$ gilt, möglicherweise Knoten mit dem gleichen Wert $C^{\ast }$ und vor der Rückgabe keine oberhalb dieses Werts. Die Priorität 11 von D übersteigt die Lösungskosten 9, sodass D nicht expandiert wird. In der Klasse vorwärts Pfade aufbauender Algorithmen, die dieselbe heuristische Information nutzen, ist A* abgesehen von Gleichständen optimal effizient. Dies ist ein Vergleich notwendiger Expansionen und keine Aussage, dass sein Programmcode immer am schnellsten läuft.

Überschätzung kann das Argument entkräften. Ändere die Schätzung für B auf 9, obwohl seine tatsächlichen Restkosten 6 betragen. B hat nun Priorität 12. A* folgt S, A, C und D und gibt S–A–C–G zu Kosten von 11 zurück, während B noch wartet.

A* hat weiterhin einen exponentiellen schlechtesten Fall und speichert erzeugte Suchinformationen.

Wenn die Suchfront nicht mehr in den Speicher passt oder eine Antwort zu langsam eintrifft, wähle, welche Ressource oder Garantie du eintauschen möchtest. Auf Geschwindigkeit ausgelegte Varianten ändern Prioritäten oder verwerfen Kandidaten. Auf Speicherersparnis ausgelegte Varianten erzeugen Pfade erneut, die sie nicht speichern konnten.

Gewichte die Schätzung stärker

Gewichtetes A* verwendet $f=g+Wh$ mit $W>1$. Es bevorzugt normalerweise stärker den Fortschritt in Richtung eines Ziels. Mit einer zulässigen Heuristik sowie den Aktualisierungen bei besseren Pfaden und dem Wiederöffnen des allgemeinen Verfahrens betragen die zurückgegebenen Kosten höchstens $W{C}^{\ast }$. Diese Schranke erlaubt eine schlechtere Lösung, verlangt sie aber nicht.

Verwende auf der Straßenkarte aus den Beispielen die Schätzungen S 8, A 7, B 5, C 4, D 2 und G 0 sowie das Gewicht 2. Von S aus sind die Prioritäten B 13, D 13 und A 16. Bei alphabetischer Auflösung des Gleichstands wird B gewählt. Sein Kindknoten C hat $4+2(4)=12$; C erzeugt dann G mit Priorität 9. Die Route mit Kosten von 9 wird nach drei Expansionen von Nichtzielknoten zurückgegeben. Die Garantie erlaubt bis zu 18 km, obwohl dieser Durchlauf das Optimum findet.

In derselben Formel ergibt Gewicht 0 die uniforme Kostensuche und Gewicht 1 A*. Mit wachsendem Gewicht dominiert die Schätzung die Vergleiche zunehmend und das Verhalten nähert sich der gierigen Suche an.

Die Strahlsuche behält nur die besten $k$ ausstehenden Knoten und verwirft den Rest. Die gespeicherte Suchfront ist beschränkt, aber ein verworfener Kandidat kann die einzige Lösung enthalten. Daher gibt das Verfahren weder eine Vollständigkeits- noch eine Optimalitätsgarantie.

Vertiefe anhand eines Schwellenwerts für geschätzte Kosten

IDA* führt eine Tiefensuche mit einem Schwellenwert für $f=g+h$ durch. Der erste Schwellenwert ist der Wert der Wurzel. Beschneide jeden Knoten oberhalb des Schwellenwerts und halte den kleinsten überschrittenen Wert fest. Dieser wird zum nächsten Schwellenwert; er ist nicht unbedingt der alte Schwellenwert plus 1. Verwende Zyklusprüfungen entlang des Pfads.

Für die Beispielkarte beträgt der erste Schwellenwert 8. A bei 9 und D bei 11 werden beschnitten; B und C bei 8 werden untersucht, aber G bei 9 wird beschnitten. Der nächste Schwellenwert ist 9. In dieser Iteration erzeugt der Pfad über A den Knoten C bei 10 und wird beschnitten. Der Pfad S–B–C–G bleibt innerhalb von 9 und führt zum Erfolg.

Bei Zulässigkeit erhält IDA* die Kostenoptimalität und benötigt nur Speicher für einen Pfad wie bei der Tiefensuche. Die wiederholten Durchläufe können aufwendig sein, wenn die Kosten viele verschiedene Schwellenwerte ergeben. Kleine ganzzahlige Kosten machen die Anzahl der Schwellenwerte oft besser beherrschbar.

Nutze beschränkten Speicher gezielter

Die rekursive Bestensuche (RBFS) speichert auf jeder Ebene die beste alternative Priorität. Sie folgt dem vielversprechendsten Zweig, bis diese Alternative besser wird, und geht dann zurück. Sie benötigt linearen Speicher, kann aber vergessene Zweige erneut erzeugen.

SMA* nutzt den verfügbaren Speicher, verwirft bei vollem Speicher das schlechteste Blatt der Suchfront und überträgt dessen Wert zurück an seinen Elternknoten. Dieser Eintrag erlaubt eine spätere erneute Erzeugung. Mit einer zulässigen Heuristik ist das Verfahren kostenoptimal, wenn ein optimaler Lösungspfad in den Speicher passt. Andernfalls kann es eine schlechtere Lösung zurückgeben oder scheitern, wenn kein Lösungspfad hineinpasst.

Wähle A* für eine optimale Antwort, wenn der Speicher ausreicht. Wähle IDA* oder eine geeignete speicherbeschränkte Variante, wenn Optimalität wichtig ist, aber die Suchfront nicht hineinpasst. Gewichtetes A* bietet eine numerische Qualitätsschranke; die Strahlsuche bietet starke Beschneidung ohne diese Schranke.

Eine Heuristik kann insgesamt optimistisch sein und sich dennoch zwischen benachbarten Zuständen zu stark ändern. Zulässigkeit und Konsistenz erfassen diese unterschiedlichen Prüfungen, und jede Eigenschaft stützt eine andere Version von A*.

Vergleiche Schätzungen mit tatsächlichen Kosten

Eine zulässige Heuristik erfüllt in jedem Zustand $0\le h(n)\le h^{\ast }(n)$. An einem Ziel sind die tatsächlichen Restkosten null, also muss auch seine Schätzung null sein. Zulässig bedeutet nicht genau: Überall null ist sicher, gibt aber keine Richtung vor.

Auf der Straßenkarte aus den Beispielen sind die Schätzungen und exakten günstigsten Restentfernungen bis G:

Jede Schätzung ist höchstens so groß wie die tatsächlichen Kosten. Bei einem großen Problem kann die Berechnung dieser exakten Kosten genauso schwer sein wie die ursprüngliche Suche. Ein Beweis anhand der Struktur des Problems ist dann nützlicher als eine vollständige Tabelle.

Prüfe jede Aktion

Konsistenz, auch Monotonie genannt, verlangt für jede Aktion $h(n)\le c(n,a,n^{\mathrm{\prime }})+h(n^{\mathrm{\prime }})$ sowie null an Zielen. Die aktuelle Schätzung darf die Kosten eines Schritts plus die Schätzung des Nachfolgers nicht übersteigen.

Auf der Straßenkarte ergibt A→C die Ungleichung $7\le 4+4$, C→B ergibt $4\le 1+5$ und D→G ergibt $2\le 2+0$. Straßen in beide Richtungen erfordern die Prüfung beider Richtungen. Alle 16 gerichteten Prüfungen sind für diese Schätzungen erfüllt.

Addiert man die Ungleichungen entlang eines Pfads zu einem Ziel, heben sich die dazwischenliegenden Schätzungen auf. Auf einem optimalen Pfad ergibt sich $h(n)\le h^{\ast }(n)$, also folgt aus Konsistenz die Zulässigkeit. Außerdem ergibt sich

Prioritäten können entlang eines Pfads nicht fallen. Die erste Expansion eines Zustands erfolgt daher auf einem günstigsten Pfad, selbst wenn seine erste Erzeugung teurer war.

Erkenne, warum bloße Zulässigkeit das Wiederöffnen erfordert

Betrachte Straßen in beide Richtungen S–A 1, A–C 1, S–B 1, B–C 2 und C–G 3. Die Schätzungen seien S 0, A 4, B 1, C 1 und G 0. Sie übersteigen die tatsächlichen Kosten S 5, A 4, B 5, C 3 und G 0 nicht und sind daher zulässig. Aber A→C verletzt die Konsistenz: $4>1+1$.

A* expandiert S, dann B mit Priorität 2 und dann C, das zu Kosten von 3 mit Priorität 4 erreicht wurde. Anschließend expandiert es A mit Priorität 5 und entdeckt einen günstigeren Pfad zu C mit Kosten von 2. Wird C dauerhaft verworfen, weil es abgeschlossen ist, bleibt ein Ziel mit Kosten von 6. Das Wiederöffnen von C gibt die Verbesserung weiter und ergibt das Optimum mit Kosten von 5.

Passe die Heuristik an das Bewegungsmodell an

Die Manhattan-Distanz ist für horizontale und vertikale Züge der Länge eins zulässig und konsistent. Kosten auch diagonale Züge 1, benötigt die Reise von (0, 0) nach (3, 3) nur drei Züge, während die Manhattan-Distanz 6 angibt. Für dieses Bewegungsmodell ergibt $\max (\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid },\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid })$ die Entfernung ohne Hindernisse. Die Garantie einer Heuristik gilt für ein bestimmtes Aktionsmodell.

Um eine sichere Schätzung zu entwickeln, löse eine einfachere Version des Problems. Ein relaxiertes Problem entfernt Aktionsbeschränkungen, sodass jede ursprüngliche Lösung weiterhin verfügbar ist. Seine geringsten Kosten können die geringsten ursprünglichen Kosten nicht übersteigen.

Entferne Beschränkungen gezielt

Exakte Kosten des relaxierten Problems ergeben eine zulässige Heuristik. Sie ist auch konsistent, wenn die ursprünglichen Aktionen mit ihren Kosten verfügbar bleiben: Ein ursprünglicher Schritt und danach eine optimale relaxierte Route ergeben eine mögliche relaxierte Route, sodass das relaxierte Optimum nicht mehr kosten kann.

Beim 8-Puzzle kann eine Kachel nur dann auf ein benachbartes Feld ziehen, wenn dieses Feld leer ist. Entfernt man die Bedingung des leeren Feldes, können Kacheln durch besetzte Felder hindurchziehen. Jede nummerierte Kachel benötigt dann mindestens ihre horizontale plus ihre vertikale Entfernung zu ihrem Ziel. Die Summe ergibt die Manhattan-Distanz $h_2$.

Entfernt man auch die Bedingung der Nachbarschaft, kann jede falsch platzierte Kachel in einem Zug direkt zu ihrem Ziel springen. Die entstehenden Kosten sind die Anzahl der falsch platzierten Kacheln $h_1$. Beide lassen sich leicht berechnen, ohne das ursprüngliche Puzzle zu durchsuchen.

Berechne beide Schätzungen

Betrachte für das Ziel „1 2 3 / 4 5 6 / 7 8 leer“ den Zustand „5 1 3 / 4 leer 2 / 7 8 6“. Nummeriere Zeilen und Spalten ab 1.

Die anderen nummerierten Kacheln liegen bereits richtig. Vier sind falsch platziert, also gilt $h_1=4$. Ihre Entfernungen ergeben zusammen $2+1+2+1=6$, also gilt $h_2=6$. Die optimale Lösung benötigt 12 Züge; die Relaxationen ignorieren Wechselwirkungen, die zusätzliche Arbeit verursachen.

Zähle das leere Feld nicht mit. Einen Zug vom Ziel entfernt sind eine nummerierte Kachel und das leere Feld beide verschoben. Würde man beide zählen, ergäbe sich 2 bei tatsächlichen Kosten von 1. Das leere Feld ermöglicht Züge; es ist keine zusätzliche Kachel, für die Kosten anfallen.

Speichere gelöste Teilprobleme

Eine Musterdatenbank erfasst exakte Kosten für ein ausgewähltes Teilproblem, etwa die korrekte Platzierung der Kacheln 1 bis 4, während andere Kacheln als austauschbar behandelt werden. Erstelle die Tabelle einmal durch Rückwärtssuche vom Ziel aus. Schlage während einer neuen Suche den Wert nach, statt das Teilproblem erneut zu lösen.

Das Teilproblem benötigt nicht mehr Arbeit als das vollständige Problem und liefert damit eine untere Schranke. Das Addieren zweier gewöhnlicher Musterkosten kann jedoch denselben realen Zug doppelt anrechnen. Die Addition ist bei disjunkten Mustern sicher, wenn jede Datenbank nur Züge ihrer eigenen Kacheln zählt. Disjunkte Kachelnamen allein begründen diese Regel der Kostenrechnung nicht.

Kombiniere sichere Schätzungen

Das Maximum zulässiger Schätzungen ist zulässig:

Jeder Kandidat bleibt unter den tatsächlichen Restkosten oder ist gleich groß, also gilt das auch für ihr Maximum. Es ist mindestens so aussagekräftig wie jede einzelne Schätzung. Eine einfache Summe bietet diesen Schutz nicht.

Eine aus gelösten Beispielen gelernte Heuristik kann die Restkosten im Durchschnitt gut vorhersagen. Durchschnittliche Genauigkeit begründet keine untere Schranke für jeden Zustand. Sie erhält die Garantie von A* für zulässige Heuristiken nur, wenn nachgewiesen wird, dass ihre Schätzungen nie überschätzen.

Eine genauere Schätzung kann die Exploration verringern, doch eine aufwendige Schätzung kann die Suche trotzdem verlangsamen. Vergleiche sowohl die gelieferten Informationen als auch den gesamten erforderlichen Rechenaufwand.

Weise Dominanz für jeden Zustand nach

Eine zulässige Heuristik $h_2$ dominiert die zulässige Heuristik $h_1$, wenn überall $h_2(n)\ge h_1(n)$ gilt. Ein günstiges Brett allein reicht nicht aus, um diese Beziehung zu beweisen.

Die Manhattan-Distanz dominiert beim 8-Puzzle die Anzahl falsch platzierter Kacheln. Jede falsch platzierte Kachel muss sich mindestens ein Feld bewegen, sodass ihr Beitrag zur Manhattan-Distanz mindestens die 1 beträgt, die die schwächere Heuristik zählt. Eine richtig platzierte Kachel trägt zu beiden null bei.

Mit konsistenten Schätzungen muss A* Pfade mit $g+h<C^{\ast }$ expandieren. Wird eine sichere Schätzung erhöht, fallen einige Pfade aus diesem zwingend zu expandierenden Bereich heraus. Eine dominierende konsistente Heuristik expandiert abgesehen von Unterschieden bei Gleichständen nicht mehr Knoten. Eine unzulässige Schätzung kann noch größer sein, verliert aber die Optimalitätsgarantie und kommt für diesen Dominanzvergleich nicht infrage.

Fasse den Suchaufwand zusammen

Der effektive Verzweigungsfaktor $b^{\ast }$ beschreibt die Breite eines entsprechenden gleichmäßigen Baums. Zähle $N$ erzeugte Knoten unterhalb der Wurzel und sei $d$ die Lösungstiefe. Löse

Die zusätzliche 1 berücksichtigt die Wurzel. Eine einheitliche Zählweise ist wichtig: Wenn eine Messung die Wurzel bereits enthält, addiere sie nicht ein zweites Mal.

Für 52 erzeugte Knoten unterhalb der Wurzel und die Lösungstiefe 5 beträgt die Gesamtzahl 53 und es gilt $b^{\ast }\approx \mathrm{1,92}$. Für 1.000 erzeugte Knoten und Tiefe 8 gilt $b^{\ast }\approx \mathrm{2,20}$. Bestimme diese Werte numerisch, indem du einen Versuchswert erhöhst oder verringerst, bis seine geometrische Summe mit der Gesamtzahl der Knoten übereinstimmt.

Ein Wert nahe 1 weist auf eine schmale Suche hin. Vergleiche Ergebnisse über repräsentative Instanzen hinweg mit derselben Zählregel und vergleichbaren Lösungstiefen. Der effektive Verzweigungsfaktor kann helfen, die Skalierung zu schätzen, aber eine ungewöhnlich einfache Instanz ist keine verlässliche Vorhersage für eine ganze Problemfamilie.

Miss die Zeit für die gesamte Berechnung

Angenommen, ein Knoten benötigt 10 Mikrosekunden, einschließlich 1 Mikrosekunde zur Berechnung der alten Heuristik. Ein Ersatz halbiert die Knotenzahl, benötigt aber 100 Mikrosekunden pro Berechnung. Die übrige Arbeit kostet weiterhin 9 Mikrosekunden, sodass die neuen Gesamtkosten pro Knoten 109 betragen. Das Verhältnis der Gesamtzeiten ist

Die Suche ist etwa 5,5-mal langsamer, obwohl sie weniger Knoten besucht. Benötigt die neue Berechnung nur 2 Mikrosekunden, steigt die Gesamtzeit pro Knoten auf 11 und das Zeitverhältnis beträgt $\mathrm{0,5}\times 11\mathrm{/}10=\mathrm{0,55}$. Das ist etwa 1,8-mal schneller.

Auch eine Musterdatenbank verursacht Erstellungskosten. Viele Suchen mit demselben Ziel können sich diese Investition teilen; eine kleine Suche allein macht sie möglicherweise nicht wett. Miss Vorverarbeitung, Nachschlagezeit, erzeugte Knoten und Speicher getrennt, damit weniger Expansionen nicht mit einer automatischen Beschleunigung verwechselt werden.

Lokale Suche verändert wiederholt einen vollständigen Lösungskandidaten. Sie eignet sich für Aufgaben, bei denen die endgültige Konfiguration zählt und die Folge der Schritte zu ihrer Ermittlung verworfen werden kann.

Stelle einen vollständigen Kandidaten dar

Setze beim 8-Damen-Problem eine Dame in jede Spalte. Stelle den Zustand durch die acht Zeilennummern dar und lies die Spalten von links nach rechts. Jeder Zustand enthält alle acht Damen, auch Zustände mit Konflikten. Bei einem Nachbarn wird eine Dame in eine andere Zeile ihrer eigenen Spalte bewegt.

Es gibt $8^8=\mathrm{16.777.216}$ Zustände und $8\times 7=56$ Nachbarn pro Zustand. Eine feste Anzahl aktueller Zustände ersetzt die große Suchfront und die Elternverweise der Pfadsuche. Der Speicherbedarf hängt weiterhin von der Größe eines Zustands ab; ein Tupel mit acht Einträgen zu speichern ist weniger aufwendig als ein riesiger Stundenplan.

Stundenplanung, Chipentwurf und die Wahl einer vollständigen Rundreise durch Städte folgen demselben allgemeinen Muster: Jeder Zustand ist ein vollständiger Vorschlag. Eine Rundreise ist selbst eine mögliche Anordnung, obwohl ihr Inhalt eine Reise beschreibt. Lokale Suche muss die Folge der Änderungen zur Verbesserung dieser Rundreise nicht bewahren.

Definiere, was besser bedeutet

Eine Zielfunktion gibt jedem Zustand einen zu maximierenden Wert. Gleichwertig kannst du zu minimierende Kosten definieren. Beim n-Damen-Problem zähle mit $h$ die Paare von Damen, die einander angreifen. Zähle jedes Paar einmal, einschließlich Angriffen entlang von Zeilen oder Diagonalen, selbst wenn eine andere Dame dazwischenliegt. Für eine Lösung gilt $h=0$.

Bei vier Spalten setzt das Tupel (1, 2, 3, 4) alle Damen auf eine Diagonale. Alle seine $\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$ Paare greifen einander an. Das Tupel (2, 1, 3, 4) hat zwei angreifende Paare, während (2, 4, 1, 3) keine hat. Hier sind niedrigere Werte besser; der Buchstabe $h$ bezeichnet Zielfunktionskosten, keine von A* verwendete Schätzung verbleibender Pfadkosten.

Interpretiere die Landschaft

Stelle dir die Qualität eines Zustands als Höhe vor. Für die Maximierung gilt:

• Ein globales Maximum hat den besten Wert im gesamten Raum.
• Ein lokales Maximum ist besser als seine Nachbarn, kann aber schlechter als ein weit entfernter Zustand sein.
• Ein Plateau ist ein zusammenhängender flacher Bereich. Es kann ein flaches lokales Maximum ohne aufwärtsführenden Ausgang oder eine Schulter sein, von der aus Seitwärtsschritte einen aufwärtsführenden Ausgang erreichen können.
• Ein Grat kann in eine Richtung ansteigen, der die verfügbaren einzelnen Züge nicht folgen können. Jede unmittelbare Wahl kann schlechter aussehen.

Bei der Kostenminimierung kehre die Höhe um: Die Suche sucht Minima und Täler. Ein lokales Minimum ist kein Beweis dafür, dass anderswo kein Zustand mit niedrigeren Kosten existiert. Die Nachbarschaft bestimmt, welche Zustände in einem Schritt verglichen werden können. Eine Änderung der erlaubten Bearbeitung kann daher verändern, wo die Suche stecken bleibt.

Prüfe, ob der Pfad ignoriert werden kann

Ein Agent zur Wegfindung muss zulässige Aktionen von seinem tatsächlichen Start aus zurückgeben. Ein gutes Ziel allein genügt nicht. Lokale Suche gibt im Allgemeinen nur den Kandidatenzustand zurück, ohne eine Elternkette durch alle früheren Änderungen.

Ein vollständiges lokales Suchverfahren fände ein Ziel, wann immer eines existiert; ein optimales fände das globale Optimum. Einfache lokale Verfahren bieten keine dieser allgemeinen Garantien. Ihr Vorteil ist, dass sie schnell gute Kandidaten erreichen können, wenn die Speicherung eines systematischen Suchbaums nicht praktikabel ist.

Bergsteigen führt die beste unmittelbar auffindbare Verbesserung aus. Bei einem zu maximierenden Wert wählt Bergsteigen mit steilstem Anstieg den Nachbarn mit dem höchsten Wert. Bei zu minimierenden Kosten wählt es den Nachbarn mit den niedrigsten Kosten. Es hält an, wenn keine strikte Verbesserung existiert.

Verfolge einen Durchlauf mit vier Damen

Ein Zustand gebe die Zeile der Dame in jeder Spalte an und $h$ zähle angreifende Paare. Beginne mit (1, 2, 3, 4), dessen Kosten 6 betragen.

1. Bewerte die Züge mit jeweils einer Dame. Ein bester Nachbar ist (2, 2, 3, 4) mit Kosten von 4.
2. Von dort ist ein bester Nachbar (2, 1, 3, 4) mit Kosten von 2.
3. Kein Nachbar, der durch den Zug einer Dame entsteht, hat Kosten unter 2. Das strikte Bergsteigen hält an.

Die Anordnung (2, 4, 1, 3) mit Kosten von null existiert, kann aber vom erreichten Zustand aus nicht durch einen unmittelbar verbessernden Zug erreicht werden. Dies ist eine Folge der lokalen Regel und kein Beleg dafür, dass das Programm Konflikte falsch gezählt hat.

Erlaube nützliche Seitwärtsbewegungen

Ein Seitwärtsschritt behält denselben Wert bei. Er kann eine Schulter zu einem verbessernden Ausgang überqueren, aber auch auf einem flachen lokalen Optimum umherwandern. Beschränke aufeinanderfolgende Seitwärtsschritte, um endlose Zyklen zu vermeiden.

In dem von Russell und Norvig beschriebenen Experiment zum 8-Damen-Problem ist Bergsteigen mit steilstem Anstieg von zufälligen Starts aus in etwa 14 % der Fälle erfolgreich und benötigt bei Erfolg etwa 4 Schritte und beim Steckenbleiben 3. Erlaubt man bis zu 100 aufeinanderfolgende Seitwärtsschritte, steigt der berichtete Erfolg auf etwa 94 %, mit etwa 21 Schritten pro Erfolg und 64 pro Misserfolg. Dies sind Ergebnisse dieses Experiments, keine allgemeinen Erfolgsraten für Bergsteigen.

Ändere die Auswahl eines Nachbarn

Stochastisches Bergsteigen wählt zufällig einen verbessernden Nachbarn aus und kann dabei größere Verbesserungen bevorzugen. Bergsteigen mit erster Verbesserung zieht Nachbarn einzeln und nimmt die erste Verbesserung. So vermeidet es, vor jedem Zug eine riesige Nachbarschaft auszuwerten. Beide lehnen weiterhin schlechtere Züge ab.

Bergsteigen mit zufälligem Neustart beginnt nach einem fehlgeschlagenen Durchlauf einen neuen Durchlauf von einem neu zufällig gezogenen Zustand aus. Bei unabhängigen Durchläufen mit Erfolgswahrscheinlichkeit $p$ beträgt die erwartete Anzahl der Durchläufe bis einschließlich zum ersten Erfolg $1\mathrm{/}p$. Für $p=\mathrm{0,14}$ sind das etwa 7 Durchläufe. Mit den berichteten Schrittzahlen beträgt die erwartete Gesamtzahl der Schritte

Auch die fehlgeschlagenen Durchläufe verursachen Arbeit. Bei positiver Erfolgswahrscheinlichkeit und unabhängigen Neustarts nähert sich die Wahrscheinlichkeit eines späteren Erfolgs mit wachsender Anzahl der Durchläufe der 1 an.

Lass mehrere Kandidaten Entdeckungen teilen

Die lokale Strahlsuche behält $k$ Zustände, erzeugt ihre Nachbarn gemeinsam und behält die besten $k$ aus dieser zusammengefassten Auswahl. Ein vielversprechender Elternknoten kann mehrere verbleibende Zustände beitragen, während ein anderer keinen beiträgt. Dieses Teilen unterscheidet das Verfahren von unabhängigen Neustarts.

Das Zusammenfassen kann auch dazu führen, dass sich alle Kandidaten in einer Region häufen. Die stochastische Strahlsuche zieht verbleibende Zustände mit einer Wahrscheinlichkeit, die mit der Qualität steigt, um mehr Vielfalt zu erhalten. Die Wahl zwischen Seitwärtsschritten, Neustarts und Vielfalt in der Population hängt davon ab, warum der Fortschritt ausbleibt: wegen einer nahe gelegenen Brücke aus gleichwertigen Zuständen, einer ungünstigen Startregion oder zu vieler Kandidaten, die denselben Bereich erkunden.

In manchen Landschaften muss vorübergehend eine Verschlechterung in Kauf genommen werden, bevor ein besserer Zustand erreichbar wird. Simulierte Abkühlung erlaubt solche Züge mit einer kontrollierten Wahrscheinlichkeit. Genetische Algorithmen erkunden den Raum dagegen durch die Auswahl und Kombination vollständiger Kandidaten.

Akzeptiere gelegentlich einen schlechteren Zug

Die simulierte Abkühlung zieht einen zufälligen Nachbarn. Akzeptiere einen verbessernden Zug. Schreibe für eine zu maximierende Zielfunktion ihre Änderung als $\mathrm{\Delta }E$. Gilt $\mathrm{\Delta }E<0$, akzeptiere den schlechteren Zug mit der Wahrscheinlichkeit

Bei der Kostenminimierung sei $\mathrm{\Delta }$ der Anstieg der Kosten. Für einen schlechteren Zug gilt dann $\mathrm{\Delta }>0$ und die Akzeptanzwahrscheinlichkeit ist $e^{-\mathrm{\Delta }\mathrm{/}T}$. Züge zu einem Zustand mit gleichem Wert haben nach beiden Formeln die Wahrscheinlichkeit 1. Temperatur und Änderungen der Zielfunktion müssen eine zueinander passende numerische Skala verwenden.

Ein Rückgang des Werts um 2 wird bei Temperatur 10 mit einer Wahrscheinlichkeit von etwa 0,819 akzeptiert, bei Temperatur 1 mit 0,135 und bei Temperatur 0,5 mit 0,018. Bei Temperatur 10 hat ein größerer Rückgang um 5 die Wahrscheinlichkeit von etwa 0,607. Die Temperatur steuert also die Toleranz, während bei gleicher Temperatur weiterhin die Größe der Verschlechterung zählt.

Senke die Temperatur

Ein Abkühlungsplan legt die Temperatur über die Zeit fest. Geometrische Abkühlung verwendet $T_{k+1}=\alpha T_k$ mit einem Faktor nahe 1, etwa 0,95. Bei hoher Temperatur werden viele schlechtere Züge akzeptiert und die Exploration ähnelt einem Zufallsweg. Nahe null werden schlechtere Züge selten und das Verhalten ähnelt dem Bergsteigen.

Zu schnelles Abkühlen kann die Suche festhalten, bevor sie einer ungünstigen Region entkommt. Sehr langsames Abkühlen erhöht den Rechenaufwand. Das asymptotische Ergebnis zum globalen Optimum erfordert ausreichend langsames Abkühlen und die übliche Möglichkeit, Zustände über die Nachbarschaft zu erreichen; ein gewöhnlicher endlicher geometrischer Durchlauf garantiert keinen globalen Erfolg. Das Verfahren wird seit den 1980er-Jahren für Chipentwurf und Ablaufplanung eingesetzt. Sein Name stammt vom Erhitzen und langsamen Abkühlen von Metall, sodass es eine energieärmere Struktur annimmt.

Erzeuge eine neue Population

Ein genetischer Algorithmus stellt Kandidaten als Zeichenketten dar. Jede Generation bewertet ihre Fitness, wählt Eltern unter Bevorzugung höherer Fitness aus, erzeugt Nachkommen durch Rekombination und wendet gelegentlich Mutationen an.

Beim 8-Damen-Problem beschreiben acht Zeilenziffern je eine Dame pro Spalte. Die Fitness kann die Anzahl der sich nicht angreifenden Paare zählen, wobei 28 das Maximum ist. Schneide die Elternzeichenketten „64751517“ und „64278273“ nach der vierten Ziffer. Die Kombination der jeweils anderen Hälften ergibt „64758273“ und „64271517“.

Die Eltern haben die Fitnesswerte 23 und 24; die Nachkommen haben die Fitnesswerte 27 und 21. Ein Nachkomme verbessert sich gegenüber beiden Eltern, während der andere schlechter ist. Rekombination bietet neue Kombinationen, garantiert aber keine Verbesserung. Sie ist nützlich, wenn gute Bausteine bei ihrer Kombination tendenziell ihren Wert behalten. Mutation verändert gelegentlich eine Position und hilft, über diese Kombinationen hinaus Vielfalt einzubringen.

Selektion, Rekombination und Mutation haben unterschiedliche Aufgaben: Selektion bevorzugt nützliche Kandidaten, Rekombination kombiniert sie neu und Mutation verändert einzelne Positionen. Wie die stochastische Strahlsuche verwaltet das Verfahren eine Population, aber neue Kandidaten können Material von zwei Eltern beziehen. Weder ein Elternteil mit hoher Fitness noch eine niedrige Endtemperatur allein beweist, dass das globale Optimum gefunden wurde.