2.2 Suchverfahren

Worum geht’s#

Sehr viele Probleme der KI lassen sich auf dieselbe abstrakte Form bringen: Man steht in einem Zustand, kann ihn mit Aktionen verändern und sucht eine Folge von Aktionen, die in einen Zielzustand führt — möglichst billig. Der Foliensatz fragt genau das: Lassen sich die Suchalgorithmen auch für anderes als die Wegplanung einsetzen? Die Antwort lautet ja, sofern man einen diskreten Zustandsraum hat, eine feste Anzahl ausführbarer Aktionen $a_1,\dots,a_k$, und jede Aktion einen Zustandswechsel bewirkt. Als Beispiele nennen die Folien das n-Damen-Problem, das 8er-Puzzle und Krypto-Rätsel — und historisch den General Problem Solver von H. Simon und A. Newell, der zu zwei Zuständen $A$ und $B$ eine Folge von Operatoren sucht, die $A$ in $B$ überführt, und dabei bevorzugt solche Operatoren wählt, die die Differenz zwischen $A$ und $B$ verkleinern.

Was mich an diesem Kapitel überzeugt, ist die saubere Trennung von Modell und Verfahren. Hat man ein Problem einmal als Zustandsraum formalisiert, kann man beliebige Suchalgorithmen darauf ansetzen, ohne das Modell anzufassen. Die ganze Kunst verlagert sich auf zwei Fragen: In welcher Reihenfolge expandiere ich Knoten — und wie viel Wissen über das Ziel lasse ich in diese Reihenfolge einfließen. Genau an dieser zweiten Frage scheidet sich blinde von informierter Suche, und sie entscheidet darüber, ob ein Verfahren Millionen oder nur Tausende Zustände anfasst, bevor es dieselbe optimale Lösung findet.

Kernkonzepte#

Suchraum gegen Suchbaum#

Der erste Begriff, der sauber sitzen muss, ist der Unterschied zwischen dem Suchraum (auch Zustandsraum) und dem Suchbaum, den ein Algorithmus über ihm aufspannt. Sie werden gern verwechselt, weil ein Bild oft beide zugleich zeigt.

Konkret: Im 8-Puzzle gibt es genau $9!/2 = 181\,440$ erreichbare Zustände — das ist der Suchraum, und er ändert sich nie. Lässt eine naive Tiefensuche jedoch zu, dass sie eben getane Züge sofort wieder rückgängig macht, erzeugt sie einen unendlich tiefen Suchbaum über diesem endlichen Graphen. Der praktische Trick, der Suchbaum klein gegen den Suchraum hält, ist deshalb das Führen einer Menge bereits gesehener Zustände (graph search statt tree search) — die Folien nennen für das 8-Puzzle die Reduktion „mit Vermeidung von repeated states” von $3^{20}$ auf $9! = 362\,880$ Zustände.

Backtracking am n-Damen-Problem#

Das durchgängige Beispiel der Folien für blinde Suche ist nicht eine abstrakte Algorithmenfamilie, sondern das n-Damen-Problem: Platziere $n$ Damen auf ein $n\times n$-Brett, ohne dass eine die andere bedroht. Der Clou liegt schon in der Repräsentation — und genau dort, sagen die Folien, „steckt die KI”: Statt aller $n^2$-aus-Brettkonstellationen kodiert man eine Lösung als Vektor $v=[x_1,\dots,x_n]$, wobei $x_i$ die Spalte der Dame in Zeile $i$ ist ($x_i=0$ = noch nicht platziert). Verschiedene Zeilen und die Forderung $x_i\neq x_k$ schließen Zeilen- und Spaltenbedrohungen schon konstruktiv aus, so dass nur noch $n!$ statt aller Konstellationen bleiben (für $n=4$: $4!=24$ Blätter).

Das einzige problemspezifische Stück ist der Zulässigkeitstest. Da Zeilen und Spalten schon ausgeschlossen sind, prüfen die Folien nur noch Diagonalen: Zwei Damen $x_i$ und $x_j$ stehen genau dann auf einer Diagonalen, wenn $|x_i - x_j| = |i - j|$ gilt. Im Worst Case läuft Backtracking den ganzen exponentiellen Suchbaum ab; im Mittel verwirft es ganze Teilbäume früh und sieht nur einen Bruchteil der Knoten.

Blinde Suche#

Blinde (uninformierte) Verfahren kennen nur die Problemstruktur, nicht aber die „Richtung” zum Ziel. Sie unterscheiden sich allein durch die Reihenfolge, in der sie die Randmenge (engl. frontier) abarbeiten:

• Breitensuche (BFS) expandiert ebenenweise (FIFO-Rand). Sie ist vollständig und bei Einheitskosten optimal, kostet aber Speicher $\mathcal{O}(b^d)$ — die gesamte Ebene muss gehalten werden.
• Tiefensuche (DFS) geht zuerst in die Tiefe (LIFO-Rand). Sie braucht nur $\mathcal{O}(b\,m)$ Speicher, ist aber weder vollständig (unendliche Pfade) noch optimal.
• Iterative Tiefensuche (IDS) ruft DFS mit wachsender Tiefenschranke $0,1,2,\dots$ wiederholt auf. Sie verbindet den geringen Speicher von DFS mit der Vollständigkeit/Optimalität von BFS; die wiederholten Läufe kosten asymptotisch kaum etwas, da die unterste Ebene dominiert.
• Uniform-Cost-Suche (UCS) expandiert den Randknoten mit den kleinsten bisherigen Pfadkosten $g(n)$. Sie ist auch bei ungleichen Kantenkosten optimal — sie ist Dijkstras Algorithmus, von einer Quelle aus formuliert.
• Bidirektionale Suche lässt zwei Fronten gleichzeitig vom Start und vom Ziel laufen, bis sie sich treffen. Statt $b^d$ expandiert sie nur etwa $2\,b^{d/2}$ Knoten — eine Wurzelersparnis —, verlangt aber umkehrbare Operatoren und einen effizienten Schnitt-Test der beiden Ränder.

Informierte Suche#

Informierte Verfahren nutzen eine Heuristik $h(n)$, die die Restkosten von $n$ zum Ziel schätzt. Damit lenken sie die Suche gezielt in vielversprechende Regionen.

• Gierige Bestensuche expandiert stets den Knoten mit kleinstem $h(n)$. Das ist schnell, aber kurzsichtig: Sie ignoriert die schon zurückgelegten Kosten und ist daher weder optimal noch vollständig — sie kann in eine Sackgasse rennen, die dem Ziel nur scheinbar nahe ist.
• A* kombiniert beides zur Bewertungsfunktion

also bisherige Kosten plus geschätzte Restkosten. $f(n)$ schätzt damit die Kosten des besten Pfades durch $n$. A* expandiert immer den Knoten mit kleinstem $f$ — gierige Bestensuche ist der Sonderfall $g \equiv 0$, UCS der Sonderfall $h \equiv 0$.

Unter den zulässigen Heuristiken zählt die Dominanz: Gilt $h_2(n) \ge h_1(n)$ für alle $n$ (beide zulässig), so expandiert A* mit $h_2$ nie mehr Knoten als mit $h_1$. „Höher schätzen, ohne zu überschätzen” ist also immer besser — der ideale Grenzfall $h = h^*$ liefe ohne Umweg direkt zum Ziel. Genau diese Theorie macht der nächste Abschnitt am 8-Puzzle messbar.

Praxis#

Übungsblatt 4#

a) Der Suchraum ist der durch das Problem festgelegte Graph aller Zustände und Übergänge — er ist objektiv und algorithmusunabhängig. Der Suchbaum ist die vom jeweiligen Verfahren erzeugte Aufzählung von Pfaden in diesem Graphen; ein Zustand kann darin (über verschiedene Wege) mehrfach auftauchen. Kurz: Der Suchraum ist was es zu durchsuchen gibt, der Suchbaum wie ein Algorithmus es tatsächlich abläuft.

b) Blinde (uninformierte) Suche kennt nur Start, Operatoren und Zieltest und entscheidet die Expansionsreihenfolge allein aus der Baumstruktur bzw. den bisherigen Pfadkosten (BFS, DFS, IDS, UCS, bidirektional). Heuristische (informierte) Suche nutzt zusätzlich eine Schätzfunktion $h(n)$ der Restkosten, um bevorzugt in Richtung Ziel zu expandieren (Gierige Bestensuche, A*). Der Gewinn ist drastisch weniger Arbeit; der Preis ist, dass man eine gute, im Idealfall zulässige Heuristik finden muss.

Repräsentation. Ein Zustand ist die Position $s=(x,y)$ des Suchenden im Gitter. Startzustand $s_0=(2,3)$, Zielzustand $s_g=(7,6)$. Eine (Teil-)Lösung ist die Knotenfolge $\langle s_0, s_1, \dots, s_k\rangle$ des bisher gefundenen Pfades; gespeichert wird sie über Vorgängerzeiger.

Operatoren. Die acht Richtungen $\Delta \in \{-1,0,+1\}^2 \setminus \{(0,0)\}$ (4 orthogonal, 4 diagonal). Ein Zug $s \to s+\Delta$ ist erlaubt, wenn das Zielfeld im Gitter liegt und nicht tabu ist.

Zieltest. $\text{Ziel}(s) \equiv (s = (7,6))$. Da ein optimaler Pfad verlangt ist, wird er nicht beim ersten Erreichen, sondern erst beim Expandieren mit minimalem $f$ als endgültig akzeptiert (so garantiert A* die Optimalität).

Pfadkosten. Schrittkosten $c$ pro Zug: orthogonal $1$, diagonal $\sqrt{2}$ (die euklidische Schrittweite). Die Pfadkosten sind die Summe der Schrittkosten, $g(s_k)=\sum_{i=1}^{k} c(s_{i-1}, s_i)$.

$f=g+h$. Als Heuristik passt bei Diagonalkosten $\sqrt 2$ die Diagonal-/Octile-Distanz zum Ziel (bei Einheitskosten für Diagonalen wäre es die Chebyshev-Distanz), denn sie überschätzt die echten Restkosten in einem 8-Nachbarschafts-Gitter nicht und ist damit zulässig. A* expandiert dann stets den Randknoten mit kleinstem $f(s)=g(s)+h(s)$: $g$ ist das gesicherte Wissen über den Weg hierher, $h$ die optimistische Vorschau auf den Rest. Das Übungsblatt notiert allgemeiner $f=\alpha\,g+\beta\,h$ — mit $\alpha=\beta=1$ ist es klassisches A*; $\beta=0$ ergibt UCS, $\alpha=0$ gierige Bestensuche, ein großes $\beta$ ergibt schnelleres, aber nicht mehr optimales gewichtetes A*.

Pseudocode (b–e). Drei der vier Strategien — Uniform-Cost (c), gierige Bestensuche (d) und A* (e) — sind dasselbe Verfahren, eine Best-First-Suche mit Prioritätswarteschlange; sie unterscheiden sich allein im Sortierschlüssel des Randes. Das ist genau die Trennung von Modell und Verfahren aus den Kernkonzepten:

BEST-FIRST(Start, Ziel, key):           # key = c) g  | d) h  | e) g+h
  rand ← Prioritätsschlange, sortiert nach key; rand.push(Start)
  g[Start] ← 0;  vorg[Start] ← null
  while rand nicht leer:
    n ← rand.pop()                        # kleinster key-Wert
    if n = Ziel: return Pfad(vorg, Ziel)  # bei optimaler Suche: erst beim Pop
    markiere n als besucht (Reihenfolge protokollieren)
    for (m, schritt) in Nachbarn(n):      # 8 Richtungen, m nicht tabu/außerhalb
      g_neu ← g[n] + schritt              # orthogonal 1, diagonal √2
      if g_neu < g.get(m, ∞):
        g[m] ← g_neu;  vorg[m] ← n;  rand.push(m mit key(m))

Setzt man key = g, ist es Uniform-Cost; key = h (Octile-Distanz) macht daraus die gierige Bestensuche, die $g$ ignoriert; key = g + h ist A*. Die bidirektionale Breitensuche (b) fällt aus dem Schema, weil sie zwei Fronten führt und Einheits-Schritte zählt:

BIDIR-BFS(A, B):
  vorne ← FIFO[A];  hinten ← FIFO[B];  vorgV[A]=null; vorgH[B]=null
  while beide Fronten nicht leer:
    expandiere eine ganze Ebene von vorne (Nachbarn in vorgV eintragen)
    if vorgV ∩ vorgH ≠ ∅: return Naht(vorgV, vorgH)   # Treffpunkt gefunden
    expandiere eine ganze Ebene von hinten (Nachbarn in vorgH eintragen)
    if vorgV ∩ vorgH ≠ ∅: return Naht(vorgV, vorgH)

Ich habe alle vier auf dem aus dem Blatt rekonstruierten Labyrinth laufen lassen (die Wandzellen habe ich pixelgenau aus dem Aufgabenbild ausgelesen) und für jede Strategie den Lösungspfad sowie die Reihenfolge der besuchten Felder markiert:

=== Blatt 4, Aufgabe 2 — Gitter-Labyrinth (A=(2,3), B=(7,6)) ===
  Strategie                         Pfadlen       Kosten    besucht
  ----------------------------------------------------------------
  b) bidirektionale Breitensuche         13        12.00         78
  c) Uniform-Cost-Suche                  14        15.07         98
  d) gierige Bestensuche                 14        16.73         27
  e) A* (f = g + h)                      14        15.07         78

Zwei Befunde sind lehrreich. Erstens liefern UCS und A* exakt denselben kostenoptimalen Pfad (Kosten $15{,}07$), A* besucht dafür aber weniger Felder ($78$ statt $98$) — die Heuristik spart Arbeit, nicht Qualität. Die gierige Suche ist mit nur $27$ besuchten Feldern am billigsten, zahlt das aber mit einem teureren Weg ($16{,}73$): Sie ist eben nicht optimal. Zweitens findet die bidirektionale BFS einen Pfad mit nur $12$ Zügen (Pfadlänge 13) — weniger Züge als die 13 Züge der kostenoptimalen Lösung. Das ist kein Widerspruch, sondern der Unterschied der Gütemaße: BFS zählt jeden Zug als $1$ (auch diagonale) und minimiert die Zuganzahl, während UCS/A* die geometrischen Kosten mit Diagonalgewicht $\sqrt2$ minimieren. Wer Diagonalen „gratis” bewegen darf, nimmt lieber mehr Diagonalschritte.

f) Bewegliches Ziel. Verändert $B$ während der Suche seine Position, ist der einmal berechnete Pfad veraltet. Drei Stufen der Reaktion: (i) Neuplanung von Grund auf — bei jeder Zielbewegung A* neu starten; korrekt, aber teuer. (ii) Inkrementelle Suche — Algorithmen wie D* Lite oder LPA* speichern die Suchbaum-Information und reparieren nur die von der Änderung betroffenen Knoten, statt alles zu verwerfen; das ist um Größenordnungen billiger, wenn sich das Ziel nur lokal bewegt. (iii) Verfolgungssuche wie Moving-Target D*, eigens für ein flüchtendes Ziel. Praktisch heißt das: $h$ bleibt eine zulässige Schätzung zum aktuellen $B$; nach jedem Zielsprung werden die $f$-Werte der offenen Knoten mit dem neuen $B$ aktualisiert und betroffene Teilbäume neu bewertet.

g) Dynamische Hindernisse. Dürfen während der Suche Wände entstehen oder verschwinden, ist es derselbe Mechanismus wie in f), nur auf der Kantenseite: Eine neue Wand macht Kanten ungültig (Kosten $\to\infty$), eine entfernte Wand gibt neue Kanten frei. Genau dafür wurde D* (Dynamic A*) entworfen — der Standard in der mobilen Robotik (Mars-Rover): Es plant rückwärts vom Ziel, und wenn der Roboter eine Karten­abweichung entdeckt, propagiert es nur die Kosten­änderungen lokal, statt komplett neu zu planen. Der Brückenschlag zu 2.1 ist offensichtlich: Eine spontan abgestellte Kiste ist exakt das „nicht kartierte Hindernis”, das dort den Wechsel auf einen reaktiven Bug-Reflex auslöste — hier bleibt man im globalen Planer, repariert ihn aber inkrementell.

i) Skizze zu $f(n)=g(n)+h(n)$. Die Formel teilt die geschätzten Gesamtkosten eines Pfades durch $n$ in zwei Hälften: das gesicherte Wissen $g(n)$ über den bereits zurückgelegten Weg vom Start bis $n$ und die optimistische Vorschau $h(n)$ auf den Rest bis zum Ziel.

Modellierung (b). Zustand = Belegung der Felder (Tupel der Kacheln, $0$ für das Leerfeld); Operatoren = Schieben einer angrenzenden Kachel ins Leerfeld; Schrittkosten $=1$; Zieltest = geordnete Stellung. Darauf läuft A* mit $f=g+h$.

Vier Heuristiken (c).

• $h_1$ — fehlplatzierte Steine (Hamming): Anzahl der Kacheln, die nicht auf ihrem Zielfeld stehen (Leerfeld ausgenommen). Genau dieses $h_1$ steht im Foliensatz, mit dem Beispielwert $h_1=7$ für eine Stellung, in der nur Kachel 7 schon richtig liegt.
• $h_2$ — Manhattan-Distanz: Summe der Gitterabstände $\sum_i (|{\Delta r_i}|+|{\Delta c_i}|)$ jeder Kachel zu ihrem Zielfeld. Die Folien nennen sie „Summe der Manhattan-Entfernungen zur richtigen Position” ($h_2=20$ im selben Beispiel).
• $h_3$ — Tauschkonfigurationen (Folien: „$2\times$ Anzahl direkter Spielsteintausche”): Mindestzahl direkter Vertauschungen, wenn man (relaxiert) zwei Kacheln direkt tauschen dürfte — zulässig, „da die Anzahl der nötigen direkten Vertauschungen nie größer wird als die tatsächliche Schrittzahl”.
• $h_4$ — Manhattan + Linear Conflicts (Lehrbuch-Verschärfung, nicht in den Folien): Manhattan plus $2$ für jedes Paar Kacheln, die in ihrer Zielzeile/-spalte stehen, sich aber gegenseitig überholen müssen.

Anforderungen (e). Zulässigkeit: $h(n)\le h^*(n)$ — die Heuristik überschätzt die wahren Restkosten nie. Zweck: Sie garantiert die Optimalität von A*. Konsistenz (Monotonie): $h(n)\le c(n,n')+h(n')$ — die Schätzung fällt über jeden Schritt höchstens um die Schrittkosten. Zweck: Die $f$-Werte wachsen monoton, ein einmal expandierter Knoten ist optimal, und A* braucht keine bereits geschlossenen Knoten erneut zu öffnen. Konsistenz impliziert Zulässigkeit, aber nicht umgekehrt. Wünschenswert ist außerdem Informiertheit (möglichst hohe, dominante Werte) bei billiger Berechenbarkeit.

Bewertung (f). Alle vier sind zulässig (sie entstehen aus Relaxationen des Problems); $h_1$, $h_2$ und $h_4$ sind zudem konsistent. Die Folien prüfen die Zulässigkeit explizit über $h(n)\le g(z)-g(n)$, also $h(n)\le h^*(n)$: $h_1$ ist erlaubt, weil jede falsch stehende Kachel mindestens einmal bewegt werden muss; $h_2$, weil jede Verringerung des Abstands einer Kachel mindestens eine Verschiebung kostet. Es gilt die Dominanzkette $h_1 \le h_2 \le h_4$: $h_2$ zählt für jede fehlplatzierte Kachel mindestens den einen Zug, den $h_1$ als $1$ bucht, also nie weniger; $h_4$ addiert nur nichtnegative Konfliktkosten. Damit ist $h_4$ am schärfsten und expandiert am wenigsten — solange seine teurere Berechnung sich lohnt. $h_1$ ist die schwächste, weil sie die Entfernung einer Kachel zu ihrem Ziel ignoriert. $h_3$ (Tauschen) liegt nicht generell über $h_2$ und dominiert Manhattan nicht; die Folien führen es als eigenständige, ebenfalls zulässige Variante. Genau diese Rangfolge bestätigt die empirische Tabelle der Folien: Bei Lösungslänge 24 expandiert A* mit $h_1$ rund $39\,135$, mit $h_2$ nur $1\,641$ Knoten — „mit zunehmender Problemgröße ist $h_2$ spürbar besser als $h_1$”.

Assistent-Heuristiken (d) und deren Bewertung durch den Assistenten (g). Das Blatt verlangt ausdrücklich, einen KI-Assistenten nach n-Puzzle-Heuristiken zu fragen und ihn die Heuristiken anschließend selbst bewerten zu lassen. Ich habe das getan und die Antwort gegen meine eigene Lösung geprüft, statt sie zu übernehmen. Der Assistent nannte zu (d): fehlplatzierte Kacheln (Hamming), Manhattan-Distanz, Linear-Conflict (Manhattan + 2 je Konfliktpaar), Pattern-Database-Heuristiken (vorab gelöste Teilmengen, in einer Tabelle gespeichert) und die Walking-Distance/Gaschnig-Heuristik. Das deckt sich mit meinen $h_1,h_2,h_4$ und ergänzt zwei stärkere, in der Vorlesung nicht behandelte Verfahren: Pattern Databases dominieren Manhattan oft um Größenordnungen, sind aber speicher- statt rechenintensiv — ein lehrreicher Hinweis, den ich übernehme.

Zur Selbstbewertung (g) ordnete der Assistent die Heuristiken korrekt nach Zulässigkeit (alle genannten sind zulässig) und Informiertheit ($\text{Hamming} \le \text{Manhattan} \le \text{Linear Conflict} \le \text{Pattern DB}$) und benannte den Zielkonflikt Schärfe gegen Berechnungskosten. Ein Punkt war jedoch ungenau: Er bezeichnete pauschal „alle gängigen Heuristiken” als konsistent. Das stimmt für Hamming, Manhattan und Linear Conflict, ist bei manchen additiven Pattern Databases aber begründungsbedürftig. Genau das ist die Lehre des Blattes: Der Assistent liefert eine schnelle, weitgehend korrekte Landkarte, aber die Garantien (Zulässigkeit und Konsistenz) muss man fallweise selbst nachweisen — was ich für $h_1,h_2$ oben über die Relaxations-Argumente getan habe.

Implementierung: A* am 8-Puzzle#

Den Kern der Theorie — Zulässigkeit (gleiche optimale Länge) und Dominanz (weniger Expansionen) — habe ich für $h_1$ und $h_2$ in reinem Python nachgerechnet und BFS als blinde Referenz daneben gestellt. Alle drei lösen dieselbe feste Startstellung. (Die Folien wählen als Zieltest „Blank in der Mitte”; ich nutze die geläufigere Zielstellung mit Leerfeld unten rechts — am Vergleich von Zulässigkeit und Dominanz ändert das nichts.) Das Herzstück ist A* mit einer Prioritätswarteschlange nach $f=g+h$:

def astar(start, h):
    counter = 0
    frontier = [(h(start), 0, counter, start)]      # (f, g, tie, zustand)
    best_g = {start: 0}
    expanded = 0
    while frontier:
        f, g, _, state = heapq.heappop(frontier)
        if g > best_g.get(state, g):
            continue                                # veralteter Eintrag
        if state == GOAL:
            return {"loesungslaenge": g, "expandiert": expanded}
        expanded += 1
        for nxt in nachbarn(state):                 # Operatoren: Kachel schieben
            ng = g + 1
            if ng < best_g.get(nxt, 1 << 30):
                best_g[nxt] = ng
                counter += 1
                heapq.heappush(frontier, (ng + h(nxt), ng, counter, nxt))

Das vollständige Skript (beide Heuristiken, BFS, Plots) liegt in python/src/eport_figures/praxis/p_2_2_suche.py. Seine Ausgabe:

8-Puzzle — A* mit f(n) = g(n) + h(n)
  Start: 8 6 7  |  2 5 4  |  3 _ 1
  Ziel:  1 2 3  |  4 5 6  |  7 8 _
  Startwerte der Heuristiken: h1 = 7 (fehlplatzierte Steine), h2 = 21 (Manhattan)

  Strategie                      Laenge       expandiert
  ----------------------------------------------------
  BFS (blind, h = 0)                 31           181438
  A*, h1 fehlplatzierte Steine         31           143848
  A*, h2 Manhattan-Distanz           31            21197

  -> Alle drei finden dieselbe optimale Laenge (31 Zuege): empirischer Beleg fuer Zulaessigkeit.
  -> h1 spart gegenueber BFS Faktor 1.3 an Expansionen;
     h2 spart gegenueber h1 noch einmal Faktor 6.8.
  -> Dominanz h2 >= h1: 21 >= 7  =>  h2 ist die schaerfere Heuristik.
  -> Entlang des optimalen Pfads gilt h1, h2 <= h* an jedem Knoten: ja (nie ueberschaetzt).

Drei Befunde, die die Theorie tragen. Erstens: Alle drei Verfahren finden eine Lösung der Länge $31$ — der empirische Beleg, dass $h_1$ und $h_2$ zulässig sind und die Optimalität von A* nicht verletzen. Zweitens: Die blinde BFS fasst gut $181\,000$ Knoten an, bei $181\,440$ Gesamtzuständen also fast den ganzen Suchraum; $h_2$ kommt mit $21\,197$ aus, einer knappen Größenordnung weniger. Drittens die Dominanz: $h_2 \ge h_1$ punktweise (am Start $21 \ge 7$), und entsprechend expandiert $h_2$ rund $6{,}8$-mal weniger als $h_1$.

Dass die Heuristiken nie überschätzen und $h_2$ enger an der Wahrheit liegt, sieht man am direktesten, wenn man ihre Werte entlang des optimalen Pfades gegen die echten Restkosten $h^*$ aufträgt:

a) Vorgehen und Startposition. Versucht man es von Hand, lernt man schnell die entscheidende Falle: Man darf sich nicht in eine Ecke des noch freien Gebiets manövrieren, von der aus kein unbesuchtes Feld mehr erreichbar ist. Intuitiv steuert man deshalb zuerst die schwer erreichbaren Randfelder an und hebt sich die gut vernetzten Zentrumsfelder auf. Die Startposition ändert nichts an der grundsätzlichen Lösbarkeit (auf dem $8\times8$-Brett existieren Springerwege von jedem Feld aus), aber sie verschiebt, wie früh man in Engpässe gerät.

b) Repräsentation und Modellierung. Ein Zustand ist das Paar $(\text{aktuelles Feld}, \text{Menge der besuchten Felder})$ — formal ein Pfad, da kein Feld doppelt vorkommen darf. Operatoren sind die bis zu acht Springerzüge auf ein freies, noch unbesuchtes Feld im Brett. Der Zieltest ist „alle $64$ Felder besucht”. Der Suchraum ist gewaltig (der Verzweigungsgrad liegt bei bis zu $8$, die Tiefe bei $64$), weshalb naive Tiefensuche mit Backtracking zwar korrekt, aber langsam ist.

c) A* sinnvoll? Nur bedingt. A* glänzt, wenn Pfadkosten minimiert werden; beim Springerweg sind aber alle vollständigen Wege gleich lang ($63$ Züge) — es gibt keine Kosten zu minimieren, gesucht ist irgendeine vollständige Tour (ein Constraint-Satisfaction-artiges Erfüllbarkeitsproblem, vgl. 2.4). Eine sinnvolle A*-Variante wäre höchstens, $h$ als „Anzahl noch unbesuchter Felder” zu lesen und A* als Tiefensuche mit kluger Zugreihenfolge zu betreiben — was direkt zu (d) führt.

d) Beschleunigung: Warnsdorffs Regel. Die berühmte Heuristik (Warnsdorff, 1823) ist bestechend einfach: Ziehe stets auf das Feld mit den wenigsten noch freien Folgezügen. Sie steuert den Springer zuerst in die „klammen” Ecken, solange diese noch erreichbar sind, und vermeidet so die Sackgassen aus (a). Das beschleunigt die Suche dramatisch, weil sie den Verzweigungsfaktor des Suchbaums faktisch auf nahezu $1$ drückt — statt exponentiell zu verzweigen, folgt sie meist direkt einer Lösung, ganz ohne Backtracking. Mein Test bestätigt das eindrücklich:

=== Blatt 4, Aufgabe 5 — Springerweg auf 8x8 (Warnsdorff) ===
  Start (0,0): vollständiger Weg = True, 64/64 Felder besucht.
  Reine Warnsdorff-Regel ohne Backtracking: 61/64 Startfelder
  liefern direkt einen vollständigen Springerweg.

Von $61$ der $64$ Startfelder findet die reine greedy Warnsdorff-Regel ohne einen einzigen Rücksetzschritt sofort eine vollständige Tour; nur an drei Startfeldern müsste man sie um etwas Backtracking ergänzen. Das ist der Kern, warum Heuristiken Suche beschleunigen: Sie ersetzen blindes Probieren durch eine informierte Zugreihenfolge, die die teuren Teilbäume gar nicht erst betritt.

Querbezüge#

• 2.1 (Pfadplanung/Navigation): Das Labyrinth aus Aufgabe 2 ist genau das Anwendungsfeld von dort — A* ist der Standardplaner für Gitter- und Wegenetze, und die Wahl der Heuristik (Manhattan, Chebyshev, euklidisch) hängt am erlaubten Bewegungsmodell.
• 2.3 (Spielbäume): Auch Minimax/Alpha-Beta sind Suche, nur in einem Baum mit gegnerischen Zügen. Die Heuristik aus diesem Kapitel kehrt dort als Bewertungsfunktion für nicht-terminale Stellungen wieder.
• 2.4 (Backtracking/CSP): Backtracking ist Tiefensuche über partiellen Belegungen; die informierten Heuristiken (MRV, Forward Checking) spielen dieselbe Rolle wie $h(n)$ hier — sie lenken die Reihenfolge der Expansion.
• Algorithmen & Datenstrukturen: A* ist Dijkstra mit einer Potentialfunktion $h$; UCS ist Dijkstra. Beide leben von der Prioritätswarteschlange (Heap), deren $\mathcal{O}(\log n)$-Operationen die Laufzeit bestimmen — hier konkret Pythons heapq.
• Theoretische Informatik: Die Schranken $\mathcal{O}(b^d)$ und der Wurzelgewinn der bidirektionalen Suche sind Komplexitätsaussagen; die Konsistenzbedingung ist im Kern eine Dreiecksungleichung und macht den $f$-Wert zu einer monoton wachsenden Größe — verwandt mit Potential- und Reduktionsargumenten.

Quellen#

• Foliensatz _220_AI_ProbSearch.pdf — Grundlage für die Systematik blinde/informierte Suche und die Notation $f=g+h$. Der Foliensatz ist stark bildbasiert; die Begriffe habe ich daher mit Russell & Norvig abgeglichen, um Zulässigkeit und Konsistenz präzise zu fassen.
• Übungsblatt 4 ki_ueb220_Search.pdf — Aufgaben 1–3 und die Zusatzaufgabe 5 (Springerwege), hier ausgearbeitet. Das Labyrinth aus Aufgabe 2 habe ich pixelgenau aus dem PDF rekonstruiert und alle vier Strategien (bidirektionale BFS, UCS, gierig, A*) darauf laufen lassen; die allgemeine Form $f=\alpha g+\beta h$ des Blattes habe ich auf die Standardfälle zurückgeführt und die Erweiterungen (bewegliches Ziel, dynamische Hindernisse) auf die inkrementellen Planer D* Lite / D* bezogen.
• Warnsdorff (1823) — die klassische „wenigste-Folgezüge”-Regel für Springerwege; an ihr habe ich die Beschleunigung gegenüber blindem Backtracking (Aufgabe 5d) gemessen.
• Stentz (1994), Optimal and Efficient Path Planning for Partially-Known Environments (D*) — nachgeschlagen für die inkrementelle Neuplanung bei beweglichem Ziel und dynamischen Hindernissen (Aufgabe 2f/g).
• Russell & Norvig, Artificial Intelligence: A Modern Approach, Kap. 3 — als Referenz für die saubere Definition von Zulässigkeit, Konsistenz und Dominanz sowie für das 8-Puzzle als kanonisches Beispiel.
• Hart, Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths — die Originalarbeit, die A* samt $f=g+h$ und der Zulässigkeitsbedingung einführt; nachgeschlagen, um die Folien-Notation an der Primärquelle zu prüfen.
• aima-python (search4e.ipynb) und die n-Puzzle-Web-Demo — ausprobiert, um die Stellung und die optimale Zuglänge gegenzuprüfen; meine eigene Implementierung reproduziert die dort beobachtete Expansionshierarchie BFS $\gg h_1 \gg h_2$.