Pathfinding (Graphsuche)
Die unauffällige Mathematik hinter Google Maps, Spielfiguren und Logistik.
Wegfindungsalgorithmen
Stell dir vor, du bist in einer fremden Stadt und suchst den Weg zum Bahnhof. Es gibt verschiedene Suchstrategien:
Uninformierte Suche (wie BFS oder Dijkstra): Durchsucht systematisch alle Straßen, ohne zu wissen wo der Bahnhof ist. Gründlich, aber zeitaufwändig. Informierte Suche (wie A* oder Greedy): Nutzt einen 'Kompass' - schätzt die Richtung zum Ziel und priorisiert Wege, die dorthin führen.
Die Wahl des richtigen Algorithmus hängt von der Situation ab: Brauchst du den kürzesten Weg? Wie viel weißt du über den Standort des Ziels?
Analogie:
Stell dir vor, du bist in einer fremden Stadt und suchst den Weg zum Bahnhof. Es gibt verschiedene Suchstrategien:
Uninformierte Suche (wie BFS oder Dijkstra): Durchsucht systematisch alle Straßen, ohne zu wissen wo der Bahnhof ist. Gründlich, aber zeitaufwändig. Informierte Suche (wie A* oder Greedy): Nutzt einen 'Kompass' - schätzt die Richtung zum Ziel und priorisiert Wege, die dorthin führen.
Die Wahl des richtigen Algorithmus hängt von der Situation ab: Brauchst du den kürzesten Weg? Wie viel weißt du über den Standort des Ziels?
Definition:
Wegfindungsalgorithmen suchen nach Routen durch einen Graphen von einem Startknoten zu einem Zielknoten. Sie unterscheiden sich darin, wie sie priorisieren, welche Knoten als nächstes erkundet werden: Manche garantieren den kürzesten Weg (optimal), andere sind schneller, finden aber möglicherweise suboptimale Routen. Die folgenden Algorithmen demonstrieren diese verschiedenen Strategien.
So funktioniert diese Demo
Diese Demo zeigt, wie verschiedene Wegfindungsalgorithmen arbeiten. Du kannst den Algorithmus bei der Arbeit beobachten und sehen, wie er Schritt für Schritt den Weg findet.
Interaktion mit der Demo
Zeichne Wände auf das Raster, um Hindernisse zu erstellen. Setze Start- und Zielpunkte. Wähle einen Algorithmus und klicke 'Start', um die Suche zu beobachten.
Was die Farben bedeuten
Gelbe Zellen sind in der Open List (noch zu erkunden). Blaue Zellen wurden bereits besucht (Closed List). Der grüne Pfad zeigt die gefundene Route.
Die verschiedenen Algorithmen
Jeder Algorithmus sucht anders: A* nutzt eine Heuristik für die Richtung, Dijkstra sucht gleichmäßig in alle Richtungen, und Greedy rennt direkt zum Ziel. Vergleiche sie, um ihre Stärken und Schwächen zu sehen.
Interaktive Pathfinding-Demo
Was auf dem Spielfeld passiert
Diese Demo sucht den kürzesten Weg durch ein Gitter. Hier steht, was du auf dem Bild siehst — die Zahlen unter dem Gitter zählen das Ganze mit.
- Was du siehst
- Ein Gitter aus Kacheln mit einem Start (🤖), einem Ziel (🚩) und schwarzen Wänden dazwischen. Rund um den Start liegt eine Fläche eingefärbter Felder, die um die Wände herumreicht.
- Was passiert
- Vom Start aus wächst eine Front besuchter Felder nach außen und fließt um die Wände herum — wie sich ausbreitendes Wasser. Sobald sie das Ziel erreicht, leuchtet der kürzeste Weg als zusammenhängende Linie vom Start zum Ziel auf.
- Was du tun kannst
- Zeichne Wände oder verschiebe Start und Ziel, wähle einen Algorithmus, und starte die Suche oder gehe Schritt für Schritt vor. Über das Tempo bestimmst du, wie schnell sich die Front ausbreitet.
- Worauf du achtest
- Die Suche tastet nicht blind in alle Richtungen. Manche Verfahren streben gezielt Richtung Ziel, andere breiten sich gleichmäßig aus — den kürzesten Weg finden sie am Ende garantiert.
Benannt nach den rechtwinkligen Straßen von Manhattan: Man kann nur horizontal oder vertikal gehen, nie schräg. Die Distanz ist die Summe der Schritte in X- und Y-Richtung.
Wähle ein Szenario, um verschiedene Algorithmus-Verhaltensweisen zu beobachten:
So funktioniert A*
Der A* Suchalgorithmus
A* (gesprochen 'A-Stern') ist einer der beliebtesten Wegfindungsalgorithmen. Er wurde 1968 von Peter Hart, Nils Nilsson und Bertram Raphael entwickelt. A* kombiniert das Beste aus Dijkstras Algorithmus (garantiert kürzester Weg) mit der Greedy Best-First-Suche (schnelle Richtungssuche).
Die Schlüsselidee von A* ist die Formel f(n) = g(n) + h(n), wobei g(n) die tatsächlichen Kosten vom Start zum aktuellen Knoten sind und h(n) die geschätzten Kosten vom aktuellen Knoten zum Ziel (die Heuristik). Durch das ständige Expandieren des Knotens mit dem niedrigsten f-Wert findet A* effizient den optimalen Pfad.
Die Heuristik-Funktion
Die Heuristik h(n) ist eine Schätzung der verbleibenden Distanz. Gängige Heuristiken sind: Manhattan-Distanz (Summe horizontaler und vertikaler Abstände), Euklidische Distanz (Luftlinie), und Chebyshev-Distanz (Maximum aus horizontalem und vertikalem Abstand).
Damit A* den optimalen Pfad garantiert, muss die Heuristik zulässig sein - sie darf die tatsächlichen Kosten niemals überschätzen. Eine optimistische Heuristik stellt sicher, dass wir keinen besseren Pfad verpassen.
Vorteile von A*
- Optimal: Garantiert den kürzesten Pfad bei zulässiger Heuristik
- Effizient: Erkundet weniger Knoten als Dijkstra durch Richtungsführung
- Flexibel: Funktioniert mit verschiedenen Heuristiken für unterschiedliche Szenarien
- Vollständig: Findet einen Pfad, wenn einer existiert
Praktische Anwendungen
A* wird überall eingesetzt: Videospiel-Wegfindung, GPS-Navigation, Robotik, Netzwerk-Routing, Puzzle-Lösung (wie das 15-Puzzle) und KI-Planung. Seine Effizienz und Optimalität machen ihn zum Standard-Algorithmus für Wegfindungsprobleme.
Probiere die Demo! Beobachte, wie A* die Heuristik nutzt, um den kürzesten Pfad effizient zu finden. Vergleiche mit Dijkstra, um den Unterschied zu sehen!
1
# A* Wegfindungsalgorithmus
2
funktion a_stern(start, ziel, raster):
3
# Finde kürzesten Pfad mit Heuristik-Führung
4
open_liste = PrioritätsWarteschlange() # Zu erkunden
5
closed_liste = Menge() # Bereits erkundet
6
open_liste.hinzufügen(start, f=0)
7
8
solange open_liste nicht leer:
9
# Wähle Knoten mit niedrigstem f-Wert
10
aktuell = open_liste.hole_niedrigstes_f()
11
open_liste.entferne(aktuell)
12
closed_liste.hinzufügen(aktuell)
13
14
# Prüfe ob Ziel erreicht
15
wenn aktuell == ziel:
16
pfad = rekonstruiere_pfad(aktuell)
17
gib pfad zurück # Erfolg!
18
19
# Erkunde alle Nachbarn
20
für jeden nachbar von aktuell:
21
wenn nachbar in closed_liste:
22
weiter # Überspringe bereits erkundete
23
24
# Berechne vorläufigen g-Wert
25
vorläufig_g = aktuell.g + distanz(aktuell, nachbar)
26
27
wenn nachbar nicht in open_liste:
28
open_liste.hinzufügen(nachbar)
29
sonst wenn vorläufig_g < nachbar.g:
30
# Besseren Pfad gefunden!
31
32
# Aktualisiere Nachbar-Werte
33
nachbar.g = vorläufig_g
34
nachbar.h = heuristik(nachbar, ziel)
35
nachbar.f = nachbar.g + nachbar.h
36
nachbar.vorgänger = aktuell
37
38
gib null zurück # Kein Pfad gefunden
🚀 Listen initialisieren
Erstelle die Open-Liste (zu erkundende Knoten) und Closed-Liste (bereits erkundet). Füge den Startknoten zur Open-Liste mit f=0 hinzu.
open_liste = PrioritätsWarteschlange() # Zu erkunden
closed_liste = Menge() # Bereits erkundet
open_liste.hinzufügen(start, f=0)
🏁 Start
Initialisiere Open- und Closed-Listen. Füge Startknoten hinzu mit g=0, h=Heuristik zum Ziel.
📊 Knoten wählen
Hole Knoten mit niedrigstem f-Wert. Verschiebe von Open zu Closed.
🎯 Zielprüfung
Ist dies das Ziel? Wenn ja, rekonstruiere Pfad. Wenn nein, weiter erkunden.
🔀 Expandieren
Hole alle begehbaren Nachbarn. Überspringe die in Closed-Liste.
🧮 Bewerten
Berechne f = g + h für jeden Nachbarn. Aktualisiere wenn besserer Pfad gefunden.
So funktioniert Dijkstra
Dijkstras Algorithmus
Dijkstras Algorithmus, 1956 von Edsger Dijkstra erfunden, findet den kürzesten Weg von einem Startknoten zu allen anderen Knoten im Graphen. Anders als A* verwendet er keine Heuristik - er erkundet systematisch in alle Richtungen.
Der Algorithmus verwaltet einen Distanzwert für jeden Knoten. Beginnend mit 0 am Startknoten, expandiert er immer den Knoten mit der kleinsten bekannten Distanz. Das garantiert das Finden des optimalen Pfades.
Wie es funktioniert
Dijkstra expandiert in einem kreisförmigen Muster vom Start, wie Wellen auf dem Wasser. Er besucht Knoten in der Reihenfolge ihrer Distanz zum Start und stellt so sicher, dass der kürzeste Pfad gefunden wird, wenn das Ziel erreicht ist.
Eigenschaften
- Optimal: Findet immer den kürzesten Pfad
- Vollständig: Findet einen Pfad, wenn einer existiert
- Keine Heuristik: Kennt die Zielrichtung nicht
- Mehr Exploration: Besucht oft mehr Knoten als A*
Schau dir die Demo an! Sieh wie Dijkstra in alle Richtungen erkundet - vergleiche mit A*, um den Unterschied zu sehen!
1
# Dijkstras Kürzester-Pfad-Algorithmus
2
funktion dijkstra(start, ziel, graph):
3
# Finde kürzesten Pfad ohne Heuristik
4
open_list = PrioritätsWarteschlange() # Zu erkunden
5
closed_list = Menge() # Erkundet
6
start.distanz = 0
7
open_list.hinzufügen(start)
8
9
solange open_list nicht leer:
10
# Wähle Knoten mit kleinster Distanz
11
aktuell = open_list.hole_min_distanz()
12
open_list.entfernen(aktuell)
13
closed_list.hinzufügen(aktuell)
14
15
# Prüfe ob Ziel erreicht
16
wenn aktuell == ziel:
17
pfad = rekonstruiere_pfad(aktuell)
18
gib pfad zurück # Gefunden!
19
20
# Erkunde alle Nachbarn
21
für jeden nachbar von aktuell:
22
wenn nachbar in closed_list:
23
weiter # Überspringe erkundete
24
25
# Berechne neue Distanz
26
neue_dist = aktuell.distanz + kantenkosten
27
wenn neue_dist < nachbar.distanz:
28
nachbar.distanz = neue_dist
29
nachbar.eltern = aktuell
30
wenn nachbar nicht in open_list:
31
open_list.hinzufügen(nachbar)
32
33
gib null zurück # Kein Pfad gefunden
🚀 Initialisierung
Erstelle Open-Liste (Prioritätswarteschlange) und Closed-Liste. Setze Startknoten-Distanz auf 0, alle anderen auf Unendlich. Füge Start zur Open-Liste hinzu.
open_list = PrioritätsWarteschlange() # Zu erkunden
closed_list = Menge() # Erkundet
start.distanz = 0
open_list.hinzufügen(start)
🏁 Start
Initialisiere Distanzen. Start = 0, andere = Unendlich.
📊 Auswahl
Hole Knoten mit minimaler Distanz aus Open-Liste.
🎯 Prüfung
Ist dies das Ziel? Ja = fertig! Nein = weiter.
🔀 Expandieren
Hole alle Nachbarn. Überspringe bereits erkundete.
🧮 Aktualisieren
Berechne neue Distanzen. Aktualisiere wenn kürzer.
So funktioniert Greedy Best-First
Greedy Best-First Search
Greedy Best-First Search bewegt sich immer so direkt wie möglich zum Ziel. Er berücksichtigt nur die Heuristik h(n) - die geschätzte Entfernung zum Ziel - und ignoriert, wie weit er bereits gelaufen ist.
Das macht ihn sehr schnell wenn keine Hindernisse im Weg sind, aber er kann in Sackgassen geraten, weil er die tatsächlichen Pfadkosten nicht berücksichtigt.
Der gierige Ansatz
Wie jemand, der auf einen Berg zuläuft - immer in seine Richtung, ohne zu bedenken, ob eine Klippe im Weg ist. Schnell wenn der Weg frei ist, problematisch wenn Hindernisse existieren.
Eigenschaften
- Schnell: Geht direkt zum Ziel
- Nicht Optimal: Findet möglicherweise nicht den kürzesten Pfad
- Kann stecken bleiben: Fallen täuschen ihn leicht
- Wenig Speicher: Erkundet weniger Knoten
Probiere das Spiral-Szenario! Schau wie Greedy in die Falle läuft, während A* den Weg drumherum findet.
1
# Greedy Best-First Search
2
funktion greedy_suche(start, ziel):
3
# Folge immer der Heuristik
4
open_list = PrioritätsWarteschlange() # Nach h-Wert
5
closed_list = Menge() # Erkundet
6
open_list.hinzufügen(start)
7
8
solange open_list nicht leer:
9
# Wähle Knoten nächsten zum Ziel (h)
10
aktuell = open_list.hole_min_h()
11
open_list.entfernen(aktuell)
12
closed_list.hinzufügen(aktuell)
13
14
# Prüfe ob Ziel erreicht
15
wenn aktuell == ziel:
16
pfad = rekonstruiere_pfad(aktuell)
17
gib pfad zurück # Gefunden!
18
19
# Erkunde Nachbarn
20
für jeden nachbar von aktuell:
21
wenn nachbar in closed_list:
22
weiter # Überspringe erkundete
23
24
# Berechne nur Heuristik
25
nachbar.h = heuristik(nachbar, ziel)
26
nachbar.eltern = aktuell
27
wenn nachbar nicht in open_list:
28
open_list.hinzufügen(nachbar)
29
30
gib null zurück # Kein Pfad gefunden
🚀 Initialisierung
Erstelle Open-Liste und Closed-Liste. Füge Startknoten zur Open-Liste hinzu. Keine Distanzverfolgung nötig - nur Heuristik zählt.
open_list = PrioritätsWarteschlange() # Nach h-Wert
closed_list = Menge() # Erkundet
open_list.hinzufügen(start)
🏁 Start
Füge Start zur Open-Liste hinzu.
🧭 Auswahl
Hole Knoten mit kleinstem h (nächster zum Ziel).
🎯 Prüfung
Ist dies das Ziel? Ja = fertig! Nein = weiter.
🔀 Expandieren
Hole Nachbarn. Überspringe erkundete.
🧮 Bewerten
Berechne h für jeden Nachbar.
So funktioniert Breitensuche
Breitensuche (BFS)
BFS erkundet einen Graphen Ebene für Ebene, wie Wellen, die sich von einem in Wasser geworfenen Stein ausbreiten. Er besucht zuerst alle Knoten mit Distanz 1, dann Distanz 2, dann Distanz 3, und so weiter.
Mit einer Warteschlange (FIFO) garantiert BFS das Finden des kürzesten Pfades in ungewichteten Graphen - wo alle Kanten die gleichen Kosten haben.
Das Wellenmuster
Stell dir vor, du wirfst einen Stein in einen Teich - die Wellen breiten sich gleichmäßig in alle Richtungen aus. BFS funktioniert genauso und erkundet alle Richtungen gleichmäßig, bevor er sich weiter vom Start entfernt.
Eigenschaften
- Optimal: Kürzester Pfad in ungewichteten Graphen
- Vollständig: Findet immer einen Pfad wenn einer existiert
- Fair: Erkundet alle Richtungen gleichmäßig
- Hoher Speicherbedarf: Speichert alle Knoten der aktuellen Ebene
Schau dir die Demo an! Sieh wie BFS sich wie eine Welle ausbreitet - vergleiche mit DFS um den Unterschied zu sehen!
1
# Breitensuche
2
funktion bfs(start, ziel):
3
# Erkunde Ebene für Ebene
4
warteschlange = Warteschlange() # FIFO Reihenfolge
5
besucht = Menge() # Verfolge besuchte
6
warteschlange.einreihen(start)
7
besucht.hinzufügen(start)
8
9
solange warteschlange nicht leer:
10
# Hole nächsten Knoten (FIFO)
11
aktuell = warteschlange.ausreihen()
12
13
# Prüfe ob Ziel erreicht
14
wenn aktuell == ziel:
15
pfad = rekonstruiere_pfad(aktuell)
16
gib pfad zurück # Gefunden!
17
18
# Füge alle Nachbarn zur Warteschlange hinzu
19
für jeden nachbar von aktuell:
20
wenn nachbar nicht in besucht:
21
besucht.hinzufügen(nachbar)
22
nachbar.eltern = aktuell
23
warteschlange.einreihen(nachbar)
24
25
gib null zurück # Kein Pfad gefunden
🚀 Initialisierung
Erstelle Warteschlange und Besucht-Menge. Füge Start zur Warteschlange hinzu und markiere als besucht.
warteschlange = Warteschlange() # FIFO Reihenfolge
besucht = Menge() # Verfolge besuchte
warteschlange.einreihen(start)
besucht.hinzufügen(start)
🏁 Start
Erstelle Warteschlange. Füge Start hinzu.
➡️ Ausreihen
Nimm ersten Knoten aus Warteschlange.
🎯 Prüfung
Ist dies das Ziel? Ja = fertig!
🔀 Expandieren
Hole alle unbesuchten Nachbarn.
➕ Einreihen
Füge Nachbarn ans Ende der Warteschlange.
So funktioniert Tiefensuche
Tiefensuche (DFS)
DFS erkundet so weit wie möglich entlang jedes Zweigs, bevor er zurückgeht. Er geht zuerst tief in den Graphen und erkundet andere Pfade erst, wenn er auf eine Sackgasse trifft.
Mit einem Stapel (LIFO) ist DFS speichereffizient, garantiert aber nicht das Finden des kürzesten Pfades.
Der Labyrinth-Erkunder
Stell dir vor, du erkundest ein Labyrinth, indem du an jeder Kreuzung immer in die gleiche Richtung abbiegst (z.B. rechts). Du wirst schließlich alles erkunden, aber du könntest lange Umwege machen.
Eigenschaften
- Speichereffizient: Speichert nur den aktuellen Pfad
- Nicht Optimal: Kann lange Umwege finden
- Vollständig: Findet einen Pfad wenn er existiert (endliche Graphen)
- Schnell für tiefe Ziele: Gut wenn Ziel weit vom Start entfernt
Schau dir die Demo an! Sieh wie DFS tief taucht bevor er zurückgeht - vergleiche mit BFS!
1
# Tiefensuche
2
funktion dfs(start, ziel):
3
# Erst tief, dann breit
4
stapel = Stapel() # LIFO Reihenfolge
5
besucht = Menge() # Verfolge besuchte
6
stapel.push(start)
7
8
solange stapel nicht leer:
9
# Hole Oberseite des Stapels
10
aktuell = stapel.pop()
11
12
wenn aktuell in besucht:
13
weiter # Überspringe wenn gesehen
14
besucht.hinzufügen(aktuell)
15
16
# Prüfe ob Ziel erreicht
17
wenn aktuell == ziel:
18
pfad = rekonstruiere_pfad(aktuell)
19
gib pfad zurück # Gefunden!
20
21
# Lege Nachbarn auf Stapel
22
für jeden nachbar von aktuell:
23
wenn nachbar nicht in besucht:
24
nachbar.eltern = aktuell
25
stapel.push(nachbar)
26
27
gib null zurück # Kein Pfad gefunden
🚀 Initialisierung
Erstelle Stapel und Besucht-Menge. Lege Startknoten auf den Stapel.
stapel = Stapel() # LIFO Reihenfolge
besucht = Menge() # Verfolge besuchte
stapel.push(start)
🏁 Start
Erstelle Stapel. Lege Start drauf.
⬆️ Pop
Nimm obersten Knoten vom Stapel.
🎯 Prüfung
Ist dies das Ziel? Ja = fertig!
🔀 Expandieren
Hole alle unbesuchten Nachbarn.
⬇️ Push
Lege Nachbarn auf den Stapel.
Teste dein Wissen
Was berechnet die Formel f(n) = g(n) + h(n) bei A*?
1. Was berechnet die Formel f(n) = g(n) + h(n) bei A*?
- ☐ A) Nur die Distanz vom Start zum aktuellen Knoten
- ☐ B) Die geschätzten Gesamtkosten vom Start zum Ziel über diesen Knoten
- ☐ C) Nur die geschätzte Distanz zum Ziel
- ☐ D) Die Anzahl der Wände zwischen Start und Ziel
2. Warum ist A* in den meisten Fällen schneller als Dijkstra?
- ☐ A) A* benötigt weniger Speicher
- ☐ B) A* überspringt Wände automatisch
- ☐ C) A* nutzt eine Heuristik um vielversprechende Richtungen zu priorisieren
- ☐ D) A* verarbeitet Knoten in zufälliger Reihenfolge
3. Was muss für die Heuristik h(n) gelten, damit A* den kürzesten Weg garantiert?
- ☐ A) Sie darf die tatsächlichen Kosten nie überschätzen (zulässig)
- ☐ B) Sie muss immer gleich null sein
- ☐ C) Sie muss größer als g(n) sein
- ☐ D) Sie muss ein zufälliger Wert sein
4. Was ist die Open List bei A*?
- ☐ A) Eine Liste aller Wände im Raster
- ☐ B) Eine Liste der Knoten, die bereits vollständig untersucht wurden
- ☐ C) Eine Liste der unerreichbaren Knoten
- ☐ D) Eine Liste der entdeckten aber noch nicht vollständig untersuchten Knoten
5. Wann würde Greedy Best-First Search versagen, während A* erfolgreich ist?
- ☐ A) Wenn das Raster sehr groß ist
- ☐ B) Wenn Hindernisse eine Falle bilden, in die Greedy hineinläuft
- ☐ C) Wenn es keinen Weg zum Ziel gibt
- ☐ D) Wenn Start und Ziel nebeneinander liegen
6. Welche Datenstruktur verwendet die Tiefensuche (DFS)?
- ☐ A) Warteschlange (FIFO)
- ☐ B) Stapel (LIFO)
- ☐ C) Prioritätswarteschlange
- ☐ D) Hashtabelle
7. Welcher Algorithmus garantiert den kürzesten Weg in einem ungewichteten Graphen?
- ☐ A) Tiefensuche (DFS)
- ☐ B) Greedy Best-First Search
- ☐ C) Breitensuche (BFS)
- ☐ D) Keiner der genannten
8. Was ist der Hauptunterschied zwischen Dijkstra und A*?
- ☐ A) Dijkstra ist schneller
- ☐ B) A* nutzt eine Heuristik um die Suche zum Ziel zu lenken
- ☐ C) Dijkstra funktioniert nur auf Gittern
- ☐ D) A* kann keinen kürzesten Weg finden
9. Warum ist DFS speichereffizienter als BFS?
- ☐ A) DFS besucht weniger Knoten
- ☐ B) DFS muss nur den aktuellen Pfad speichern, nicht alle Knoten einer Ebene
- ☐ C) DFS verwendet eine kleinere Datenstruktur
- ☐ D) DFS verfolgt besuchte Knoten nicht
10. Welche Aussage über BFS ist korrekt?
- ☐ A) BFS verwendet einen Stapel (LIFO)
- ☐ B) BFS erkundet Knoten in der Reihenfolge ihrer Distanz zum Start
- ☐ C) BFS findet immer den längsten Weg
- ☐ D) BFS benötigt eine Heuristikfunktion
Verwandte Inhalte
Artikel
Algorithmische Komplexität
Die Lehre, dass ein eleganter Algorithmus jeden Supercomputer schlägt — vorausgesetzt, n ist groß genug.
Kontrollstrukturen
Kontrollstrukturen: alles, was zwischen "tu dies" und "tu das" entscheidet.
Datenstrukturen II (Hierarchisch & Vernetzt)
Bäume, Suchbäume und Graphen — Datenstrukturen mit Familienverhältnissen.
Regeln & Logik: Expertensysteme
Die KI, bevor sie aus Daten lernte: Experten gefragt, Regeln aufgeschrieben, gehofft.
Suche im Graphen — Die Anfänge
Graphsuche: das erste, was KI tatsächlich konnte — und immer noch nützlich ist.
Heuristiken & Pfadsuche: Von Dijkstra zu A*
Wie A* funktioniert — und warum Dijkstra ohne Heuristik schnell langweilig wird.
Datenstrukturen I (Linear)
Die einfachsten Arten, Daten zu sortieren — Reihen, Stapel und Schlangen.
MinMax & Pruning
MinMax in der Praxis: rückwärts denken, vom schlimmsten Gegner ausgehen, abkürzen wo möglich.
Rekursion
Rekursion: die Programmiertechnik, die einfach aussieht, bis man sie versteht. Und dann auch.
Was ist ein Algorithmus?
Was Euklid, IKEA-Anleitungen und Google-Suche gemeinsam haben — alle drei sind Algorithmen.
Demo
Schwarmintelligenz (Boids)
Erlebe, wie aus drei simplen lokalen Regeln das komplexe Verhalten eines Vogelschwarms entsteht.
MinMax (Spieltheorie)
Erlebe Spieltheorie hautnah: Spiele gegen eine KI und beobachte, wie sie den optimalen Zug berechnet.
Regelbasierte KI
Sammle Hinweise und löse Kriminalfälle durch systematische Anwendung regelbasierter Logik. Diese interaktive Demo zeigt, wie KI-Systeme Schritt für Schritt zu Lösungen gelangen.
Travelling Salesman: Algorithmen im Wettstreit
Setze Städte, zeichne deine eigene Route und lass Greedy, Simulated Annealing und Genetic Algorithm gegen dich antreten.