Funcionou em 3 casos, então sempre funciona
Conjectura ≠ prova
Exemplos sugerem uma regra, mas não garantem validade geral.
TEMA 22 · LÓGICA E ESTRATÉGIA
Lógica, estratégia e padrões
Resolver um problema estratégico é identificar regras, estados possíveis, objetivos e movimentos que preservam condições. Padrões ajudam a formular conjecturas, mas precisam ser justificados.
Estratégia é mais que tentativa e erro.
Uma boa estratégia reduz o problema a subproblemas menores, procura invariantes e registra o efeito de cada decisão.
Torre de Hanói padrão: usamos três hastes, n discos de tamanhos distintos, movemos apenas um disco por vez e nunca colocamos um disco maior sobre um menor. Nessas condições, para transportar a torre inteira entre duas hastes precisamos mover n−1 discos para a haste auxiliar, deslocar o maior disco e mover os n−1 discos sobre ele. O mínimo satisfaz M(n)=2M(n−1)+1, com M(1)=1, e portanto M(n)=2ⁿ−1.
O número 2ⁿ−1 não é uma fórmula para qualquer variante do problema. Mudar o número de hastes ou as regras de movimento cria outro problema de otimização.
Observar um padrão não é demonstrá-lo.
Escolher sempre o movimento mais curto
Estratégia local pode falhar
O melhor passo imediato nem sempre conduz à solução global.
Ignorar restrições
Estado inválido
Uma solução precisa respeitar todas as regras em cada etapa.
Veja o crescimento do mínimo de movimentos no problema padrão.
O simulador mantém exatamente as hipóteses de três hastes e regras clássicas descritas acima.
Movimentos mínimos15
2^4−1 = 15
Na Torre de Hanói padrão, se 5 discos exigem no mínimo 31 movimentos, quantos exigem 6?
Resolva o subproblema duas vezes e mova o maior disco entre essas duas etapas.