Better Split Towers of Hanoi
Surpreendentemente, a nossa solução de dividir (split) as torres gera muito
mais movimentos que a solução de intercalá-las. Como os problemas são
simétricos, isto não deveria acontecer.
Quantidade de discos | Intercalada | Split |
5 pares | 62 movimentos | 88 movimentos |
6 pares | 126 movimentos | 183 movimentos |
7 pares | 254 movimentos | 374 movimentos |
Consegue deixar o "split" tão eficiente quanto o intercalada?
A fonte de discrepância é uma decomposição ineficiente do
problema. Satisfeitos com o fato dele simplesmente funcionar, não procuramos
mais por uma solução melhor. Manter os discos da torre intercalada na ordem
correta durante cada movimento é desnecessário. De fato, podemos evitar
completamente mover a torre intercalada. Uma decomposição melhor do problema
divide o par de discos em duas torres coloridas à medida em que eles são
removidos da torre intercalada.
Se alguém puder dividir os (n-1) pares de discos previamente, poderia
dividir o par restante?
- Primeiro divida os primeiros (n-1) pares de discos da pilha intercalada em
uma torre branca e uma torre preta (a chamar recursivamente a sua função
principal).
- Então mova o disco branco grande para sua vara objetivo.
- Então mova os (n-1) discos brancos menores ao topo do maior.
- Então mova o disco preto grande para sua vara objetivo.
- Então mova os discos pretos pequenos para a posição.