lernzettel_classical-search_31-05-26

ai-generated methods-of-ai exam-prep

Warum dieser Lernzettel

Die MoAI-Vorlesung (SoSe 26) lehrt klassische Suche NICHT als Thema. Sie taucht nur in 3 Lectures kurz auf:

• Introduction — Slide listet „Systematic search: DFS, BFS, Uniform-cost search …” (nur Erwähnung).
• Session 04 Planning I — „Classical Search (Forward Planning): uninformed search: usually variants of depth-first search; informed search with variants of A*” (Kontext: Planen als Suche).
• Session 10 ML II — „ID3 performs a top-down, breadth-first, greedy search” (BFS als Suchstrategie in ID3).

Kein Pseudocode, keine Eigenschaften-Analyse, keine Übung. → Hintergrundwissen, das du selbst draufhaben musst. Relevant für quiz_paper-transformers-search_28-05-26 Q14 (Path-merging vs BFS/DFS/A*) und allgemeine Such-Fragen in der mündlichen Prüfung.

---

BFS — Breadth-First Search

• Idee: expandiert die Frontier schichtweise (alle Knoten in Tiefe $d$, bevor Tiefe $d+1$). Datenstruktur: FIFO-Queue.
• Properties:
  • Complete (in endlichen Graphen): findet Lösung, wenn eine existiert.
  • Optimal für gleiche Kantenkosten (kürzester Pfad in Kanten).
  • Zeit: $O(b^d)$ — $b$ = Verzweigungsgrad, $d$ = Tiefe des flachsten Goals.
  • Speicher: $O(b^d)$ — alle Knoten der aktuellen Schicht in der Queue → Hauptschwäche.
• Wann: Lösung garantiert nah, Speicher reicht aus, Kosten uniform.

DFS — Depth-First Search

• Idee: geht so tief wie möglich, bevor zurückgesetzt wird (Backtracking). Datenstruktur: LIFO-Stack (oder Rekursion).
• Properties:
  • Complete: nur in endlichen Graphen ohne Zyklen (oder mit visited-Set); im allgemeinen Tree-Search NICHT complete.
  • NICHT optimal: liefert die erste gefundene Lösung, nicht die kürzeste.
  • Zeit: $O(b^m)$ — $m$ = maximale Tiefe (kann ≫ $d$ sein).
  • Speicher: $O(b\cdot m)$ — nur der aktuelle Pfad + Geschwister → sehr speichereffizient, Hauptvorteil.
• Wann: Lösungen tief & häufig, Speicher knapp, Optimalität egal. Backtracking-Search in CSP ist DFS-artig.

A* — Informed Best-First Search

• Idee: expandiert den Knoten mit kleinstem $f(n)=g(n)+h(n)$, wobei
  • $g(n)$ = tatsächliche Kosten vom Start bis $n$,
  • $h(n)$ = Heuristik: geschätzte Restkosten von $n$ zum Goal.
    Datenstruktur: Priority Queue geordnet nach $f$.
• Properties:
  • Complete (in endlichen Graphen).
  • Optimal ⇔ $h$ ist admissible (unterschätzt nie die wahren Kosten): $h(n)\le h^{\ast }(n)$.
  • Konsistent (monotone Heuristik) $h(n)\le c(n,n^{\prime })+h(n^{\prime })$ ⇒ $A^{\ast }$ noch effizienter (kein Re-Expansion nötig).
  • Zeit/Speicher: stark abhängig von $h$ — bei perfektem $h^{\ast }$ linear; bei $h=0$ degeneriert zu Uniform-Cost / BFS.
• Wann: informierte Suche, gute Heuristik vorhanden, Optimalität gefordert.

---

⚖️ Vergleichstabelle (für Q14 Aufschlag)

	BFS	DFS	A*	Path-Merging (Paper)
complete?	ja (endlich)	ja (endlich, ohne Zyklen)	ja	gelernt, ~approximativ
optimal?	ja (uniform cost)	nein	ja (admissible $h$)	n/a (es entscheidet nur den next vertex)
Frontier	FIFO-Queue	LIFO-Stack	Priority Queue ($f=g+h$)	reachable-set in jedem Token
Exploration	seriell, schichtweise	seriell, tief + Backtrack	seriell, best-first	parallel über alle Vertices
Tiefe in $L$	$\propto L$ (linear)	$\propto L$	abhängig von $h$	$\propto {\log }_{2}L$ (logarithmisch)
Beweisbarkeit	klassisch beweisbar	klassisch beweisbar	klassisch beweisbar	empirisch; non-maximale Merges → Generalisierungs-Ceiling

---

🎯 Connection zum Exam-Paper (Q14)

• Task des Papers ist klassische path-based Suche über einen DAG → vergleichbar zu BFS/DFS/A*, nicht Hill Climbing.
• Path-Merging ist die parallele/log-depth Variante einer transitive closure (entspricht repeated squaring der Erreichbarkeits-Relation), während BFS/A* seriell, linear in Pfadlänge sind.
• Trade-off: klassische Suche = beweisbar korrekt + skalierbar; gelernte Suche (Path-Merging) = approximativ (non-maximal merges, Ceiling bei $L\ge 14$). Das motiviert neuro-symbolische Hybride (LLM-modulo).

⚠️ Häufige Stolperfallen

• DFS ist nicht complete im allgemeinen Tree-Search — nur in endlichen Graphen oder mit Cycle-Check. In der Praxis nutzt man iterative deepening für completeness + space efficiency.
• A*-Optimalität braucht admissible $h$. Eine inkonsistente, aber admissible $h$ ist noch ok (Optimalität ja, Effizienz schlechter). Inadmissible $h$ → keine Optimalitätsgarantie.
• „Frontier” ≠ „visited”: BFS/A* speichern beides; Local Search (im Gegensatz!) speichert nur den aktuellen Zustand.
• Backtracking-Search in CSP = DFS mit constraint-checking → completeness ja, effizient durch heuristics (MRV, LCV) + arc-consistency-Preprocessing.

🎙️ Oral-Exam One-Liners

• „Was macht eine Heuristik gut?” → admissibility (unterschätzt nie die wahre Restdistanz) ⇒ $A^{\ast }$ bleibt optimal. Consistency (monotone) ⇒ $A^{\ast }$ effizient, kein Re-Expansion.
• „Warum nicht immer DFS?” → keine Optimalität, schlechte Worst-Case-Zeit; aber Speicher schlägt BFS in tiefen Räumen → wann immer Optimalität egal & Speicher knapp.
• „BFS vs A*?” → BFS = uninformiert, optimal bei uniform cost, exponentielles Memory; A* = informiert, optimal bei admissibler $h$, deutlich besser wenn $h$ informativ.
• „Wie passt das zum Paper?” → Path-Merging ist eine parallele, log-tiefe Approximation desselben Problems (graph connectivity), das BFS/A* seriell, linear lösen — daher in Aufgabe vergleichbar, im Mechanismus fundamental anders.

---

see also

• quiz_paper-transformers-search_28-05-26 — Q14 Search-Connection
• lernzettel_local-search_30-04-26 (falls vorhanden) — Local Search ≠ klassische Suche
• Methods of AI Lecture