| Autor |
Beitrag |
malibu85
      
Beiträge: 51
|
Verfasst: So 26.10.08 19:44
Hallo Leute ich möchte in einem Vortrag etws über Problemlösen erzählen. Dabei mache ich einen kleinen Exkurs zu den algorithmen. Ich habe mir dazu überlegt ein Labyrinth als beispiel zu nehmen und möchte die Studenten fragen ob ihnen ein algorithmus einfällt der auf alle fälle zur lösung führt egal wie das Labyrinth aussieht und ohne dass sie mit dem auge den richtigen weg suchen. Als Lösung wollte ich den folgenden Algorithmus angeben:
gehe den weg entlang;
wenn du auf eine Gabelung triffst, dann wähle immer den rechten weg;
wenn du auf eine Sackgasse triffst, drehe um;
dadurch, dass rechts und links vertauscht sind wenn man einen weg zurück geht, sollten alle möglichkeiten durchgespielt werden bis man ans ziel kommt ohne in eine endlosschleife zu kommen.
Was sagt ihr dazu? Ist dieser algorithmus allgemeingültig?
|
|
Jakob_Ullmann
      
Beiträge: 1747
Erhaltene Danke: 15
Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
|
Verfasst: So 26.10.08 19:59
Ich würde sagen: ja. Klingt logisch und mir ist auch kein Labyrinth eingefallen, für das der Algorithmus nicht zutrifft. 
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: So 26.10.08 20:11
Es gibt einen noch einfacheren Algorithmus:
Immer an der linken Wand endlang (in Laufrichtung).
Das ist konzeptionell das Gleiche, aber etwas kürzer.
Zur Erklärung:
Wenn Du Dich immer an der linken (oder rechten) Wand endlang tastest, wirst Du zwangsläufig auch links abbiegen.
Wenn Du dann an eine Sackgasse kommst, drehst Du dich ja zwangsläufig (immer an der linken Wand endlang tastend) und läufst zurück.
Man kann auch beweisen, das dies in einem Labyrinth immer zum Ziel führt. Ein Labyrinth enthält übrigens keine Kreise, Geheimgänge, Warp-Tore etc.
_________________ Na denn, dann. Bis dann, denn.
|
|
Hidden
      
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: So 26.10.08 20:38
Hi,
Auch mit Warp-Toren führt er zum Ziel, da das praktisch ein Ausgang ist. Dann kommt halt ein weiteres labyrinth, das sich genauso lösen lässt.
Aber du wolltest vermutlich auch eher auf die Definition zurück
Allgemein kann man sagen: Er führt dann zum Ziel, wenn der AUsgang des Labyrinths auf seinem Rand liegt(Was nach der Def der Fall ist).
mfG,
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
der organist
      
Beiträge: 467
Erhaltene Danke: 17
WIN 7
NQC, Basic, Delphi 2010
|
Verfasst: So 26.10.08 21:39
alzaimar hat folgendes geschrieben : | Es gibt einen noch einfacheren Algorithmus:
Immer an der linken Wand endlang (in Laufrichtung).
Das ist konzeptionell das Gleiche, aber etwas kürzer.
Zur Erklärung:
Wenn Du Dich immer an der linken (oder rechten) Wand endlang tastest, wirst Du zwangsläufig auch links abbiegen.
Wenn Du dann an eine Sackgasse kommst, drehst Du dich ja zwangsläufig (immer an der linken Wand endlang tastend) und läufst zurück.
Man kann auch beweisen, das dies in einem Labyrinth immer zum Ziel führt. Ein Labyrinth enthält übrigens keine Kreise, Geheimgänge, Warp-Tore etc. |
Um genau zu sein, redet ihr über einen Irrgarten. Labyrinthe sehen so aus: de.wikipedia.org/wiki/Labyrinth
Irrgärten: de.wikipedia.org/wiki/Irrgarten
Mich würde aber mal interessieren, warum der Linke Algorithmus schneller sein soll, ich meine, der Ausgang ist doch zufällig. Sie könnten auch genau gleich lang sein...
_________________ »Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin
|
|
Jakob_Ullmann
      
Beiträge: 1747
Erhaltene Danke: 15
Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
|
Verfasst: So 26.10.08 21:43
Laut Definition ist doch ein Irrgarten auch ein Labyrinth. Außerdem dürfte der Algorithmus doch für beides stimmen.
|
|
jasocul
      
Beiträge: 6395
Erhaltene Danke: 149
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Mo 27.10.08 09:15
Immer diese 2D-Denker. Was macht ihr in einem 3-dimensionalem Labyrinth?
Der Wechsel zwischen den Ebenen (Keller, Obergeschoss, etc.) muss nicht am Rand liegen und kann somit nach diesem Verfahren unerreichbar sein. Ist der Ausgang dann auf einer anderen Ebene, findet man höchstens wieder zum Eingang. Aber auch das nur, wenn dieser ebenfalls am Rand liegt.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 27.10.08 09:30
Der Algorithmus funktioniert für alle Labyrinthe und Irrgärten, die keinen Kreis definieren.
jasocul, dieser Simpel-Algorithmus soll eigentlich nur veranschaulichen, mit welch einfachen Mitteln man so ein an sich komplexes Problem "Finde den Weg durch das Labyrinth" lösen kann.
Algorithmisch würde ich das Labyrinth als ungerichteten Graph ansehen und dort einen 2-Pairs-Shortest-Path-Algorithmus ansetzen.
_________________ Na denn, dann. Bis dann, denn.
|
|
jasocul
      
Beiträge: 6395
Erhaltene Danke: 149
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Mo 27.10.08 09:49
alzaimar hat folgendes geschrieben : | | jasocul, dieser Simpel-Algorithmus soll eigentlich nur veranschaulichen, mit welch einfachen Mitteln man so ein an sich komplexes Problem "Finde den Weg durch das Labyrinth" lösen kann. |
Ich nutze dieses Verfahren schon viele Jahre, um durch Labyrinthe in Computer-Spielen zu gelangen. Bis ich dann auf eines gestoßen bin, dass irgendwo mittendrin die Ebene gewechselt hat. Deswegen meine Anmerkung.
|
|
Jakob_Ullmann
      
Beiträge: 1747
Erhaltene Danke: 15
Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
|
Verfasst: Mo 27.10.08 11:00
jasocul hat folgendes geschrieben : | | Ich nutze dieses Verfahren schon viele Jahre, um durch Labyrinthe in Computer-Spielen zu gelangen. Bis ich dann auf eines gestoßen bin, dass irgendwo mittendrin die Ebene gewechselt hat. Deswegen meine Anmerkung. |
Ja, aber der Algo dient ja nur zu Demonstrationszwecken. Außerdem gilt er nur, wenn Ein- und Ausgang am Rand liegen.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 27.10.08 11:19
Jakob_Ullmann hat folgendes geschrieben : | | Außerdem gilt er nur, wenn Ein- und Ausgang am Rand liegen. |
Nein! Er gilt immer dann, wenn es keine Kreise im Labyrinth gibt. Oder anders ausgedrückt: Wenn das Labyrinth so konstruiert ist, das man mit einem Stift an der Wand ohne Abzusetzen entlang fahren kann und irgendwann alle Wände angepinselt hat.
_________________ Na denn, dann. Bis dann, denn.
|
|
elundril
      
Beiträge: 3747
Erhaltene Danke: 123
Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
|
Verfasst: Mo 27.10.08 11:37
Ich denke in diesem Topic ist es angebracht auf die Folien des Prologs an der TU Wien für Algorithmen und Datenstrukturen zu verweisen.
Hier mal der Link dazu:
www.informatik.tuwie...um/prolog/index.html
insbesondere auf das Programm Theseus will ich aufmerksam machen, da dieser ein Labyrinth mit diversen methoden "durchsucht" (Tiefensuche, Breitensuche, Rechte Wand methode,...)
lg elundril
_________________ This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.
|
|
|