Artigo original: How to Solve the Tower of Hanoi Problem - An Illustrated Algorithm Guide
Tradução realizada em português europeu
Antes de começarmos, vamos discutir o que é o problema da Torre de Hanói. Bem, é um simples puzzle onde o objetivo é mover um bloco completo de discos de uma posição inicial para outra posição. São seguidas três regras simples:
- Apenas pode ser movido um disco de cada vez.
- Cada movimento consiste em pegar no disco mais acima na pilha e colocá-lo no topo de outra pilha. Por outras palavras, um disco apenas pode ser movido se for o disco que está mais acima na pilha.
- Não pode ser colocado um disco maior sobre um menor.
Agora, vamos tentar imaginar um cenário. Vamos supor que temos uma pilha com três discos. O nosso objetivo é mover esta pilha da origem A para o destino C. Como fazemos isto?
Antes de lá chegarmos, vamos imaginar que existe um ponto intermédio B.
Podemos utilizar B como ajuda para completar essa tarefa. Agora, estamos prontos para avançar. Vamos analisar cada um dos passos:
- Mover o primeiro disco de A para C
- Mover o primeiro disco de A para B
- Mover o primeiro disco de C para B
- Mover o primeiro disco de A para C
- Mover o primeiro disco de B para A
- Mover o primeiro disco de B para C
- Mover o primeiro disco de A para C
Resolvemos o nosso problema!
Podes observar a imagem animada acima para uma compreensão melhor do problema.
Agora, vamos tentar criar o algoritmo para resolver o problema. Espera, temos aqui uma nova palavra: "Algoritmo". O que é isso? Alguma ideia? Sem problema, vamos ver.
O que é um algoritmo?
Um algoritmo é um dos conceitos mais importantes para um programador de software. Na verdade, acho que não é apenas importante para desenvolvimento de software ou programação, mas para toda a gente. Os algoritmos afetam-nos na nossa vida do dia a dia. Vamos ver como.
Vamos supor que trabalhas num escritório. Então, todas as manhãs fazes uma série de tarefas em sequência: primeiro acordas, depois vais à casa de banho, tomas o pequeno-almoço, preparas-te para o trabalho, sais de casa e, depois, podes apanhar um táxi ou autocarro, ou começar a andar em direção ao escritório e, depois de um determinado tempo, chegas ao escritório. Podes dizer que todos esses passos formam um algoritmo.
De forma simples, um algoritmo é um conjunto de tarefas. Espero que não te tenhas esquecido dos passos que realizamos para mover os três discos da pilha A para a C. Também podes dizer que esses passos são o algoritmo para resolver o problema da Torre de Hanói.
Em matemática e ciências da computação, um algoritmo é uma especificação ambígua de como resolver uma classe de problemas. Os Algoritmos podem realizar cálculo, processamento de dados e tarefas de raciocínio automatizado. — Wikipédia
Se observares estes passos, podes ver que fizemos a mesma tarefa várias vezes — mover discos de uma pilha para outra. A esses passos dentro de passos podemos chamar recursividade.
Recursividade
Recursividade é chamar a mesma ação a partir dessa ação, tal como na imagem acima.
Portanto, existe um regra para quando fazemos algum trabalho recursivo: deve existir uma condição para parar a execução da ação. Espero que tenhas compreendido os conceitos básicos sobre recursividade.
Agora, vamos tentar criar um procedimento que nos ajuda a resolver o problema da Torre de Hanói. Estamos a tentar criar a solução utilizando pseudocódigo. Pseudocódigo é um método de escrita de código utilizando a língua inglesa.
tower(disk, source, intermediate, destination)
{
}Esse é o esqueleto da nossa solução. Recebemos o número total de discos como um argumento. Depois temos de passar a origem, local intermédio e destino de modo a podermos compreender o mapa que vamos utilizar para completar a tarefa.
Agora, precisamos de encontrar um estado terminal. O estado terminal é o estado onde vamos deixar de chamar a função.
IF disk is equal 1No nosso caso, este seria o nosso estado terminal. Quando existir apenas um disco na pilha, é simples realizar este último passo e, depois disso, a nossa tarefa estará concluída. Não te preocupes se isto não for claro para ti. Quando chegarmos ao final, este conceito será mais claro.
Bem, encontramos o nosso ponto de estado terminal onde movemos o nosso disco para o destino, deste modo:
move disk from source to destinationAgora, chamamos a nossa função novamente ao passar estes argumentos. Neste caso, dividimos a pilha de discos em duas partes. O disco maior (enésimo disco) está numa parte e todos os outros discos (n-1) estão na segunda parte. Aí, chamamos o método duas vezes para (n-1).
tower(disk - 1, source, destination, intermediate)Tal como indicamos, passamos total_disks_on_stack — 1 como argumento. Então, movemos novamente o nosso disco, deste modo:
move disk from source to destinationDepois disso, chamamos novamente o nosso método, desta forma:
tower(disk - 1, intermediate, source, destination)Vamos observar o nosso pseudocódigo completo:
tower(disk, source, inter, dest)
IF disk is equal 1, THEN
move disk from source to destination
ELSE
tower(disk - 1, source, destination, intermediate) // Step 1
move disk from source to destination // Step 2
tower(disk - 1, intermediate, source, destination) // Step 3
END IF
ENDEsta é a árvore para três discos:
Este é o código completo em Ruby:
def tower(disk_numbers, source, auxilary, destination)
if disk_numbers == 1
puts "#{source} -> #{destination}"
return
end
tower(disk_numbers - 1, source, destination, auxilary)
puts "#{source} -> #{destination}"
tower(disk_numbers - 1, auxilary, source, destination)
nil
endChama tower(3, 'source','aux','dest')
Resultado:
source -> dest
source -> aux
dest -> aux
source -> dest
aux -> source
aux -> dest
source -> destForam necessários sete passos para os três discos chegarem ao destino. Chamamos a isto um método recursivo.
Cálculo de complexidade de tempo e de espaço
Complexidade de tempo (texto do link em inglês)
Quando executamos código ou uma aplicação na nossa máquina demora tempo — ciclos de CPU. Não é igual em todos os computadores, no entanto. Por exemplo, o tempo de processamento de um Core I7 e de um dual core é diferente. Para resolver este problema, existe um conceito utilizado na ciência da computação chamado complexidade de tempo.
Complexidade de tempo é um conceito em ciências da computação que lida com a quantificação da quantidade de tempo gasto por um conjunto de código ou algoritmo para processar ou executar como uma função da quantidade do input.
Por outras palavras, complexidade de tempo é essencialmente eficiência, ou quanto tempo uma função do programa demora a processar um determinado input. — techopedia
A complexidade de tempo dos algoritmos é geralmente expressada utilizando a notação de O grande. É uma notação assimptótica para representar a complexidade de tempo.
Agora, o tempo necessário para mover n discos é T(n). Existem duas chamadas recursivas para (n-1). Existe uma operação de tempo constante para mover um disco de um ponto inicial para um destino, que seja m1. Portanto:
T(n) = 2T(n-1) + m1 ..... eq(1)E
T(0) = m2, a constant ...... eq(2)
From eq (1)
T(1) = 2T(1-1) + m1
= 2T(0)+m1
= 2m2 + m1 ..... eq(3) [From eq 2]
T(2) = 2T(2-1) + m1
= 2T(1) + m1
= 4m2 + 2m1 + m1 .... eq(4) [From eq(3)]
T(3) = 2T(3-1) + m1
= 2T(2) + m1
= 8m2 + 4m1 + 2m1 + m1 [From eq(4)]A partir destes padrões — eq(2) até ao último — podemos dizer que a complexidade de tempo deste algoritmo é O(2^n) ou O(a^n), onde a é uma constante maior do que 1. Por isso, tem complexidade de tempo exponencial. Para um único aumento no tamanho do problema, o tempo necessário é o dobro do anterior. Isto é computacionalmente muito caro. A maior parte dos programas recursivos recebem tempo exponencial, e é por isso que é muito difícil escrevê-los de maneira iterada.
Complexidade de espaço (texto do link em inglês)
Depois da explicação da análise da complexidade de tempo, acho que consegues adivinhar o que é isso. É o cálculo do espaço necessário em memória RAM para executar código ou uma aplicação.
No nosso caso, o espaço para o parâmetro por cada chamada é independente de n, o que significa que é constante. Que seja J. Quando realizamos a segunda chamada recursiva, a primeira termina. Isso significa que podemos reutilizar o espaço depois de finalizar a primeira. Portanto:
T(n) = T(n-1) + k .... eq(1)
T(0) = k, [constant] .... eq(2)
T(1) = T(1-1) + k
= T(0) + k
= 2K
T(2) = 3k
T(3) = 4kEntão, a complexidade de espaço é O(n).
Depois destas análises, podemos ver que a complexidade de tempo deste algoritmo é exponencial, mas a complexidade de espaço é linear.
Conclusão
Depois deste artigo, espero que agora consigas compreender melhor o puzzle da Torre de Hanói e como resolvê-lo. Além disso, tentei fornecer algum conhecimento básico sobre algoritmos, a sua importância, recursividade, pseudocódigo, complexidade de tempo e complexidade de espaço. Se quiseres obter informações mais detalhadas sobre estes tópicos, aqui estão os links para alguns cursos on-line bastante conhecidos:
- Algoritmos, Parte I, da Coursera
- Algoritmos, Parte II, da Coursera
- O Curso da Google da Udacity
- Certificação em Algoritmos e Estruturas de Dados em JavaScript (300 horas)
Podes visitar o repositório do autor sobre estruturas de dados e algoritmos para ver as outras soluções dele para diversos problemas.
O autor pode ser encontrado nestas redes sociais: GitHub | Twitter | LinkedIn