Projetando Algoritmos por Indução

If you wish to make an apple pie from scratch, you must first invent the universe.

Foi Carl Sagan quem disse: se você quiser fazer, do zero, uma torta de maçã, primeiro terá que inventar o universo.

Para fazer uma torta de maçã, cada etapa depende de uma etapa anterior — plantação da macieira, preparo do solo, formação do Sol — até a criação do Universo.

Quando lidamos com programação de computadores, a todo tempo estamos consultando soluções no StackOverflow projetando algoritmos para serem implementados. Para resolver um problema, muitas vezes começamos da estaca zero, sem levar em consideração que soluções de problemas menores podem ajudar na solução do problema maior. Por isso, acabamos “criando todo o universo” para chegar em nosso objetivo.

A metodologia de projeto de algoritmos por indução combina soluções de subproblemas para compor a solução do problema original. Desta forma, não é preciso projetar o algoritmo do zero, a solução desejada é baseada na resolução de problemas iguais, mas menores. Este paradigma de projeto de algoritmos foi proposto por Udi Manber e é análogo à indução matemática — um método de prova de teoremas.

Vá Direto ao Assunto…

Indução Matemática

Suponha que queremos provar um teorema para qualquer número natural . Na indução matemática, em vez de provar diretamente o resultado, é suficiente:

  • Mostrar que o caso base, , vale.
  • Assumir que vale para qualquer valor , nossa hipótese de indução.
  • Mostrar que vale ao usar a hipótese de indução. Chamamos esta etapa de passo de indução.

Como exemplo, vamos utilizar o teorema da soma dos primeiros naturais :

\begin{equation} T(n) = \frac{n^2+n}{2} \end{equation}

Para provar este teorema utilizando a indução matemática, primeiro precisamos provar o caso base, :

\begin{equation} T(1) = \frac{(1^2+1)}{2} = 1 \end{equation}

Como a soma da sequência até o primeiro número natural é o próprio número, é válido.

O próximo passo é estabelecer a nossa hipótese de indução. Vamos supor que vale para todo .

Agora, no passo de indução, devemos utilizar a hipótese de indução de alguma forma para provar o nosso teorema. Se pensarmos em como sendo a soma do -ésimo natural com os naturais anteriores, podemos calculá-lo em termos de :

\begin{equation} T(n) = T(n - 1) + n \end{equation}

Como está coberto pela nossa hipótese de indução (assumimos que ela funciona para todo mundo menor que ), podemos substituir por aquilo que a nossa hipótese de indução diz sobre ele:

\begin{equation} T(n) = \underbrace{\frac{(n - 1)^2 + n - 1}{2}}_{T(n - 1)} + n \end{equation}

Desenvolvendo a expressão, temos:

Exatamente onde queríamos chegar!

Ou seja, para provar , foi preciso apenas mostrar que o caso base é válido e achar uma forma de reduzir o problema em termos de para então aplicar a hipótese de indução. Não foi necessário provar o teorema do zero.

Projetando Algoritmos por Indução

Agora usaremos a mesma ideia para projetar algoritmos. Resolveremos o problema especificando como resolver o caso simples (ou caso base) e utilizaremos soluções de subproblemas para compor a solução definitiva.

Exponenciação Rápida

Queremos calcular o valor de , onde é um natural. Vamos chamar a solução de .

Ao projetar o algoritmo por indução, primeiro especificamos como resolver o caso base . A solução é simples: .

Supondo que sabemos calcular para qualquer , como resolver ?

Simples! Sabemos que .

Ou seja, para resolver , precisamos apenas resolver e multiplicar o resultado por . Agora vem o pulo do gato… Nós já sabemos resolver , pois ela coberta está em nossa hipótese de indução, lembre-se que foi assumido que sabe ser resolvido, logo podemos usar o resultado de para encontrar .

Recapitulando, temos:

Da relação de recorrência acima, tiramos o seguinte algoritmo:

1
2
3
4
5
6
7
8
double exponenciacao(double x, int n)
{
    if (n == 1) {  // Caso base
        return x;
    } else {  // Aplica-se a hipótese de indução para resolver T(n)
        return x * exponenciacao(x, n - 1);
    }
}

Este algoritmo é ineficiente, pois depende de chamadas à função exponenciacao para calcular .

Assim, dizemos que ele leva passos, que grosso modo significa que o tempo que ele leva para calcular o resultado é proporcional ao valor de .

Será que podemos usar o projeto por indução para fazer um algoritmo mais eficiente?

Bom, podemos tentar outra maneira de quebrar em subproblemas.

Se é par, sabemos que . Quando é ímpar, temos que . Mas nossa hipótese de indução cobre tanto quanto , que correspondem respectivamente às soluções de e .

Resumindo, temos:

Desta equação, temos o seguinte algoritmo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double exponenciacao(double x, int n)
{
    double sol;

    if (n == 1) {  // Caso base
        return x;
    } else if (n % 2 == 0) {  // Aplica-se a hipótese de indução quando n é par.
        sol = exponenciacao(x, n / 2);
        return sol * sol;
    } else {  // Aplica-se a hipótese de indução quando n é ímpar.
        sol = exponenciacao(x, (n - 1) / 2);
        return x * sol * sol;
    }
}

O código ficou um pouco mais complicado, mas esse algoritmo é muito mais eficiente que o anterior. Em vez de reduzir o problema de uma unidade, reduzimos pela metade. Desta forma, este algoritmo requer passos para efetuar a exponenciação, o que é muito mais rápido do que passos.

Torre de Hanoi

Outro problema clássico é a da Torre de Hanoi.

O quebra-cabeça começa com 3 estacas. A primeira estaca é chamada de estaca origem e a terceira, estaca destino. Alguns discos são empilhados, do maior para o menor, na primeira estaca, de modo que o menor esteja no topo. A segunda e a terceira estaca estão vazias. Cada disco recebe um número de a de acordo com seu tamanho.

A figura abaixo mostra a configuração inicial de uma Torre de Hanoi com discos:

Configuração inicial

O objetivo do quebra-cabeça é passar todos os discos da primeira para a terceira estaca, obedecendo as seguintes regras:

  • Você pode movimentar apenas um disco por jogada.
  • Uma jogada consiste em mover um disco no topo de uma estaca para outra estaca.
  • Nenhum disco pode ser colocado em cima de outro disco menor.

As imagens a seguir mostram uma solução para o quebra-cabeça com discos:

Solução para o quebra-cabeça com 4 discos.

Com apenas um disco, é muito fácil resolver o problema: basta pegar o disco e colocá-lo na estaca destino. Isto seria o equivalente ao nosso caso base.

Mas como fazer com discos?

Novamente, o segredo é usar a hipótese de indução e assumir que já temos a solução quando o número de discos em uma estaca é menor que :

  1. Resolvemos o problema para os primeiros discos, colocando-os na estaca intermediária e usando a estaca de destino como auxiliar.
  2. Retiramos o maior disco da estaca de origem e o inserimos na estaca de destino.
  3. Resolvemos o problema de mover os primeiros discos da estaca intermediária para a estaca de destino usando a estaca de origem como auxiliar.

Observe que não estamos ferindo as regras do jogo, pois os discos inseridos na estaca de destino sempre são os maiores possíveis. Assim, chegamos ao seguinte algoritmo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

using namespace std;

void hanoi(int n, int origem, int destino, int auxiliar)
{
    if (n == 1) {  // Caso base
        cout << "Movendo o disco " << n << " da estaca " << origem
          << " para a estaca " << destino << "\n";
    } else {
        // Move-se os "n - 1" primeiros discos da estaca origem para a estaca
        // auxiliar utilizando a estaca de destino como auxiliar.
        hanoi(n - 1, origem, auxiliar, destino);

        // Move-se o disco n da estaca origem para a estaca destino
        cout << "Movendo o disco " << n << " da estaca " << origem
          << " para a estaca " << destino << "\n";

        // Move-se os n - 1 primeiros discos da estaca auxiliar para a estaca
        // destino utilizando a estaca origem como auxiliar.
        hanoi(n - 1, auxiliar, destino, origem);
    }
}

int main()
{
    int n;
    cout << "Digite o número de discos: ";
    cin >> n;
    hanoi(n, 1, 3, 2);
}

Perceba que não foi preciso projetar o algoritmo do zero. Apenas foram especificados o caso base e como reduzir o problema de mover discos para a partir da solução de dois subproblemas que movimentavam discos.

Considerações Finais

Usando o projeto de algoritmos por indução, aprendemos como solucionar um problema através das soluções dos seus subproblemas.

O caso base sustenta toda a indução matemática e, por analogia, os algoritmos projetados via indução. Se o caso base for demonstrado incorreto, todo o projeto do algoritmo cai por água abaixo.

Essa metodologia facilita a escrita de algoritmos complexos e nos dá uma intuição bem forte de que eles estão corretos, já que a descrição do algoritmo está em uma linguagem bem próxima daquela utilizada para a demonstração de sua correção.

O projeto de algoritmos por indução naturalmente leva a definições recursivas. Apesar disso, eles não precisam ser implementados desta forma. Para melhorar o desempenho, podemos criar versões iterativas desses algoritmos com laços de repetição.

Apesar de não servir para todos os problemas, é interessante ter esta abordagem de projeto de algoritmos em seu repertório.

Referências

  • Manber, Udi. “Using induction to design algorithms.” Communications of the ACM 31.11 (1988): 1300-1313.

  • Manber, Udi. Introduction to algorithms: a creative approach. Vol. 4. Reading, MA: Addison-Wesley, 1989.

Comentários desabilitados...