SÃO PAULO – Com a ajuda de supercomputadores do Google, matemáticos provam que qualquer combinação no cubo-mágico pode ser resolvida em apenas 20 movimentos.
Processando todas as 43.252.003.274.489.856.000 de configurações possíveis, Morley Davidson, da Kent State University, John Dethridge, engenheiro do Google, Herbert Kociemba, professor de matemática da Alemanha, e Tomas Rokicki, programador da Califórnia, descobriram o número máximo para solucioná-las.
Esse chamado “número de Deus” já havia sido proposto, porém nenhum grupo havia conseguido provar que todas as possibilidades do objeto poderiam ser resolvidas com duas dezenas ou menos de movimentos.
Na verdade, apenas cerca de 300 milhões de possibilidades precisam de 20 movimentos. A maioria requer entre 15 e 19 (veja tabela na próxima página).
Esta foi a combinação mais difícil para os computadores resolverem
O Google não revele os detalhes de suas super máquinas utilizadas, mas os pesquisadores fazem uma comparação em seu site: com um bom PC (como o Intel Nehalem, de quatro núcleos com freqüência de 2,8 GHz), seriam necessário 1,1 bilhão de segundos, ou cerca de 35 anos, para fazer esses cálculos.
Como calcular 43.252.003.274.489.856.000 combinações?
Mesmo os computadores de Mountain View teriam trabalho lidando com um número tão grande. Por isso, a equipe teve que dividir as combinações em 2.217.093.120 grupos de 19.508.428.800 diferentes posições.Dessa forma, cada um desses subproblemas era pequeno o bastante para caber na memória – e a maneira como eles foram quebrados, matematicamente, permitiu resolver cada etapa rapidamente.
Simetria
O próximo passo foi cortar etapas desnecessárias. Se você pegar um cubo embaralhado e virá-lo de ponta cabeça, não terá alterado em nada sua dificuldade, pois ele ainda levará o mesmo número de movimentos para ser resolvido. Na hora de calcular, ao invés de resolver essas duas posições, a equipe viu que poderia simplesmente resolver uma e virá-la de cabeça para baixo. Há 24 diferentes maneiras para se orientar um cubo no espaço, portanto, usando essas simetrias, foi possível diminuir o número de problemas a serem resolvidos de 2.217.093.120 para 55.882.296.
Otimização
A “solução otimizada” tem uma definição bem óbvia: é aquela que não requer mais movimentos do que o necessário. Parece óbvio, mas não é simples realizar, ou calcular, o mínimo de movimentos possíveis. Ao invés de resolver de forma otimizada todos os problemas, os pesquisadores programaram seus algoritmos para buscar soluções que precisavam de 20 ou menos movimentos.
Dessa forma, pela primeira vez, um grupo conseguiu provar que todas as combinações do cubo mágico pode ser resolvidas em, no máximo, 20 etapas. Agora, os quatro colegas aguardam que uma equipe independente confirme seus resultados.
Fonte: Aqui
Nenhum comentário:
Postar um comentário
Postem aqui