Symbolische KI & Problemlösung durch Suche
Problem-Solving by Search: Graphen und Suchalgorithmen
Lernziele dieser Lektion
- Verstehen, wie reale Probleme als Graphen dargestellt werden können
- Den Unterschied zwischen einem Graphen und einem Suchbaum erklären können
- Die Suchalgorithmen BFS (Breitensuche) und DFS (Tiefensuche) beschreiben und vergleichen können
- Wissen, dass fortgeschrittene Algorithmen (Dijkstra, A*) optimale Lösungen finden können
Problem-Solving by Search
Eine der wichtigsten Techniken der symbolischen KI ist das Problemlösen durch Suche (Problem-Solving by Search). Die Idee: Ein reales Problem wird in eine durchsuchbare Struktur umgewandelt, und dann wird systematisch nach einer Lösung gesucht.
Schritt 1: Das Problem als Graph darstellen
Ein Graph besteht aus Knoten (Orte, Zustände) und Kanten (Verbindungen, Wege). Die Kanten können gewichtet sein – z.B. mit Entfernungen oder Kosten.
Beispiel: Route von Arad nach Bukarest
Stellen wir uns vor, wir suchen die kürzeste Route von Arad nach Bukarest in Rumänien. Wir modellieren die Landkarte als Graph:
- Knoten: Städte (Arad, Timisoara, Satu Mare, Brasov, Craiova, Bukarest)
- Kanten: Strassenverbindungen mit Distanzen (z.B. Arad–Timisoara: 316 km, Arad–Satu Mare: 354 km)
Schritt 2: Den Graphen als Baum darstellen
Um den Graphen systematisch zu durchsuchen, wird er in einen Suchbaum umgewandelt. Der Startknoten (Arad) bildet die Wurzel. Von jedem Knoten aus werden alle möglichen nächsten Schritte als Kindknoten dargestellt.
Der Baum zeigt alle möglichen Wege – auch solche, die über Umwege führen. Es gibt mehrere Pfade von Arad nach Bukarest, mit unterschiedlichen Distanzen.
Dies ist nur ein kurzer Auszug. Die vollständige Lektion mit interaktiven Übungen und Lernfortschritts-Tracking gibt es nach Einlösung eines Einschreibeschlüssels.