Vídeo: Binário, Hanói e Sierpinski, Parte 2

Grant Sanderson • 3Blue1Brown • Boclips

Binário, Hanói e Sierpinski, Parte 2

12:13

Transcrição do vídeo

Bem-vindo de volta! Então, na última parte, mostrei uma maneira de resolver as Torres de Hanói apenas contando em binário, uma solução que aprendi com o cientista da computação Keith Schwarz. Se, de alguma forma, você chegou aqui sem assistir, provavelmente vai querer dar uma olhada. Aqui, neste vídeo, quero descrever uma variante restrita desse quebra-cabeça e como ela se relaciona com a descoberta de uma curva que preenche o triângulo de Sierpinski.

KEITH: A variante do problema é que, você sabe, alguém pode pensar que esses discos estão em uma linha. Você só pode mover um disco de um eixo para outro adjacente. E, agora, a questão é resolver as Torres de Hanói.

GRANT: Então, por exemplo, como em um anterior, começamos movendo o disco zero para B. E o próximo passo foi mover o disco um para C. Mas você não pode fazer isso porque não tem uma reta direita até C.

KEITH: Exatamente! Então é mais complicado. Mas a ideia para esta versão modificada ainda é semelhante. Então, se eu quiser mover o disco três, digamos que estou tentando movê-lo de A para C. Então, como antes, não posso mover o disco três, a menos que esta torre acima dele — dois, um e zero — esteja fora do caminho. Então, finalmente, eu gostaria que essa torre não o bloqueasse. Mas há duas maneiras de bloqueá-lo agora. Então, anteriormente, só precisava não estar no topo. Agora, além de não estar no topo, também não pode ser adjacente. Então, realmente, o que eu quero fazer é pegar essa torre de zero, um e dois e, de alguma forma, eu não sei, colocar isso na coisa C e mover o disco três. Depois, desça de C de volta para A. Em seguida, mova o disco três do pino B para o pino C. E então mova a torre todo o caminho de volta.

O caso menor divide-se essencialmente da mesma maneira. Você resolve para dois discos, move o disco número dois, resolve para dois novamente, move o número do disco dois e depois resolve dois discos novamente. À medida que você continua se subdividindo nesse padrão auto semelhante, expandindo cada subproblema em seu próprio conjunto de subproblemas. Eventualmente, você chega ao menor subproblema de todos, movendo uma torre de tamanho um, o que envolve apenas mover o disco número zero duas vezes.

Como no caso irrestrito, isso fornecerá a solução mais eficiente, pois em todas as escalas você está apenas fazendo o que precisa. Você precisa mover essa sub torre com zero, um e dois para o pino C se planeja mover o disco número três. E você precisa movê-lo de volta para A para mover o disco três novamente. E você tem que mudar tudo de volta para C pela terceira vez. Nunca há margem para ineficiência depois que você a divide em termos de subproblemas como este. E assim como o quebra-cabeça irrestrito espelhava o padrão de contagem em binário, o colapso desse problema restrito é espelhado pela contagem na base três, também conhecida como ternária. Aqui, vamos falar um pouco sobre como é a base três, qual é o ritmo da contagem.

Portanto, como você sabe, nosso sistema de contagem usual, base 10, possui 10 algarismos separados e binários, ou base dois, possui dois algarismos separados. Então o ternário é um sistema de representação de números em que você tem apenas três símbolos distintos disponíveis: zero, um e dois.

KEITH: Eu nem sei como você chama isso. Então, não é um pouco; não é um algarismo; é isso, é trit? Isso só … acho que estávamos falando sobre isso antes. Como se não parecesse certo.

Eles são de fato chamados trits. Mas, ei, se isso lhe parecer um pouco estranho, pergunte a um falante de francês como eles se sentem sobre a nossa convenção de chamar algarismos binários de “bits”.

Enfim, voltando ao que estávamos fazendo, vamos pensar no ritmo da contagem em nível ternário. Você começa contando os trits, zero, um, dois. Então, você deve rolar para um segundo trit em três lugares. Então, você conta até quatro, que é um, um; cinco, que é um, dois; e você precisa rolar novamente para dois, zero, representando seis. Então dois, um; dois, dois, em que você precisa rolar duas vezes para o nono lugar, escrevendo o número nove como um, zero, zero. Assim como a base dois e a base 10, há uma certa semelhança com esse padrão. Em todas as escalas, parece contar até certo ponto, rolando, contando com o mesmo valor, rolando novamente. Contando com a mesma quantia pela terceira vez.

Mas esse é o padrão que acabamos de ver nas torres restritas de Hanói. Faça uma subtarefa, faça algum tipo de movimento maior, faça uma subtarefa, faça o mesmo movimento maior. Em seguida, execute a subtarefa pela terceira vez. Assim como a contagem binária reflete a solução para as torres irrestritas de Hanói, a contagem na ternária reflete o padrão recursivo para resolver as torres restritas de Hanói. Isso fornece uma maneira realmente agradável e metódica de resolver o problema restrito apenas contando. Sempre que alterar apenas o último trit, mova o número do disco zero. Portanto, para os dois primeiros movimentos quando estiver contando um, dois, você estará movendo o disco zero. Sempre que você passar apenas uma vez para os três lugares, como quando você conta de dois a três representados por um, zero, você move o disco número um.

E continuando assim, você daria o último passo, move zero; vire o último, move zero; role escrevendo dois, zero; e depois mova o disco um. Depois, mais duas vezes, você vira o último e move o disco zero. Então, sempre que você rolar duas vezes para o lugar nove, mova o disco número dois. Mais uma vez, é bem divertido voltar e assistir a esse jogo. Demora um pouco, no entanto. Para quatro discos, você terá que contar até dois, dois, dois, dois, o que é ternário para três elevado a quatro menos um, que é 80. Isso significa que resolver isso envolve 80 etapas. No entanto, como eu disse antes, esta é a solução mais eficiente.

KEITH: Mas isso também oferece algo muito legal. Você pode perguntar: “Quantas configurações diferentes existem para as Torres de Hanói?”

Na verdade, vamos tirar um momento e pensar sobre isso. Quantas configurações totais de discos em pinos são possíveis, onde os discos em um determinado pino precisam estar em ordem decrescente de tamanho? A resposta é de três elevado a quatro, 81 estados possíveis em que o seu quebra-cabeça pode estar. Para ver isso, observe que existem três opções para onde colocar o maior disco. Depois, três opções para onde colocar o próximo maior disco. E para cada disco sucessivo, você tem três opções para onde colocá-lo.

E lembre-se, esse processo de resolução contando em base ternária envolve pegar três elevado a quatro menos um passo. O que significa que, do começo ao fim, você terá 81 configurações diferentes. E se você pensar bem sobre isso, ela não pode atingir uma determinada configuração duas vezes. Se isso acontecesse, haveria uma solução mais eficiente fora dela, trabalhando até a primeira vez em que você acessa essa configuração e, em seguida, pulando tudo entre essa e a segunda vez em que você tem a mesma configuração, continuando.

KEITH: Eu tenho, de certa forma, uma espécie de grande turnê. Isso não apenas resolverá as Torres de Hanói. Isso passará por todas as configurações possíveis dos discos.

Muito legal, né? Bem, aqui é onde as coisas ficam incríveis. Para aqueles que conhecem os gráficos, há uma estrutura muito bonita nessas configurações. O que vou fazer é representar cada uma dessas configurações com um ponto, um nó em nosso gráfico. Então, dizemos que duas configurações diferentes estão conectadas se você puder passar de uma para outra com alguns movimentos legais das Torres de Hanói. E desta vez, quero dizer uma jogada sem restrições. Portanto, as configurações ainda são consideradas conectadas, mesmo que exijam um movimento do pino A para o pino C. Quando você realiza e conecta todas as configurações como essa, encontrando todas as arestas que representam algum tipo de movimento, a estrutura gráfica das Torres de Hanói tem essa forma suspeitamente familiar.

Agora, vamos dar um zoom e pensar de onde vem esse padrão. Por exemplo, este nó aqui representando o estado inicial com todos os discos no pino A será conectado a este, que é o resultado de mover o disco zero para o pino B. E os dois estão conectados a este, que é o resultado da movimentação do disco zero para o pino C. Essas três configurações formam um pequeno triângulo em nosso gráfico. Ou seja, as três configurações estão todas mutuamente conectadas. De fato, qualquer configuração fará parte de um desses triângulos em algum lugar do gráfico. Você apenas considera o que acontece quando se move livremente pelo disco de número zero entre os três pinos.

Agora, para entender como essas pequenas ilhas triangulares estão interconectadas, dê uma olhada nesses dois nós. Eles diferem apenas pelo movimento do disco número um do pino A ao pino C. Portanto, eles serão conectados por uma aresta. Essa aresta é como uma ponte entre duas ilhas triangulares diferentes. De fato, esses dois triângulos, junto com este outro, formam uma espécie de metatriângulo quando você considera todos os movimentos do disco um. Cada pequeno grupo de três nós aqui representa uma posição diferente para o disco número um. E o padrão de triforce como um todo representa todas as configurações que você pode obter movendo os discos número um ou zero.

E, de maneira semelhante, um movimento do disco número dois fornece uma ponte de um desses padrões de triforce para um novo. E os três lugares possíveis onde o disco dois pode ficar nos fornece esses três padrões de triforce separados, cada um conectado por uma pequena ponte. O fato de haver apenas dois nós em um desses padrões de triforce que tem uma aresta saindo do próprio padrão é apenas um reflexo do fato de que é difícil mover o disco número dois. Isso acontece apenas nas configurações muito especiais em que o disco um e o disco zero estão fora do caminho.

À medida que você considera mais e mais discos, esse padrão continua. A estrutura gráfica das configurações das Torres de Hanói é um grande triângulo de Sierpinski. Isso não é louco?! Agora, vamos pensar no que significa esse método de resolver o problema restrito, contando, em nível ternário, para percorrer todas as configurações possíveis. O que isso nos dará é uma maneira de percorrer esse gráfico e atingir cada nó uma vez e apenas uma vez. Isso é loucura para mim. Se você apenas olhar para a estrutura gráfica de Sierpinski, não está claro a princípio que esse caminho seja possível. E, no entanto, encontramos um apenas contando. Se isso não for bonito, não sei o que é.

Tudo bem! Então, para esta última animação aqui, mostrarei o caminho que percorre o gráfico de Sierpinski de acordo com a maneira pela qual a contagem ternária resolve o quebra-cabeça restrito das Torres de Hanói. Se eu desvanecer esse gráfico apenas para enfatizar o caminho, aqui está o que parece para ordens cada vez maiores, correspondendo as Torres de Hanói com mais e mais discos. O que você está vendo é muito parecido com a ideia de curvas de preenchimento de espaço que eu falei no vídeo da curva de Hilbert. Só que o limite aqui preenche um fractal em vez do quadrado. Isso não é louco?! Você pode ter uma curva que preenche o triângulo de Sierpinski, que eu não considero totalmente uma coisa do tipo curva.

A Nagwa usa cookies para garantir que você tenha a melhor experiência em nosso site. Saiba mais sobre nossa Política de privacidade.