| Der Maze-Running-Algorithmus - wir "sausen" also durch den Irrgarten - aber wie machen wir das effizient??? |
|
|
Letztmalig dran rumgefummelt: 30.01.25 03:21:05 |
 |
In der Informatik geht es genauso wenig um Computer wie in der Astronomie um Teleskope. Diese Aussage des niederländischen Informatikers Edsger W. Dijkstra 1930 – 2002 irritiert viele Menschen erst einmal, aber Informatik ist viel mehr als nur die Erstellung von Software, also dem Programmieren. | ||||||
 |
1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung und Übung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen |
||||||
|
|
||||||
 |
Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff. |
| 1. Problembeschreibung |
|
|
 |
|
Labyrinth oder Irrgarten? Das Labyrinth (gleich welcher Art) ist dabei die einfache Variante - es geht immer vorwärts (nur, wenn ich anfangs die falsche Richtung gewählt habe, komme ich ans Ende und muss umkehren). Der Weg kann sehr lang sein, ist jedoch eindeutig und endlich. Das ist auch bei einem Irrgarten so, aber da es Möglichkeiten gibt, ist es fraglich, ob ich in der verfügbaren Zeit den richtigen (da reden wir noch nicht einmal vom kürzesten!) Weg auch finden kann (sofern er überhaupt existiert!). | ||||||||||||
|
|
||||||||||||
|
|
||||||||||||
|
|
| 2. Hintergründe, Zusammenhänge - Einordnung in Klassen |
|
|
|
|
|
Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten. | ||||||||
|
|
||||||||
|
| 3. Lösungsalgorithmus |
|
|
|
|
|
Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt). | ||||||
|
|
| 4. Programmvorschläge |
|
|
|
|
|
Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen. | ||||||
|
|
||||||
|
Maze-Running-Algorithmus nach Jannick Mitsch im Schuljahr 2018/19 |
||||||
| 5. Zusammenfassung und Übungen |
|
|
|
|
|
Lösungsalgorithmen für Irrgärten
beschreiben Methoden, mit denen automatisiert ein Weg aus einem Irrgarten
gefunden werden kann. Dabei gibt es Algorithmen, die einer in einem
Irrgarten gefangenen Person ins Freie helfen können, ohne dass sie etwas
über den Irrgarten weiß: die zufällige Wegwahl, die Rechte-Hand-Methode, der
Pledge-Algorithmus und der Trémaux-Algorithmus. Dagegen setzen Algorithmen
wie das Auffüllen von Sackgassen oder das Finden des kürzesten Auswegs
voraus, dass der Irrgarten als Ganzes überblickt werden kann. Irrgärten, in denen man nicht im Kreis gehen kann, werden auch als Standard- oder perfekte Irrgärten bezeichnet. Diese sind äquivalent zu einem Baum in der Graphentheorie. Dies wird intuitiv klar, wenn man sich vorstellt, dass man die Wege eines perfekten Irrgartens geradebiegt. Macht man dies in der richtigen Weise, so sieht das Ergebnis einem Baum sehr ähnlich. Daher spielt die Graphentheorie auch eine große Rolle bei den Lösungsalgorithmen für Irrgärten. |
|||||||||||||||
|
|
|||||||||||||||
|
|
|||||||||||||||
| 6. Weiterführende Literatur |
|
|
|
|
|
|
|
|
|
|
|
| 7. Links zum Thema |
|
|
|
|
|
|
|
http://www.mathematische-basteleien.de/kaprekarzahl.htm |
|
| 8. Verwandte Themen |
|
|
|
|
|
Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft. | ||||||||||||||||||||||||
|
|
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||
|
|
 zur Hauptseite |
© Samuel-von-Pufendorf-Gymnasium Flöha | © Frank Rost im Dezember 2007 |
|
... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-) „Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“ Diddi Hallervorden, dt. Komiker und Kabarettist |
|
Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-) |
als CorelDraw
11.0-Datei zum Download
Projekt-Materialien
Projekt-Materialien
