0votos

Con "Guido Van Robot" hacer que resuelva cualquier laberinto en Python

por josejuan hace 6 años

Por lo visto éste es un problema con cierta importancia sobre autómatas allá por 1970 en que se demostró que con "miguitas" de pan es posible salir de un laberinto, pero el único paper que he encontrado está en alemán ¡¿#?!. Mi solución es intuitiva (es decir, no DEMUESTRO que siempre salga del laberinto). Por otro lado, el patético repertorio de instrucciones no pone las cosas fáciles (¡no indica si la posición actual tiene beeper!).

Con "Guido Van Robot", una herramienta educativa que es un robot con un pequeño conjunto de instrucciones en python. Programarlo para que resuelva cualquier laberinto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# claro, no puede existir esta función predefinida... 
define turnright: 
    do 3: 
        turnleft 
 
# hacemos una típica salida de laberinto "pegado a un lado" 
# con un pequeño hack para saltar entre lazos, consiste 
# en que cuando giramos abajo, dejamos una miga, para 
# la próxima vez que pasemos, saltemos al lazo siguiente. 
define pegado_der: 
    if right_is_clear: 
        turnright 
        if facing_south: 
            if next_to_a_beeper: 
                turnleft 
        if facing_south: 
            putbeeper 
        move 
    elif front_is_clear: 
        move 
    else: 
        turnleft 
 
while not_next_to_a_beeper: 
    pegado_der 
    if next_to_a_beeper: 
            pickbeeper 
            while front_is_clear: 
                move 
            turnleft 
 
turnoff 
 
# dejo imágenes en los comentarios 
3 comentarios
0votos

Escrito por josejuan hace 6 años

Dejo un AVI (1.7Mbytes) con una ejecución de un laberinto con lazos.

http://jose-juan.computer-mind.com/jose-juan/data/tmp/guidoRobot.avi

La única referencia que he encontrado (tampoco he buscado mucho, si tienes interés buscaría más) es de un trabajo en alemán...

"A one-symbol printing automaton escaping from every labyrinth"

http://link.springer.com/article/10.1007%2FBF02252348
0votos

Escrito por Miguel hace 6 años

Gran solución (^_^), lo he probado con un laberinto al azar y también lo ha resuelto.
0votos

Escrito por josejuan hace 6 años

No Miguel, no es una gran solución, he detectado que puede haber "falsos lazos" que hacen entrar al robot en un bucle infinito (vamos, que hay laberintos para los que la estrategia que he puesto falla).

Podría refinarse la estrategia para evitar los casos que veamos, pero sin una demostración más o menos clara lo único que conseguiremos es tener un algoritmo muy complicado que fallará en situaciones más complejas.

Al menos (por las ref que he pasado) ya sabemos que sí se puede hacer... :P

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.