Torres de Hanói

Agora, vamos resolver indutivamente o problema das Torres de Hanói. Muita gente conhece o jogo, mas não sabe como resolvê-lo computacionalmente. As regras são as seguintes:

1. Devemos mover um disco de cada vez.
2. Um disco maior não pode ser colocado sobre um disco menor.

Usando indução, a solução computacional para o problema é quase trivial.

Idéia indutiva:

• Caso Base: para zero disco, o problema já está resolvido.
• Hipótese de Indução: vamos supor que o problema pode ser resolvido para n - 1 elementos. Esse truque libera o disco da base (maior disco).
• Caso Geral: basta invocar a hipótese de indução para mover os n- 1 discos e liberar o disco maior, e em seguida, invocamos a H.I. novamente para mover os n - 1 discos para o destino.

Para esclarecer, vamos analisar um exemplo:

Situação inicial: todos os discos estão em A.

Hipótese de indução 1: vamos supor que os n - 1 discos iniciais serão movidos para o pino C.

Caso trivial: agora ficou fácil mover o disco maior para o destino, ou seja, para o pino B.

Hipótese de indução 2: agora vamos supor que os n - 1 discos que estão em C serão movidos para B.

E assim, chegamos a solução do problema!!!

As implementações decorrem da idéia apresentada acima.

• Implementação em Python

def hanoi(n, A, B, C):
  if n > 0:
    hanoi(n - 1, A, C, B)
    print "Mova o disco " + str(n) + " de " + A + " para " + B
    hanoi(n - 1, C, B, A)

• Implementação em Java

static void hanoi(int n, char A, char B, char C) {
  if (n > 0) {
    hanoi(n - 1, A, C, B);
    System.out.println("Mova o disco " + n + " de " + A + " para " + B);
    hanoi(n - 1, C, B, A);
  }
}

Complexidade do algoritmo: vamos derivar a relação de recorrência T(n) = 2T(n - 1) + 1.

$T(n) = 2T(n - 1) + 1$
$T(n) = 2(2T(n - 2) + 1) + 1$
$T(n) = 4T(n - 2) + 2 + 1$
$T(n) = 4(2T(n - 3) + 1) + 2 + 1$
$T(n) = 8T(n - 3) + 4 + 2 + 1$
$...$
$T(n) = 2^n + 2^{n - 1} + 2^{n - 2} + ... + 2^2 + 2^1 + 2^0$
$T(n) = 2^n - 1$
$T(n) = O(2^n)$

Podemos concluir que a complexidade do algoritmo é limitada pela função exponencial. Na prática, se o número de discos for muito grande, a obtenção de uma solução torna-se inviável.