Aufgaben PAI

Quiz: Grundlagen der Künstlichen Intelligenz

Grundlagen der KI

Frage 1 von 4

Welche Arten von AI-Agenten gibt es?

Python-Aufgaben: Grundlagen für Labyrinth-Navigation

Aufgabe 1: Koordinate eines Elements finden

Schreibe eine Funktion finde_koordinate(liste_2d, element), die die Koordinate (x, y) eines Elements in einer 2D-Liste zurückgibt. Wenn das Element nicht gefunden wird, soll None zurückgegeben werden.

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
koordinate = finde_koordinate(labyrinth, 'S')  # Sollte (1, 1) zurückgeben

Aufgabe 2: Element an Koordinate abrufen

Schreibe eine Funktion hole_element(liste_2d, x, y), die eine 2D-Liste, x- und y-Koordinaten bekommt und das Element an dieser Koordinate zurückgibt. Wenn die Koordinate außerhalb der Liste liegt, soll None zurückgegeben werden.

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
element = hole_element(labyrinth, 1, 1)  # Sollte 'S' zurückgeben

Aufgabe 3: Direkte Nachbarn finden

Schreibe eine Funktion finde_nachbarn(liste_2d, x, y), die die Koordinaten der direkten Nachbarn (Manhattan-Distanz = 1) einer Koordinate in einer 2D-Liste zurückgibt. Die Nachbarn sind die Zellen direkt oben, unten, links und rechts. Berücksichtige die Grenzen der Liste.

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
nachbarn = finde_nachbarn(labyrinth, 1, 1)  
# Sollte [(0, 1), (2, 1), (1, 0), (1, 2)] zurückgeben

Aufgabe 4: Nachbarn mit Kriterium finden

Schreibe eine Funktion finde_nachbarn_mit_kriterium(liste_2d, x, y, wert), die die Koordinaten der Nachbarn einer Koordinate zurückgibt, welche einem Kriterium entsprechen (gleich dem Parameter wert der Funktion sind).

Beispiel:

labyrinth = [
    [0, 0, 1],
    [0, 'S', 0],
    [1, 0, 'G']
]
freie_nachbarn = finde_nachbarn_mit_kriterium(labyrinth, 1, 1, 0)  
# Sollte [(0, 1), (2, 1), (1, 0), (1, 2)] zurückgeben (alle mit Wert 0)

Labyrinth-Aufgabe

Gegeben ist das folgende Labyrinth:

S . . . . .
. X X X . .
. . . . . .
. X X X . .
. . . . . G

Wobei:

• S = Start
• G = Ziel
• . = freier Weg
• X = Wand

Aufgaben:

1. Markiere den schnellsten Weg zum Ziel - Zeichne den kürzesten Pfad von S zu G ein.

2. Wie viele Wege findest du? - Zähle alle möglichen Wege von S zu G (ohne zurückzugehen).

3. Findest du eine Strategie, die immer funktioniert? - Beschreibe eine Suchstrategie, die garantiert einen Weg findet, wenn einer existiert. Welche Eigenschaften muss diese Strategie haben?

Türme von Hanoi

Gegeben sind die Türme von Hanoi mit 3 Scheiben. Die Scheiben sind unterschiedlich groß und müssen von Stab A nach Stab C bewegt werden, wobei:

• Nur eine Scheibe zur Zeit bewegt werden darf
• Nur die oberste Scheibe eines Stabes bewegt werden darf
• Eine größere Scheibe darf nie auf eine kleinere gelegt werden

Aufgabe:

Zeichne einen Baum/Graph, der alle möglichen Zustände zeigt, die beim Lösen des Problems mit 3 Scheiben erreicht werden können. Beginne mit dem Startzustand (alle Scheiben auf Stab A) und zeige, wie sich die Zustände verzweigen, bis das Ziel erreicht ist (alle Scheiben auf Stab C).

Tipp: Jeder Knoten im Graph repräsentiert einen Zustand (welche Scheiben sind auf welchem Stab). Jede Kante repräsentiert einen gültigen Zug.

Angeleitete Implementation: BFS (Breitensuche)

In dieser Aufgabe implementierst du Schritt für Schritt die Breitensuche (BFS) für ein Labyrinth.

Funktionssignatur:

def bfs(map, start_char, goal_char):
    # Gibt den Pfad von Start zu Ziel zurück (Liste von Koordinaten)
    # Falls kein Pfad gefunden wird, gibt None zurück
    pass

Map-Format: Die map ist eine 2D-Liste mit folgenden Werten:

• 0: freie Zelle
• 1: besetzte Zelle (Wand)
• "S": Start
• "A": Agent (optional)
• "G": Goal (Ziel)

BFS Implementation - Breitensuche

Schritt 1 von 9

Schritt 1: Queue-Klasse implementieren

Implementiere eine eigene Queue-Klasse für BFS. Eine Queue funktioniert nach dem FIFO-Prinzip (First In, First Out) - das erste Element, das hinzugefügt wird, wird auch als erstes entfernt. Erstelle eine Klasse Queue mit folgenden Methoden:

• init(self): Initialisiert eine leere Liste
• enqueue(self, element): Fügt ein Element am Ende hinzu
• dequeue(self): Entfernt und gibt das erste Element zurück
• is_empty(self): Gibt True zurück, wenn die Queue leer ist

Die Klasse sollte eine interne Liste self.items verwenden. Die Methode enqueue fügt am Ende hinzu (append), dequeue entfernt vom Anfang (pop(0)), und is_empty prüft ob die Liste leer ist.

Angeleitete Implementation: DFS (Tiefensuche)

In dieser Aufgabe implementierst du Schritt für Schritt die Tiefensuche (DFS) für ein Labyrinth. DFS funktioniert ähnlich wie BFS, verwendet aber einen Stack statt einer Queue.

Funktionssignatur:

def dfs(map, start_char, goal_char):
    # Gibt den Pfad von Start zu Ziel zurück (Liste von Koordinaten)
    # Falls kein Pfad gefunden wird, gibt None zurück
    pass

Map-Format: Die map ist eine 2D-Liste mit folgenden Werten:

• 0: freie Zelle
• 1: besetzte Zelle (Wand)
• "S": Start
• "A": Agent (optional)
• "G": Goal (Ziel)

DFS Implementation - Tiefensuche

Schritt 1 von 10

Schritt 1: Stack-Klasse implementieren

Implementiere eine eigene Stack-Klasse für DFS. Ein Stack funktioniert nach dem LIFO-Prinzip (Last In, First Out) - das letzte Element, das hinzugefügt wird, wird als erstes entfernt. Erstelle eine Klasse Stack mit folgenden Methoden:

• init(self): Initialisiert eine leere Liste
• push(self, element): Fügt ein Element am Ende hinzu
• pop(self): Entfernt und gibt das letzte Element zurück
• is_empty(self): Gibt True zurück, wenn der Stack leer ist

Die Klasse sollte eine interne Liste self.items verwenden. Die Methode push fügt am Ende hinzu (append), pop entfernt vom Ende (pop() ohne Index), und is_empty prüft ob die Liste leer ist.