Algoritmo de Tremaux

El algoritmo de Tremaux es un algoritmo inventado por el ingeniero francés Charles Trémaux, para hallar la salida de un laberinto. En el capítulo Stop, or My Dog Will Shoot!, de la decimoctava temporada de Los Simpson, Lisa sugiere utilizar el algoritmo para salir de un laberinto de maíz en que la familia se encontraba atrapada.

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

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

Si 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.

Saludos…

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s