Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como usar os movimentos da torre de Hanoi para gerar todos os subconjuntos de um determinado conjunto?

+1 voto
49 visitas
perguntada Jun 22 em Matemática por JoaoMaria (71 pontos)  
republicada Jun 27 por JoaoMaria
Compartilhe

1 Resposta

+1 voto
respondida Jun 26 por JoaoMaria (71 pontos)  
editado Jun 27 por JoaoMaria

Antes de apresentar a solução, é necessário explicar o jogo da Torre de Hanói e alguns conceitos que estão ligados a ele.
A Torre de Hanói consiste de uma base com três pinos e um certo número \(n\)
de discos de diâmetros diferentes, colocados um sobre o outro em um dos pinos, em ordem decrescente de seus diâmetros, de baixo para cima, como na figura abaixo, em que \(n=6\):
A imagem será apresentada aqui.
O jogo consiste em transferir a torre de discos para um dos outros dois pinos, movimentando um disco de cada vez, utilizando-se um dos pinos livres como auxiliar e nunca colocando um disco sobre outro de diâmetro menor.
A ilustração abaixo apresenta uma possibilidade para os 7 movimentos necessários para resolver o jogo para n=3:
A imagem será apresentada aqui.
O interessante sobre o jogo é que o numero de movimentos para resolvê-lo quando existem \(n\) discos é \(n^2-1\).

voltando ao nosso problema, encontrar os subconjuntos um conjunto \(A\) com \(n\) elementos. Deseja-se encontrar todos os elementos de \(2^A\) .
Qual o número de subconjuntos distintos que ele possui ?
Se n=0 então \( A\) terá somente um subconjunto. o vazio \( \{\phi \}\).
Se n=1 então \( A\) terá um subconjunto contendo um elemento, mais o vazio.
Se n=2 então \( A\) terá dois subconjuntos contendo um elemento,um subconjunto exatamente igual a \(A\), mais o vazio.
Dessa forma, por indução, facilmente demonstra-se que o número de subconjuntos de um conjunto \(A\) com \(n\) elementos é : \(2^n\).

Logo, temos a solução!
O número de movimentos da torre de Hanói com \(n\) discos, é exatamente igual ao número de subconjuntos de um conjunto com \(n\) elementos menos o conjunto vazio.
Podemos implementar um algoritmo recursivo para solucionar a torre de Hanói com \(n\) discos e para cada movimento de discos verificaremos o estado dos pinos para gerarmos os subconjuntos.
Abaixo explicamos em detalhe o algoritmo codificado em Python.

Inicialmente, declaramos duas variáveis globais em nosso código. O número e movimentos e a variável que guardará os subconjuntos:

 nmov=0
subconjuntos=[]

Abaixo encontramos a rotina recursiva que controla os movimento da torre. Para ela são passados as seguintes variáveis:
n - o número de discos
pini, pfim, paux - Respectivamente os pinos inicial, final e auxiliar
patinete - vetor que contém n elementos que é utilizada para controlar o tamanho dos subconjuntos, pois teremos subconjuntos com t=1,...,n elementos.

def hanoi(n,pini,pfim,paux,patinete):
    if(n==1):
        move(n,pini,pfim,patinete)
    else:
        hanoi(n-1,pini,paux,pfim,patinete)
        move(n,pini,pfim,patinete)
        hanoi(n-1,paux,pfim,pini,patinete)

Abaixo, mostramos a rotina que "move os pinos". Aqui controlamos o índice da variável patinete para gerarmos o subconjunto associado e em seguida chamamos a rotina que irá gerar o subconjunto de acordo com a situação dos pinos.
Para facilitar o entendimento, colocamos a impressão da situação atual dos subconjuntos

def move(n,pini,pfim,patinete):
        global nmov
        nmov+=1
        print ("Mov no.:", nmov,"move disco:",n," de:",pini,"-->",pfim)

        if patinete[n-1]==0:
            patinete[n-1]=1
        else:
            patinete[n-1]=0

        pega_subconjunto(patinete)
        print(subconjuntos)

a rotina abaixo, gera o subconjunto específico para o estado dos pino A, B e C

def pega_subconjunto(patinete):
    conjunto=[]
    for i in range(0, len(patinete)):
        if patinete[i]==1:
            conjunto.append(i+1)
    subconjuntos.append(conjunto)
    return

Agora, abaixo está o programa principal. Nele se define o número de discos, também se adiciona o subconjunto vazio ( pois ele sempre estará em \(2^A\)), inicializa-se a variável patinete de acordo com o número de discos e, por fim, chama-se a rotina Hanoi

if __name__ == '__main__':
    ndiscos=4
    patinete=[]
    subconjuntos.append([])
    for i in range(0,ndiscos):
        patinete.append(0)
    hanoi(ndiscos,'A','B','C',patinete)

Abaixo são apresentados os resultados para \(n=4\)

Mov no.: 1 move disco: 1  de: A --> C
[[], [1]]
Mov no.: 2 move disco: 2  de: A --> B
[[], [1], [1, 2]]
Mov no.: 3 move disco: 1  de: C --> B
[[], [1], [1, 2], [2]]
Mov no.: 4 move disco: 3  de: A --> C
[[], [1], [1, 2], [2], [2, 3]]
Mov no.: 5 move disco: 1  de: B --> A
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3]]
Mov no.: 6 move disco: 2  de: B --> C
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3]]
Mov no.: 7 move disco: 1  de: A --> C
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3]]
Mov no.: 8 move disco: 4  de: A --> B
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4]]
Mov no.: 9 move disco: 1  de: C --> B
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4]]
Mov no.: 10 move disco: 2  de: C --> A
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4], [1, 2, 3, 4]]
Mov no.: 11 move disco: 1  de: B --> A
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4], [1, 2, 3, 4], [2, 3, 4]]
Mov no.: 12 move disco: 3  de: C --> B
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4], [1, 2, 3, 4], [2, 3, 4], [2, 4]]
Mov no.: 13 move disco: 1  de: A --> C
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4], [1, 2, 3, 4], [2, 3, 4], [2, 4], [1, 2, 4]]
Mov no.: 14 move disco: 2  de: A --> B
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4], [1, 2, 3, 4], [2, 3, 4], [2, 4], [1, 2, 4], [1, 4]]
Mov no.: 15 move disco: 1  de: C --> B
[[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3], [3, 4], [1, 3, 4], [1, 2, 3, 4], [2, 3, 4], [2, 4], [1, 2, 4], [1, 4], [4]]
comentou Jun 30 por Peng Yaohao (101 pontos)  
editado Jun 30 por Peng Yaohao
Boa resposta: o jogo da Torre de Hanoi ficou bem explicado aos que eventualmente não o conheciam, as figuras também foram bem escolhidas. O código ficou bem sucinto e ilustra bem como a ideia da recursão e como esse conceito pode ser aplicado para tornar um algoritmo computacional mais eficiente.

A intuição de utilizar os movimentos necessários para resolver esse jogo para encontrar os subconjuntos do conjunto \(A=\{1,2,3,...,n\}\) está no fato de os discos não serem movidos um mesmo número de vezes - mais que isso, constata-se que o número de vezes que cada disco é movido é uma potência de dois (por exemplo, é fácil ver que o maior disco se moverá apenas uma vez, o segundo maior, duas vezes, e assim por diante.) Assim, o número de movimentos totais será a soma \(2^0+2^1+2^2+...+2^{n-1}=2^n-1\) (e não \(n^2-1\), como consta na resposta).

Conforme bem descrito na resposta, o número de subconjuntos de \(A\) é igual a \(2^n\) - é possível associar esse número a um problema simples de combinatória: para cada subconjunto possível, é possível encarar cada um dos \(n\) elementos de \(A\) como estando "presente" ou "ausente" - 2 resultados para cada elemento, resultando em \(2^n\) subconjuntos ao todo. Associando com a torre de Hanoi, a cada movimento, a "orientação" do respectivo disco se "inverte" (ou seja, se ele está "presente", ficará "ausente", e vice-versa). Somando com a configuração inicial, obtêm-se exatamente os \(2^n-1+1=2^n\) subconjuntos!

No código implementado utilizou-se o *append*, que inclui um elemento novo na lista. Em vez disso, seria melhor substituir a lista atual pelo novo subconjunto, derivado do novo movimento da torre de Hanoi, para ficar mais fácil de visualizar:

No caso de 4 discos, ficaria algo assim:

Configuração inicial (Todos os discos no pino esquerdo): Subconjunto vazio (vetor binário: \(\{0,0,0,0\}\))

Mov no.: 1 move disco: 1  de: A --> C -- (sem perda de generalidade, disco 1 é o menor e disco 4 é o maior)
  - Vetor binário: \(\{1,0,0,0\}\)) -- "inverte" 1º elemento do disco de 0 para 1, manter o resto constante
  - Subconjunto associado (1 para presença, 0 para ausência): \(\{1\}\)) (apenas 1º elemento presente)

Mov no.: 2 move disco: 2  de: A --> B
  - Vetor binário: \(\{1,1,0,0\}\)) -- "inverte" 2º elemento do disco de 0 para 1, manter o resto constante
  - Subconjunto associado (1 para presença, 0 para ausência): \(\{1,2\}\)) (1º e 2º elementos presentes)

Mov no.: 3 move disco: 1  de: C --> B
  - Vetor binário: \(\{0,1,0,0\}\)) -- "inverte" 1º elemento do disco de 1 para 0, manter o resto constante
  - Subconjunto associado (1 para presença, 0 para ausência): \(\{2\}\)) (2º elemento presente, 1º elemento fica "ausente")

E assim por diante. A lista de subconjuntos será: \(\{\}\),\(\{1\}\),\(\{1,2\}\),\(\{2\}\),\(\{2,3\}\),\(\{1,2,3\}\),\(\{1,3\}\),\(\{3\}\),\(\{3,4\}\),\(\{1,3,4\}\),\(\{1,2,3,4\}\),\(\{2,3,4\}\),
\(\{2,4\}\),\(\{1,2,4\}\),\(\{1,4\}\),\(\{4\}\), exatamente igual à lista final apresentada pela resposta, após o movimento nº 15.

É interessante notar que esse algoritmo funciona para qualquer subconjunto de \(A\) escolhido como configuração inicial - escolhendo qualquer um dos \(2^n\) subconjuntos,  o algoritmo irá encontrar os \(2^n-1\) restantes, um para cada movimento da torre de Hanoi. Por exemplo, inicializando com \(\{1,2,4\}\), a sequência será \(\{1,2,4\}\),\(\{2,4\}\),\(\{4\}\),
\(\{1,4\}\),\(\{1,3,4\}\),\(\{3,4\}\),\(\{2,3,4\}\),\(\{1,2,3,4\}\),\(\{1,2,3\}\),\(\{2,3\}\),\(\{3\}\),\(\{1,3\}\),\(\{1\}\),
\(\{\}\),\(\{2\}\),\(\{1,2\}\)
comentou Jul 7 por JoaoMaria (71 pontos)  
Obrigado pela avaliação e sugestão
...