Suchalgorithmen in der KI: CS6601 Assignment 1 Tutorial (Frühjahr 2025)

Einführung in Suchalgorithmen für CS6601 Assignment 1 (Frühjahr 2025)

Suchalgorithmen sind das Herzstück der Künstlichen Intelligenz. Sie helfen dabei, Probleme zu lösen, bei denen die Lösung nicht sofort ersichtlich ist – sei es die Routenplanung in einer Karte, das Lösen eines Puzzles oder die Optimierung von Lieferketten. In CS6601 Assignment 1 aus dem Frühjahr 2025 geht es genau darum: Implementiere verschiedene Suchalgorithmen, um die kürzeste Route zwischen zwei Punkten in Rumänien zu finden. Dabei sollen sowohl Zeit- als auch Speicherkosten minimiert werden. Dieses Tutorial führt dich durch die wichtigsten Konzepte und gibt dir praktische Tipps, um die Aufgabe erfolgreich zu meistern.

Warum Suchalgorithmen wichtig sind: Von Rumänien bis zu KI-Trends 2026

Stell dir vor, du planst eine Reise durch Rumänien – von Arad nach Bukarest. Oder du entwickelst eine KI für ein autonomes Fahrzeug, das in Echtzeit den besten Weg durch den Verkehr findet. Suchalgorithmen sind überall: in Navigations-Apps, in Spielen wie StarCraft (wo Einheiten den kürzesten Weg suchen), in sozialen Netzwerken (um Freunde zu finden) und sogar in der Genomik. Auch aktuelle Trends wie KI-gestützte Routenplanung für Drohnenlieferungen oder Algorithmen für Echtzeit-Strategiespiele bauen auf denselben Prinzipien auf. Mit diesem Wissen bist du bestens gerüstet für die Zukunft.

Setup und Abhängigkeiten: So startest du dein Projekt

Bevor du loslegst, musst du die richtige Umgebung einrichten. Folge diesen Schritten:

Conda-Umgebung erstellen: conda create –name a1_env python=3.9 -y
Umgebung aktivieren: conda activate a1_env
Abhängigkeiten installieren: pip install -r requirements.txt

Die requirements.txt enthält alle benötigten Bibliotheken wie numpy, matplotlib und networkx. Mit diesen Werkzeugen kannst du den Rumänien-Graphen visualisieren und deine Algorithmen testen.

Jupyter Notebook: Deine interaktive Entwicklungsumgebung

Das Assignment wird in einem Jupyter Notebook bearbeitet. Starte es mit jupyter notebook und öffne die Datei notebook.ipynb. Hier sind einige Tipps:

Kernel-Probleme: Stelle sicher, dass deine Conda-Umgebung aktiviert ist, bevor du Jupyter startest.
Zellenreihenfolge: Führe immer alle Zellen aus, von denen eine Zelle abhängt – auch wenn sie nicht direkt davor stehen. Nutze „Run All“ im Menü.
Variablenwerte: Wenn ein Wert unerwartet ist, überprüfe, ob du die richtigen Zellen in der richtigen Reihenfolge ausgeführt hast.

Die Rumänien-Karte: Ein ungerichteter Graph

Die Basis für alle Aufgaben ist ein ungerichteter Graph der Städte Rumäniens. Jede Stadt ist ein Knoten, jede Straße eine Kante mit einer Gewichtung (Entfernung). Du wirst Algorithmen implementieren, die den kürzesten Weg von einem Start- zu einem Zielknoten finden. Der Graph ist im Modul romania_graph.py definiert.

Implementierung der Suchalgorithmen

1. Breitensuche (BFS)

BFS erkundet den Graphen Ebene für Ebene. Es garantiert den kürzesten Weg in ungewichteten Graphen. Für die Rumänien-Karte (mit Gewichten) ist BFS nicht optimal, aber ein guter Einstieg.

def bfs(graph, start, goal):
    visited = set()
    queue = deque([(start, [start])])
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in graph.neighbors(node):
                queue.append((neighbor, path + [neighbor]))
    return None

2. Tiefensuche (DFS)

DFS geht so tief wie möglich, bevor es zurückkehrt. Es findet nicht unbedingt den kürzesten Weg, ist aber speichereffizient.

def dfs(graph, start, goal):
    visited = set()
    stack = [(start, [start])]
    while stack:
        node, path = stack.pop()
        if node == goal:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in graph.neighbors(node):
                stack.append((neighbor, path + [neighbor]))
    return None

3. A*-Suche

A* ist der Star unter den Suchalgorithmen. Es kombiniert die Kosten des bisherigen Weges (g) mit einer Heuristik (h), die die geschätzten Kosten bis zum Ziel schätzt. Für die Rumänien-Karte verwendest du die Luftlinienentfernung als Heuristik.

def a_star(graph, start, goal, heuristic):
    open_set = [(0, start, [start])]
    g_score = {node: float('inf') for node in graph.nodes}
    g_score[start] = 0
    while open_set:
        _, current, path = heapq.heappop(open_set)
        if current == goal:
            return path
        for neighbor in graph.neighbors(current):
            tentative_g = g_score[current] + graph.edges[current][neighbor]['weight']
            if tentative_g < g_score[neighbor]:
                g_score[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score, neighbor, path + [neighbor]))
    return None

4. IDA* (Iterative Deepening A*)

IDA* kombiniert die Speichereffizienz von DFS mit der Optimalität von A*. Es verwendet eine Tiefenbeschränkung, die auf dem f-Wert basiert.

def ida_star(graph, start, goal, heuristic):
    bound = heuristic(start, goal)
    path = [start]
    while True:
        t = search(path, 0, bound, graph, goal, heuristic)
        if t == 'FOUND':
            return path
        if t == float('inf'):
            return None
        bound = t

def search(path, g, bound, graph, goal, heuristic):
    node = path[-1]
    f = g + heuristic(node, goal)
    if f > bound:
        return f
    if node == goal:
        return 'FOUND'
    min_cost = float('inf')
    for neighbor in graph.neighbors(node):
        if neighbor not in path:
            path.append(neighbor)
            t = search(path, g + graph.edges[node][neighbor]['weight'], bound, graph, goal, heuristic)
            if t == 'FOUND':
                return 'FOUND'
            if t < min_cost:
                min_cost = t
            path.pop()
    return min_cost

Tests und Abgabe

Um deine Implementierung zu überprüfen, stehen mehrere Testdateien zur Verfügung:

search_basic_tests.py: Einfache Tests mit Visualisierung des Rumänien-Graphen.
search_romania_tests.py: Umfassende Tests für den Rumänien-Graphen.
search_atlanta_tests.py: Tests für den optionalen Atlanta-Graphen (für die „Race“-Aufgabe).
search_submission_tests_grid.py: Visualisierung als Gitter.
search_case_visualizer.py: Visualisierung fehlgeschlagener Testfälle.

Führe die Tests mit python search_romania_tests.py aus. Für einen einzelnen Test: python search_romania_tests.py SearchRomaniaTests.test_bfs_romania. Nach bestandenen Tests reichst du die Dateien aus dem submission-Verzeichnis auf Gradescope ein.

Trends und Beispiele aus der Praxis

Suchalgorithmen sind nicht nur für Rumänien relevant. Im Jahr 2026 nutzen KI-Systeme ähnliche Verfahren für:

Autonome Fahrzeuge: A* wird in Echtzeit-Navigationssystemen verwendet.
Spiele-KI: In League of Legends oder Fortnite suchen NPCs mit BFS/DFS nach dem Spieler.
Logistik: Lieferdienste optimieren Routen mit A* und IDA*.
Soziale Netzwerke: Facebook verwendet BFS, um Freundesvorschläge zu machen.

Diese Beispiele zeigen, wie mächtig Suchalgorithmen sind – und wie du sie in deiner Karriere einsetzen kannst.

Häufige Fehler und Lösungen

Vergessene Heuristik: A* benötigt eine zulässige Heuristik. Verwende die Euklidische Distanz für Rumänien.
Endlosschleifen: Stelle sicher, dass du besuchte Knoten in BFS/DFS markierst.
Falsche Reihenfolge: Bei IDA* muss die Tiefenbeschränkung korrekt aktualisiert werden.

Fazit

Mit diesem Tutorial hast du einen soliden Überblick über die Suchalgorithmen für CS6601 Assignment 1 (Frühjahr 2025). Übe die Implementierung, führe die Tests durch und passe die Algorithmen bei Bedarf an. Denke daran: Suchalgorithmen sind ein grundlegendes Werkzeug der KI – und mit diesem Wissen bist du bereit für komplexere Herausforderungen. Viel Erfolg!