Algorithmus von Tremaux, seltsame Versionen

14/04/2009 - 19:51 von Detlef Müller | Report spam
Hallo,

Ein frustrierter Student hat einen Zettel in der Uni
ausgehàngt mit folgendem Labyrinth:

######### #########
######### #########
######### #########
### ############### #######
#S# ############### #####Z#
### ############### #######
######### #########
######### #########
######### #########

Der Algorithmus von Tremaux soll hier nicht funktionieren
um von S nach Z zu kommen.

Das habe ich mir mal angesehen: Der Algorithmus, wie man
ihn hier und dort im Netz beschrieben sieht, geht so:

1.
Gehe einen beliebigen Weg und markiere ihn dabei, bevorzuge
unmarkierte Wege.

2.
Hast Du irgendwann keinen unmarkierten Weg mehr frei, so
gehe einen bereits einmal markierten und markiere ihn beim
durchlaufen ein weiteres mal, weiter bei 1.

Angeblich kommt man so entweder nach Z oder, wenn das nicht
möglich ist, endet man wieder in S und muß niemals einen Weg
mehr als zweimal beschreiten.

Einen Beweis konnte ich nicht auftreiben, aber offenbar reicht
das bis jetzt aufgeschriebene nicht, denn im Beispiel oben kann man von
S starten, den linken Kreis durchlaufen, dann nach rechts und den
rechten Kreis durchlaufen, ohne nach Z abzuzweigen und dann wieder
zum linken Kreis marschieren, von wo man nie mehr weg kommt.

Womöglich fehlt irgendeine Voraussetzung an das Labyrinth,
in diversen Beschreibungen wird jedenfalls explizit erwàhnt, daß
man in 2. die freie Wahl irgendeines einfach markierten Weges
hat (andere schreiben ein zurückgehen vor).
Etwa http://en.wikipedia.org/wiki/Maze_s..._algorithm schlàgt
nur unverbindlich vor, bei einer Sackgasse aus einfach markierten Wegen
umzukehren. In
http://de.wikipedia.org/wiki/Irrgar..._und_Tarry
wird explizit der Rückweg als eine von vielen Möglichkeiten in 2.
beschrieben. Dann ist aber die obige Situation offensichtlich ein
Gegenbeispiel.

Wenn man als Rückweg aus einer Sackgasse mit einfach markierten
Ausgàngen das direkte Umkehren vorschreibt, liegt oben kein
Gegenbeispiel mehr vor.
Sollte man den Wicki-Eintrag in der Richtung korrigieren oder
kann man die "freie" Wahl mit einer Voraussetzung an das Labyrinth
retten?
Der Algorithmus "ohne Umkehrzwang" ist mir an mehreren Stellen
untergekommen ... da kommen einem ja schon fast Zweifel ("Millionen
Fliegen können nicht irren:)") - seltsam bei so einem simplen
Gegenbeispiel.

Gruß,
Detlef

Dr. Detlef Müller, Weender Landstr. 80, 0551/35652, 01639641642,
http://mathe-doktor.de email: detlef.mueller@mathe-doktor.de
Steuernr. 2003015382
 

Lesen sie die antworten

#1 Stefan Kirchner
14/04/2009 - 22:27 | Warnen spam
On Tue, 14 Apr 2009, Detlef Müller wrote:

Hallo,

Ein frustrierter Student hat einen Zettel in der Uni
ausgehàngt mit folgendem Labyrinth:

######### #########
######### #########
######### #########
### ############### #######
#S# ############### #####Z#
### ############### #######
######### #########
######### #########
######### #########

Der Algorithmus von Tremaux soll hier nicht funktionieren
um von S nach Z zu kommen.

Das habe ich mir mal angesehen: Der Algorithmus, wie man
ihn hier und dort im Netz beschrieben sieht, geht so:

1.
Gehe einen beliebigen Weg und markiere ihn dabei, bevorzuge
unmarkierte Wege.

2.
Hast Du irgendwann keinen unmarkierten Weg mehr frei, so
gehe einen bereits einmal markierten und markiere ihn beim
durchlaufen ein weiteres mal, weiter bei 1.

Angeblich kommt man so entweder nach Z oder, wenn das nicht
möglich ist, endet man wieder in S und muß niemals einen Weg
mehr als zweimal beschreiten.

Einen Beweis konnte ich nicht auftreiben, aber offenbar reicht
das bis jetzt aufgeschriebene nicht, denn im Beispiel oben kann man von
S starten, den linken Kreis durchlaufen, dann nach rechts und den
rechten Kreis durchlaufen, ohne nach Z abzuzweigen und dann wieder
zum linken Kreis marschieren, von wo man nie mehr weg kommt.



In der Tat. Das könnte auch erklàren, warum Du keinen Beweis auftreiben
konntest.

Womöglich fehlt irgendeine Voraussetzung an das Labyrinth, in diversen
Beschreibungen wird jedenfalls explizit erwàhnt, daß man in 2. die freie
Wahl irgendeines einfach markierten Weges hat (andere schreiben ein
zurückgehen vor). Etwa
http://en.wikipedia.org/wiki/Maze_s..._algorithm schlàgt nur
unverbindlich vor, bei einer Sackgasse aus einfach markierten Wegen
umzukehren. In
http://de.wikipedia.org/wiki/Irrgar..._und_Tarry
wird explizit der Rückweg als eine von vielen Möglichkeiten in 2.
beschrieben. Dann ist aber die obige Situation offensichtlich ein
Gegenbeispiel.

Wenn man als Rückweg aus einer Sackgasse mit einfach markierten
Ausgàngen das direkte Umkehren vorschreibt, liegt oben kein
Gegenbeispiel mehr vor.



Wenn das direkte Umkehren verbindlich ist, hat man einen normalen
Tiefensuch-Algorithmus (depth-first search). Dieser findet natürlich einen
S-Z-Weg (sofern überhaupt einer existiert), und für dessen Korrektheit
gibt es natürlich auch Beweise, die nicht besonders schwer sind.

Sollte man den Wicki-Eintrag in der Richtung korrigieren oder
kann man die "freie" Wahl mit einer Voraussetzung an das Labyrinth
retten?
Der Algorithmus "ohne Umkehrzwang" ist mir an mehreren Stellen
untergekommen ... da kommen einem ja schon fast Zweifel ("Millionen
Fliegen können nicht irren:)") - seltsam bei so einem simplen
Gegenbeispiel.



Ich vermute, dass eine Charakterisierung, bei welchen Labyrinthen
(Graphen) die "freie" Wahl stets klappt, nicht einfach ist. Bei
kreisfreien Graphen funktioniert der Ansatz natürlich. Eventuell sind die
maximalen Zweifachzusammenhangskomponenten und der dazugehörige Blockgraph
interessant ( http://mathworld.wolfram.com/Block.html ).

Was die Wiki-Eintràge angeht: Korrigieren sollte man es auf jedenfall, in
der deutschen Wikipedia gibt es auf der Diskussionsseite bereits etwas zum
Trémaux-Verfahren, insbesondere einen Beweis durch Behauptung: "Nein,
nein, versagen tut die Methode nie!".


Viele Grüße
Stefan

Ähnliche fragen