Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- ef:algorithmen:start [2025/11/13 15:35] – 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
@@ Zeile 125: / Zeile 137: @@
 cell.py
+<sxh>
 import random
@@ Zeile 202: / Zeile 214: @@
         else:
             return j*rows + i
+</sxh>