Algoritmo de Tremaux

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Tremaux' Methode - animiertes Beispiel.gif

El algoritmo de Tremaux es un algoritmo inventado por el ingeniero francés Charles Trémaux,[1] para hallar la salida de un laberinto.

Lo primero que hay que hacer es marcar el camino que se va siguiendo, y seguir estos pasos:

  1. No siga el mismo camino dos veces.
  2. Si llega a un cruce nuevo, no importa qué camino siga.
  3. Si un camino nuevo lo lleva a un cruce viejo, o a un callejón sin salida, retroceda hasta la entrada del camino.
  4. Si un camino viejo lo lleva a un cruce viejo, tome un camino nuevo, y si no lo hay, tome cualquiera.

Si se siguen estos pasos, aunque es posible que lleve horas, este sistema le llevará hasta la salida del laberinto, y si no la hay, de nuevo hasta la entrada.

Referencias culturales[editar]

En el capítulo Stop, or My Dog Will Shoot!, de la Decimooctava temporada de Los Simpson , Lisa sugiere utilizar el algoritmo para salir de un laberinto de maíz en que la familia se encontraba atrapada, logrando ese objetivo.

Referencias[editar]

  1. Conferencia pública (2 de diciembre de 2010) del profesor Jean Pelletier-Thibert en la Academie de Macon (Borgoña - Francia) - (resumen publicado en los Anales académicos, marzo de 2011 - ISSN 0980-6032)
    Charles Tremaux (° 1859 - † 1882) Ecole Polytechnique of Paris (X:1876), ingeniero francés de telégrafos

Enlaces externos[editar]