Suchalgorithmen in der KI: Python-Tutorial für CS6601 Assignment 1

Einführung in Suchalgorithmen für KI

Suchalgorithmen sind das Herzstück der Künstlichen Intelligenz. Sie helfen dabei, Probleme zu lösen, bei denen die Lösung nicht sofort offensichtlich ist – zum Beispiel bei der Routenplanung, bei Spielen wie Schach oder bei der Navigation in sozialen Netzwerken. In diesem Tutorial lernst du die wichtigsten Suchstrategien kennen und setzt sie in Python um. Dabei orientieren wir uns an einem klassischen Assignment der Georgia Tech: CS6601 Assignment 1 – Search. Stell dir vor, du planst eine Reise durch Rumänien und willst die kürzeste Route zwischen zwei Städten finden. Genau das machen wir – mit Code.

Warum Suchalgorithmen wichtig sind

Suchalgorithmen sind überall. Ob du eine Route mit Google Maps planst, einen Zug in einer KI-Umgebung steuerst oder den nächsten Zug in einem Spiel berechnest – ohne Suche läuft nichts. Sie helfen dabei, den Lösungsraum effizient zu durchsuchen, ohne alle Möglichkeiten durchprobieren zu müssen. In der KI-Kurslandschaft sind sie der erste Schritt zu komplexeren Themen wie Planen, Spielen und maschinellem Lernen.

Setup deiner Entwicklungsumgebung

Bevor wir loslegen, brauchst du eine saubere Umgebung. Wir empfehlen einen virtuellen Conda-Container. So geht's:

Erstelle eine Conda-Umgebung: conda create –name a1_env python=3.9 -y
Aktiviere sie: conda activate a1_env
Installiere die Abhängigkeiten: pip install -r requirements.txt

Diese Schritte stellen sicher, dass alle Bibliotheken in der richtigen Version vorliegen. Falls du schon andere Umgebungen hast, liste sie mit conda env list auf.

Arbeiten mit Jupyter Notebook

Jupyter Notebooks sind ideal für interaktives Arbeiten. Starte dein Notebook mit jupyter notebook im Terminal. Öffne dann die Datei notebook.ipynb. Wichtig: Führe immer alle Zellen aus, von denen ein Zell abhängt – am besten mit „Run All“. Sonst kann es zu unerwarteten Fehlern kommen. Das ist eine häufige Fehlerquelle, wenn man zwischen den Sessions wechselt.

Die Romania-Karte als Testumgebung

Wir arbeiten mit einem ungerichteten Graphen, der die Städte Rumäniens und ihre Verbindungen darstellt. Jede Kante hat eine Kosten (z.B. Entfernung in km). Ziel ist es, einen Pfad von A nach B zu finden, der die Gesamtkosten minimiert. Optional gibt es einen Atlanta-Graphen für zusätzliche Tests.

Wichtige Suchalgorithmen

Breitensuche (BFS)

BFS erkundet den Graphen Ebene für Ebene. Sie garantiert den kürzesten Pfad in ungewichteten Graphen. Für unseren Romania-Graphen ist sie nützlich, wenn alle Kanten gleiche Kosten haben – was hier nicht der Fall ist, aber als Basisalgorithmus wichtig.

Tiefensuche (DFS)

DFS geht in die Tiefe, bevor sie zurückgeht. Sie findet schnell einen Pfad, aber nicht unbedingt den kürzesten. In der Praxis wird sie oft für Probleme mit großem Suchraum eingesetzt, z.B. in der Spiel-KI.

Uniform Cost Search (UCS)

UCS erweitert BFS auf gewichtete Graphen. Sie wählt immer den Knoten mit den geringsten Gesamtkosten aus. Das ist perfekt für unsere Romania-Karte, denn hier zählt die tatsächliche Entfernung.

A*-Suche

A* kombiniert UCS mit einer Heuristik, die die verbleibenden Kosten schätzt. So wird der Suchraum effizienter durchsucht. Eine gute Heuristik ist z.B. die Luftlinie zwischen zwei Städten. A* ist der Star unter den Suchalgorithmen – schnell und optimal, wenn die Heuristik zulässig ist.

Praktische Umsetzung in Python

Hier ein Auszug, wie du eine generische Suchfunktion aufbaust:

def search(graph, start, goal, strategy):
    frontier = [(0, start)]  # Prioritätswarteschlange
    explored = set()
    parent = {start: None}
    cost_so_far = {start: 0}

    while frontier:
        current_cost, current_node = heappop(frontier)
        if current_node == goal:
            return reconstruct_path(parent, start, goal)
        explored.add(current_node)
        for neighbor, weight in graph[current_node].items():
            new_cost = cost_so_far[current_node] + weight
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic(neighbor, goal) if strategy == 'astar' else new_cost
                heappush(frontier, (priority, neighbor))
                parent[neighbor] = current_node
    return None

Dieser Code implementiert sowohl UCS als auch A*, je nachdem, ob du eine Heuristik übergibst. Für BFS und DFS müsstest du die Prioritätswarteschlange durch eine FIFO-Queue oder einen Stack ersetzen.

Trends und Analogien: Suchalgorithmen im Alltag

Suchalgorithmen sind heute aktueller denn je. Denk an die Routenplanung in Google Maps: Jeden Tag berechnen Millionen Menschen die schnellste Strecke – das ist im Kern A*. Auch in der Spieleentwicklung, z.B. bei der KI in „The Legend of Zelda: Tears of the Kingdom“, laufen ständig Suchalgorithmen, um Gegner zu dir zu navigieren. Und selbst in sozialen Netzwerken wie TikTok wird gesucht: Der Algorithmus sucht nach dem nächsten Video, das dich fesselt – allerdings mit anderen Methoden wie Reinforcement Learning.

Aktuell (Mai 2026) ist ein großer Trend die Integration von KI in Smart-Home-Geräte. Stell dir vor, dein Staubsaugerroboter sucht den effizientesten Weg durchs Wohnzimmer – auch das ist ein Suchproblem. Oder in der Logistik: Amazon sucht den kürzesten Weg für Pakete in riesigen Lagern. Ohne Suchalgorithmen wäre das unmöglich.

Testen und Debuggen

Zum Testen stehen dir mehrere Skripte zur Verfügung:

search_basic_tests.py: Einfache Tests mit Visualisierung des Romania-Graphen.
search_submission_tests_grid.py: Visualisierung als Gitter.
search_romania_tests.py: Umfassende Tests für Rumänien.
search_atlanta_tests.py: Tests für den Atlanta-Graphen.
search_case_visualizer.py: Visualisierung fehlgeschlagener Fälle.

Führe sie mit python search_romania_tests.py aus. Für einen einzelnen Test: python search_romania_tests.py SearchRomaniaTests.test_bfs_romania.

Häufige Fehler und Tipps

Jupyter startet nicht: Aktiviere deine Conda-Umgebung und starte Jupyter von dort.
Variablen unerwartet: Führe alle abhängigen Zellen aus – „Run All“ hilft.
Heuristik nicht zulässig: A* funktioniert nur optimal, wenn die Heuristik die Kosten nie überschätzt. Nutze die Luftlinie als sichere Wahl.

Fazit

Suchalgorithmen sind ein unverzichtbares Werkzeug für jeden KI-Entwickler. Mit diesem Tutorial hast du die Grundlagen verstanden und kannst sie in Python umsetzen. Egal ob für dein Studium, für ein Projekt oder einfach aus Neugier – die Konzepte von BFS, DFS, UCS und A* begleiten dich durch die Welt der KI. Viel Erfolg bei deinem Assignment!