Better Split Towers of Hanoi
Surpreendentemente, nossa solução de dividir (split) as torres gera
muito mais movimentos que a solução de intercalar elas. 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 |
Você 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ós 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, você 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 (chamando recursivamente sua função
principal).
- Então mova o disco branco grande para sua vara objetivo.
- Então mova os (n-1) discos brancos menores para o 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.