Dicas úteis

Como encontrar uma saída do labirinto

Pin
Send
Share
Send
Send




Desde os tempos antigos, os labirintos carregavam uma sensação de mistério e mistério. Um dos primeiros labirintos conhecidos pela humanidade descreve Heródoto - era um labirinto egípcio no qual havia 5.000 quartos. Com o tempo, os labirintos perderam seu significado religioso e místico e se tornaram objetos de entretenimento, transformando-se em jardins e parques na forma de sebes verdes de configuração complexa.

Resolver os labirintos sempre foi uma atividade fascinante, mas ainda mais emocionante é a criação de máquinas que podem atravessar o labirinto.

Uma das regras mais simples para atravessar um labirinto é a regra de “uma mão”: movendo-se por um labirinto, você sempre deve tocar a parede com a mão direita ou esquerda. Esse algoritmo provavelmente era conhecido pelos gregos antigos. Você tem que percorrer um longo caminho, indo para todos os becos sem saída, mas no final o objetivo será alcançado. Embora essa regra tenha uma desvantagem, falaremos sobre isso mais tarde.

Vamos tentar descrever um robô agindo de acordo com a regra da "mão direita".

No início de seu trabalho, o robô deve encontrar a parede ao longo da qual seguirá. Para fazer isso, ele pode simplesmente avançar até encontrar um obstáculo.

Depois que o robô se depara com um obstáculo, ele começa a se mover de acordo com a regra da "mão direita".

Movendo-se ao longo da parede, o robô monitora se há uma passagem à direita. Se houver uma passagem, o robô deve caminhar ao longo dela para não se afastar da parede à direita.

Se não houver passagem - em frente ao muro - o robô vira à esquerda. Se não houver passagem novamente, vira à esquerda novamente, girando 180 graus e segue na direção oposta.

O diagrama de blocos do algoritmo para um robô que trabalha de acordo com a "regra da mão direita" é mostrado na figura.


Vamos tentar verificar a operação desse algoritmo e escrever um programa para ele. Para esse fim, passamos ao ambiente de programação GameLogo. Esse ambiente é uma ferramenta conveniente para modelar vários algoritmos relacionados ao controle do robô. Ele tem uma tartaruga executora, que em essência nada mais é do que um robô real. A tartaruga tem um conjunto muito conveniente de comandos - frente, direita, esquerda, costas. Além disso, no centro da tartaruga, existe um sensor que assume um valor de 0 a 100, dependendo do tom da superfície em que está localizada.

O dialeto do idioma do logotipo que usaremos é muito simples e semelhante ao básico. Você pode se familiarizar com os comandos de idioma aqui. Um download gratuito do ambiente de programação GameLogo está aqui. O tamanho da distribuição é pequeno - apenas 1 Mb.

No arquivo do GameLogo existem fundos com labirintos, um dos quais usaremos.

No início do programa, damos o comando para a tartaruga levantar a pena (por padrão, a tartaruga deixa um rastro).

O tamanho do campo é de 800 por 600 pixels. A posição inicial da tartaruga está localizada nas coordenadas 115, 545 (quadrado branco).

A cor dos caminhos do labirinto é clara, o sensor neles assumirá valores maiores que 50. A cor das paredes do labirinto é escura, o valor do sensor será menor que 50. A saída do labirinto é representada por um quadrado preto, o valor do sensor acima do qual será 0.

Declararemos uma bandeira variável, com a qual controlaremos se a saída do labirinto é alcançada.

Escreveremos o programa e o iniciaremos com a ajuda do grande botão vermelho com a inscrição “Run”.

Se for sabido que o labirinto não possui paredes separadas, ou seja, não há rotas fechadas pelas quais você possa retornar ao ponto de partida, esse labirinto é chamado de simplesmente conectado e sempre pode ser contornado completamente aplicando a regra de "uma mão".

Se o labirinto contiver paredes independentes, aplicando a regra de “uma mão”, nem sempre é possível passar por todos os corredores e becos sem saída. Labirintos com paredes separadas e com rotas fechadas são chamados de conexões múltiplas. Nesse caso, os labirintos multiplamente conectados podem ser divididos em dois grupos: sem um “loop” ao redor do alvo (uma rota fechada não passa ao redor do alvo) e com um “loop” fechado ao redor do alvo (o alvo pode ser contornado por um caminho fechado).

Nos labirintos multiplamente conectados do segundo grupo, a regra de “mão única” não funciona e, usando-a, é impossível alcançar a meta. Mas mesmo esses labirintos podem ser superados contando com um algoritmo exato.

A solução para o problema de tais labirintos pertence a um tempo relativamente atrasado, e o começo foi estabelecido por Leonard Euler. Euler, não sem razão, acreditava que uma saída de qualquer labirinto pode ser encontrada e, além disso, de uma maneira relativamente simples.

O algoritmo universal para a passagem de qualquer labirinto foi descrito apenas um século depois no livro do matemático francês E. Luke "Recreations matematiques", publicado em 1882. Curiosamente, ao descrever o algoritmo, Luke apontou para a primazia de outro matemático francês M. Tremot. Assim, o algoritmo ficou conhecido como algoritmo Luc-Tremo.

Tremo oferece as seguintes regras: deixando qualquer ponto do labirinto, faça uma marca em sua parede (cruz) e mova-se em uma direção arbitrária para um beco sem saída ou cruzamento, no primeiro caso, volte e coloque uma segunda cruz indicando que o caminho foi cruzado duas vezes - para frente e para trás e siga em uma direção que nunca foi percorrida ou uma vez, na segunda - siga em uma direção arbitrária, marcando cada cruzamento na entrada e saindo com uma cruz; se já houver uma cruz na cruz, você deve seguir um novo caminho se não t - esse caminho atravessado, marcando-o com uma segunda cruz.

Conhecendo o algoritmo Tremo, você pode ajustar o comportamento do lendário Teseu. Inspirado pelo presente de sua amada Ariadne, ele caminha com confiança pelo labirinto. De repente, à sua frente, há um movimento ao longo do qual uma linha já foi esticada. O que fazer Em nenhum caso você o cruza, mas retorna ao longo do caminho já conhecido, dobrando o encadeamento, até encontrar mais um movimento não realizado.

Usando uma variante do algoritmo Tremo, o pai da teoria da informação, Claude Elwood Shannon, construiu um dos primeiros robôs de autoaprendizagem. Shannon deu a ele o nome sonoro de "Teseu", mas na história de "Teseu" ficou mais conhecido como o "rato" de Shannon. O “rato” examinou primeiro o labirinto inteiro e depois (pela segunda vez) foi muito mais rápido, evitando que as áreas passassem duas vezes.

Atualmente, os robôs que passam pelo labirinto participam de uma das competições mais interessantes de máquinas pensantes, que ocorre em vários países do mundo. Essas competições são coletivamente chamadas de competição Micromouse e estão entre os líderes do esporte robótico em termos de inovações técnicas.

As competições foram realizadas na primeira Olimpíada Russa de Robôs, cujo objetivo era passar por uma espécie de labirinto: no menor tempo possível, passando pelas "portas abertas" nas paredes, o robô tinha que ir do ponto inicial ao ponto final. O robô podia controlar seu movimento ao longo de linhas pretas desenhadas no chão do labirinto.

REGRA DE UMA MÃO

Existe uma maneira muito simples de entrar em qualquer labirinto sem medo de se perder nele. Usando esta regra, você sempre pode encontrar uma saída para qualquer labirinto, não importa quão confusas sejam suas transições. Aqui está a regra para vaguear com segurança em labirintos:

É necessário caminhar pelo labirinto, tocando constantemente sua parede com a mesma mão.

Isso significa que, na entrada do labirinto, você deve tocar sua parede com uma mão (da mesma forma, direita ou esquerda) e, no momento em que estiver vagando, continuar a tocar a parede com a mesma mão.

Tente - para experimentar esse método - aplique a "regra de uma mão" para uma caminhada mental ao longo do plano de Hampton Maze. Armado com um fósforo, imagine que você está entrando neste labirinto de jardim e o tempo todo toca nas paredes com uma mão. Logo você chegará da entrada externa ao centro do labirinto. Não abaixe sua mão aqui, continue avançando, tocando-a com as paredes, e você sairá com precisão de seus cantos novamente para a entrada externa.

De onde veio essa regra conveniente? Vamos tentar entender isso. Imagine que você está com os olhos vendados entrando em uma sala com apenas uma entrada. O que você deve fazer para contornar tudo e sair de novo? A maneira mais fácil é andar pelas paredes sem tirar as mãos da parede, e certamente você alcançará novamente a porta pela qual entrou. Aqui, a racionalidade da "regra de uma mão" é auto-explicativa. Imagine agora que as paredes da sala têm saliências, como mostrado na fig. 4 e 5. Antes de você não ser mais simples, mas labirintos reais. Mas a "regra de uma mão" deve, é claro, e nesses casos, manter sua força, levando você de volta com segurança à saída das instalações.

A "regra de uma mão" tem seu inconveniente. Usando-o, você pode entrar em qualquer labirinto e certamente sair dele. Mas isso não significa que você percorrerá todos os cantos do labirinto sem exceção. Você visitará apenas os lugares cujas paredes estão de alguma forma conectadas com a parede externa do labirinto - por assim dizer, sua continuação. Mas você passará por aquelas seções do labirinto cujas paredes não têm conexão com as paredes externas. No labirinto do jardim Hampton, existe exatamente esse site e, portanto, usando a regra de “uma mão”, você não pode percorrer todos os caminhos deste labirinto: um caminho permanece desconhecido. Na fig. 6 linhas tracejadas mostram o caminho ao longo das paredes do hedge, se você usar a "regra de uma mão", e o asterisco marca esse beco, que ao mesmo tempo permanece sem ser detectado.

Pin
Send
Share
Send
Send