Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- ef:algorithmen:start [2025/11/13 15:32] – lehmannr
+++ ef:algorithmen:start [2025/11/19 16:27] (aktuell) – lehmannr
@@ Zeile 2: / Zeile 2: @@
 Ein Labyrinth kann man durch einen Graphen darstellen. Ein sogenanntes "perfektes Labyrinth" wird dabei durch einen Baum dargestellt. Allgemeinerer Labyrinthe (die nicht "perfekt" sind), können durch Graphen repräsentiert werden.
+<WRAP nicebox green>
+** Aufgabe 1 **
+  - Wie funktioniert der Algorithmus Randomized Depth First Search (DFS), um ein Labyrinth zu erstellen? Erkläre.
+  - Wozu benötigt man einen Stack, um den DFS zu implementieren.
+  - Finde zu einem gegebenen Labyrinth den zugehörigen Graphen und umgekehrt (vgl. Arbeitsblatt).
+</WRAP>
 ======= 2. Pfadfinder-Algorithmen =======
 Betrachte die Aufgabe zum Programmierwettbewerb Hidden-Gems: [[https://hiddengems.gymnasiumsteglitz.de/]]
 Bei "Stages" siehst du den einfachsten Testlevel und die Informationen, die man erhält.
+Es gibt etliche Algorithmen, welche einen Pfad von einem Startpunkt zum Ziel finden sollen. Diese funktionieren sowohl bei Wegen mit Hindernissen, als auch bei Labyrinthen.
+===== 2.1 Labyrinthe lösen =====
+<WRAP nicebox green>
+**Aufgabe 2**
+  - Wie funktioniert der Random-Mouse Algorithmus?
+  - Wie funktioniert der "Hand on wall"-Algorithmus? Für welche Labyrinthe funktioniert er sicher?
+  - Wie funktioniert der DFS-Algorithmus um den Pfad in einem Labyrinth zu finden? Produziert er den kürzesten Weg?
+  - Wie funktioniert der BFS-Algorithmus um den Pfad in einem Labyrinth zu finden? Produziert er den kürzesten Weg?
+</WRAP>
+===== 2.2 Andere Pfad-Finder-Algorithmen =====
 <WRAP nicebox green>
-** Aufgabe **
+** Aufgabe 3**
-  - Überlege dir, welchen Algorithmus man bei der Testumgebung verwenden könnte? Wie steuert man den Bot zu den Edelsteinen?
+  - Wie funktioniert der Dijkstra-Algorithmus, um den schnellsten Weg zu finden? Funktioniert er für gerichtete und ungerichtete Graphen? Funktioniert er für gewichtete Graphen? [[https://www.youtube.com/watch?v=GazC3A4OQTE|Dijkstra Computerphile]]. Führe den Dijkstra-Algorithmus durch für das Beispiel in OneNote.
-  - Was ändert sich, wenn man sich in einer Umgebung mit Wänden bewegt? Wie wird die Umgebung, die Position des Bots und der Edelsteine repräsentiert?
+  - Wie funktioniert A*? Erkläre ihn. Recherchiere nach bekannten Pfadfinder-Algorithmen. [[https://youtu.be/-L-WgKMFuhE?si=I7kuQFjTcYBDQRN7|Sebastian Lague A*]]
-  - Überlege dir einen möglichen Algorithmus, der auch bei Wänden funktionieren könnte. Schreibe den exakten Ablauf deines Algorithmus schriftlich hin.
-  - Recherchiere nach bekannten Pfadfinder-Algorithmen. Was ist die Manhatten-Distanz? (BFS, DFS, Dijkstra, A*)(Bsp: [[https://www.youtube.com/watch?v=9W8hNdEUFbc|Englisches Video mit Visualisierung]])
   - Eine gute visuelle Darstellung von verschiedenen Algorithmen findet sich z.B. hier: [[https://clementmihailescu.github.io/Pathfinding-Visualizer/#]]
-  - Erklärung zur Breitensuche: [[https://de.khanacademy.org/computing/computer-science/algorithms/breadth-first-search/a/the-breadth-first-search-algorithm|Breitensuche in Khan-Academy]]
-  - Erklärung des Dijkstras-Algorithmus [[https://www.youtube.com/watch?v=GazC3A4OQTE|Dijkstra Computerphile]]
 </WRAP>
-  - Wie funktioniert die Breitensuche?
-  - Was ist eine Queue und wie verwendet man sie, wenn man die Breitensuche implementiert? (Siehe Link von Khan-Academy)
+main.py
 <sxh>
 # main.py
@@ Zeile 122: / Zeile 134: @@
 root.mainloop()
 </sxh>
+cell.py
+<sxh>
+import random
+class Cell:
+    def __init__(self, x, y, size, col="white"):
+        self.x = x                # X-Koordinate
+        self.y = y                # Y-Koordinate
+        self.size = size          # Breite/Höhe der Zelle
+        self.walls = [True, True, True, True]  # [oben, rechts, unten, links]
+        self.col = col            # Farbe der Zelle
+        self.visited = False      # Besuchsstatus
+    def highlight(self, can, col):
+        x1 = self.x * self.size+8
+        y1 = self.y * self.size+8
+        x2 = x1 + self.size-10
+        y2 = y1 + self.size-10
+        can.create_rectangle(x1, y1, x2, y2, fill=col, outline="")
+    def draw(self, can): # Zeichnet die Zelle auf dem übergebenen Canvas.
+        x1 = self.x * self.size+4  # +4, damit der linke bzw. obere Rand nicht abgeschnitten werden
+        y1 = self.y * self.size+4
+        x2 = x1 + self.size+4
+        y2 = y1 + self.size+4
+        # Hintergrundfarbe
+        if self.visited:
+            can.create_rectangle(x1, y1, x2, y2, fill=self.col, outline="")
+        else:
+            can.create_rectangle(x1, y1, x2, y2, fill="lightyellow", outline="")
+        # Wände zeichnen
+        if (self.walls[0]):  # oben
+            can.create_line(x1, y1, x2, y1, fill="black", width=4)
+        if self.walls[1]:  # rechts
+            can.create_line(x2, y1, x2, y2, fill="black", width=4)
+        if self.walls[2]:  # unten
+            can.create_line(x2, y2, x1, y2, fill="black", width=4)
+        if self.walls[3]:  # links
+            can.create_line(x1, y2, x1, y1, fill="black", width=4)
+    def checkNeighbors(self, cells, rows, cols):
+        neighbors = []
+        topIndex = Cell.get_index(self.x, self.y-1, rows, cols)
+        rightIndex = Cell.get_index(self.x+1, self.y, rows, cols)
+        bottomIndex = Cell.get_index(self.x, self.y+1, rows, cols)
+        leftIndex = Cell.get_index(self.x-1, self.y, rows, cols)
+        #top = cells[Cell.get_index(self.x, self.y-1, rows, cols)]
+        #right = cells[Cell.get_index(self.x+1, self.y, rows, cols)]
+        #bottom = cells[Cell.get_index(self.x, self.y+1, rows, cols)]
+        #left = cells[Cell.get_index(self.x-1, self.y, rows, cols)]
+        if (topIndex and (not cells[topIndex].visited)):
+            neighbors.append(cells[topIndex])
+        if (rightIndex and (not cells[rightIndex].visited)):
+            neighbors.append(cells[rightIndex])
+        if (bottomIndex and (not cells[bottomIndex].visited)):
+            neighbors.append(cells[bottomIndex])
+        if (leftIndex and (not cells[leftIndex].visited)):
+            neighbors.append(cells[leftIndex])
+        if neighbors:
+            return random.choice(neighbors)
+        else:
+            return None
+    @classmethod
+    def get_index(cls, i, j, rows, cols):
+        if (i<0 or j<0 or i>=cols or j >= rows):
+            return None
+        else:
+            return j*rows + i
+</sxh>