Trémaux’ Methode

Trémaux’ Methode ist ein Algorithmus, der ein Passieren jedes Irrgartens oder, allgemeiner, labyrinthischen Wegesystems ohne Kenntnis eines Plans ermöglicht. Das Verfahren arbeitet mit Markierungen und ist für eine praktische Anwendung geeignet.

Geschichte

Der Algorithmus wurde von Charles Pierre Trémaux (1859–1882) entwickelt, der eine Ausbildung an der École polytechnique zum Telegraphen-Ingenieur absolvierte. Nach seinem frühen Tod nahmen sowohl der Mathematiker Gaston Tarry (1843–1913) als auch der Autor und Mathematiker Édouard Lucas (1842–1891) die Idee auf. Während Tarry versuchte, eine einzige „Fundamentalregel“ zu formulieren, gab Lucas in einer populären Sammlung mathematischer Spiele Trémaux’ ursprüngliche, bis dahin unveröffentlichte Regeln in verständlicher Form wieder.

Idee

Während Wegesysteme, die ausschließlich in Sackgassen verzweigen, auf einfache Weise mithilfe der „Rechten-Hand-Regel“ (wall follower method, „Folge-der-Mauer-Methode“) gelöst werden können, wurde ein System mit netzartiger Struktur als „unentrinnbar“ betrachtet, weil es die Gefahr eines unendlichen „Im-Kreis-Gehens“ barg. Bereits Leonhard Euler hatte sich mit dem Königsberger Brückenproblem einer verwandten Fragestellung gewidmet. Trémaux gelang es, die einzige immer anwendbare Methode zu entwickeln, die im schlechtesten Fall mit einem zweifachen Abgehen des Wegesystems auskam und ein dauerndes Irregehen ausschloss.

Arbeitsweise
Mögliche Verzweigungssituationen
Beispiel für das Trémaux’sche Verfahren – Animation (1 min 45 s)

Voraussetzungen

Das unbekannte Wegesystem wird als Graph aufgefasst. Dieser besteht aus Kanten und Knoten (Wege und Plätze; unter „Plätzen“ werden einfache Abzweigungen, Kreuzungen, aber auch beliebige Wegesterne verstanden). Ein Weg wird beim Betreten und Verlassen markiert, etwa durch einen Strich am Boden. Wege mit zwei Markierungen dürfen nicht mehr betreten werden.

Regeln
  • Gehe einen gewählten Weg immer bis zu dessen Ende.
    • Endet der Weg in einer Sackgasse, gehe an deren Anfang zurück. (Du wirst den Eingang zur Sackgasse dann mit einem zweiten Strich markieren und deshalb nicht wieder betreten.)
    • Mündet der Weg in einen Platz, analysiere den Platz.
      • Wurde der Platz noch nie betreten, wähle einen beliebigen der unbekannten Wege.
      • Ist der Platz bereits bekannt, analysiere den Weg, der zu dem Platz führte.
        • Wurde dieser Weg das erste Mal begangen, kehre um! (Du hast eine Schleife entdeckt und markierst das zuletzt begangene Teilstück an beiden Enden mit einem zweiten Strich, um zu verhindern, dass du hier künftig im Kreis gehst.)
        • Wurde der Weg jedoch bereits abgegangen, betrachte die Eingänge der anderen Wege. (Du verlässt einen Bereich, den du komplett abgesucht hast, und verschließt ihn mit einem zweiten Strich.)
          • Gibt es einen Weg, der noch nicht betreten wurde, wähle diesen. (Erforsche einen neuen Bereich des Labyrinths.)
          • Gibt es andernfalls einen Weg, der erst einmal betreten wurde, so wähle diesen. (Es wird nur einen solchen Weg geben. Dies ist dein Rückweg aus einem Bereich, den du vollständig, aber vergeblich abgesucht hast.)
          • Andernfalls bist du nach vollständigem zweifachen Abgehen des Labyrinths wieder zum Ausgangspunkt zurückgekehrt.

Es darf beim Betreten eines Platzes auf keinen Fall vergessen werden, diesen auf Markierungen an den anderen Wege-Einmündungen zu untersuchen, um zu entscheiden, ob es sich um eine noch „unbekannte“ Verzweigung handelt.

Literatur
  • Gaston Tarry: Le problème des labyrinthes. In: Nouvelles annales de mathématiques, Bd. 14, 1895, S. 187–190.
  • Édouard Lucas: Récréations mathématiques [Band 1]. 2. Auflage. Paris 1891, S. 47–49 (im 3. Abschnitt).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.