Solucionador de labirinto míope ideal

Eu estava brincando com a demo do Google Blocky's Maze e lembrei da regra antiga de que, se você quiser resolver um labirinto, mantenha a mão esquerda na parede. Isso funciona para qualquer labirinto conectado simples e pode ser implementado por um transdutor finito.

Deixe nosso robô ser representado por um transdutor com as seguintes ações e observáveis:

• Ações: vá em frente ( ), vire à esquerda ( ), vire à direita ( )← $\uparrow$$\leftarrow$$\rightarrow$
• Observáveis: parede à frente ( ), sem parede à frente ( )$\bot$$\top$

Em seguida, podemos construir o solucionador de labirinto esquerdo como (perdoe meu desenho preguiçoso):

Onde ver um observável nos fará seguir a borda apropriada para fora do estado enquanto executamos a ação associada a essa borda. Esse autômato resolverá todos os labirintos simplesmente conectados, embora possa demorar um pouco após os becos sem saída. Chamamos outro autômato melhor que se:$B$ $A$

1. $B$ executa estritamente mais etapas em apenas um número finito de labirintos e

2. $B$ executa estritamente menos etapas (em média; para variantes probabilísticas) em um número infinito de labirintos.

Minhas duas perguntas:

1. Existe um autômato finito melhor que o desenhado acima? E se permitirmos transdutores probabilísticos?

2. Existe um autômato finito para resolver labirintos que não são necessariamente simplesmente conectados?

Se entendi bem a pergunta, acho que você pode aplicar um truque de aceleração para obter autômatos mais rápidos em um número infinito de labirintos (desde que a saída seja colocada em uma das bordas): você pode simplesmente usar os estados internos para armazenar um número finito de etapas e reconhecer becos sem saída como o da figura:

Quando um autômato à direita está na posição e seu estado "sinaliza" que acabou de seguir um quadrado fechado ( com tamanho fixo codificado, não um quadrado grande arbitrário ), ele pode virar à esquerda com segurança e evitar visitar o beco sem saída zona. Conforme sublinhado no meu comentário abaixo, o autômato aplicará o atalho em todos os labirintos que contenham uma (ou mais) "sub-imagens" como a da figura, para que ele tenha um desempenho melhor em infinitos labirintos. Nos labirintos que não contêm uma sub-imagem como a da figura, ela funcionará como um autômato padrão à direita.$A$

De maneira semelhante, você pode codificar um número finito de diferentes formas de tamanho fixo para evitar becos sem saída e acelerar seu autômato. Como conseqüência, não existe um solucionador de labirinto míope "ideal" para labirintos simplesmente conectados com a saída colocada na borda.

O truque funciona se a entrada for colocada dentro do labirinto e a saída na fronteira também; mas se a saída for colocada dentro do labirinto, não funcionará porque todos os locais devem ser visitados e, nesse caso, o seu solucionador míope é ideal.

Obviamente, você não pode aplicar o mesmo truque para resolver labirintos não simplesmente conectados (mas deve funcionar se houver um limite superior fixo no tamanho de cada componente não conectado).

Questão 1

Acho que sua definição de melhor é muito rigorosa no sentido de que finito é muito restritivo (mas não tenho nenhuma definição melhor).

$R=(R_i)_i$$R_i$$i$$L$$A_R$$A_L$$R$$L$$A_R$$A_L$

$A_R$$R$$A_R$

Transdutores probabilísticos provavelmente podem ser descartados, já que um transdutor determinístico será mais rápido nesses conjuntos infinitos de labirintos.

Pergunta 2 (graças à discussão com o OP )

Não. (Fonte: este artigo inovador de Lothar Budach. O teorema é mais claramente afirmado no resumo deste artigo por Frank Hoffmann.)