22 moves suffice

[Carlos de Alcântara 2.765]

Comprovada a possibilidade de resolver o cubo mágico a partir de qualquer posição em 22 movimentos. Segue artigo traduzido por Pepperoach:

"Com um total de 1.28 milhões de posições resolvidas, nós demonstramos que toda posição do Cubo Mágico pode ser resolvida em 22 ou menos movimentos.

Foi necessária uma quantidade absurda de CPUs contribuídos por John Welborn e Sony Pictures Imageworks.

Não foram encontradas posições a 21 movimentos da solução na pesquisa, apesar de ter resolvido mais de 25 sextilhões de posições.

Há um pequeno artigo na New Scientist (edição de 9 de Agosto) a respeito dessa pesquisa e desse resultado.

A mesma idéia da prova dos 25 movimentos foi usada, desta vez com muito mais computadores.

Eu encontrei 310 posições a 18, e aproximadamente 82,000 a 19 movimentos da solução; todas as outras estavam a 20 ou menos.

Agradeço profundamente a John Welborn, Sony Pictures Imageworks, Herbert Kociemba, e Silviu Radu, e muitos outros que me ajudaram durante os últimos anos.

Chegou a hora atualizar os documentos!"

(fonte: http://cubezzz.homelinux.org/drupal/?q=node/view/121 )

[Willian 230]

E o Cube Explorer??

[Carlos de Alcântara 2.765]

antes eu tinha essa mesma pergunta, quando eram uns 26 ou 27 movimentos

agora que são 22 eu tenho minhas dúvidas se o cube explorer ainda dá conta do recado

mas não sei a média de movimentos que ele dá como solução, não costumo usar muito o programa

e que é estranho eles precisarem de "milhões" de computadores prá fazer o que o cube explorer faz, isso é

[Pedro 279]

antes eu tinha essa mesma pergunta, quando eram uns 26 ou 27 movimentos

agora que são 22 eu tenho minhas dúvidas se o cube explorer ainda dá conta do recado

mas não sei a média de movimentos que ele dá como solução, não costumo usar muito o programa

e que é estranho eles precisarem de "milhões" de computadores prá fazer o que o cube explorer faz, isso é

eles usaram muitos computadores pra pesquisar bilhões de casos de cubo

o cube explorer acha a solução ótima, mas não tem como vc afirmar que todas as 43 quintilhões de posições são resolvíveis em 22 movimentos só pq as poucas que vc pos no cube explorer foram;)

[Carlos de Alcântara 2.765]

por que 'bilhões'? não pesquisam todas as possibilidades?

eu falei que me parecia bem claro que o cube explorer era melhor quando eram 26 ou 27 movimentos, e disse que sobre 22 já não tenho muita certeza se ele dá conta

e as poucas que eu pus no explorer são o bastante prá mostrar que a possibilidade de acontecer de encontrar uma com solução longa (maior que 27 movimentos) é mínima. Nosso ponto é que um "simples" software consegue se equiparar com esses estudos de dimensões astrológicas

[Pedro 279]

por que 'bilhões'? não pesquisam todas as possibilidades?

eu falei que me parecia bem claro que o cube explorer era melhor quando eram 26 ou 27 movimentos, e disse que sobre 22 já não tenho muita certeza se ele dá conta

e as poucas que eu pus no explorer são o bastante prá mostrar que a possibilidade de acontecer de encontrar uma com solução longa (maior que 27 movimentos) é mínima. Nosso ponto é que um "simples" software consegue se equiparar com esses estudos de dimensões astrológicas

acho que eles usam "cosets", que devem ser conjuntos de casos simétricos/isomórficos/whatever

[StarKad 0]

O cube explorer não procura a solução ótima, ele usa um algoritmo de duas etapas chamado de algoritimo de Kociemba, que pode achar a solução ótima, mas nem sempre.

Ele não acha a solução de 20 movimentos do superflip[1], por exemplo.

[1]posição em que todos os meios estão no lugar certo e com a orientação errada.

[Eduardo Alex 0]

Basicamente, os super computadores selecionam alguns bilhares de casos e tentam aplicar algorítmos predeterminados qe levam a posições em que prováveis 10 ou menos movimentos seriam necessários para se resolver?

(nesse caso se não cair em um desses casos ele o classifica como superior a x movimentos...)

Ou eles pegam um caso específico e tentam centenas de algoritmos até se achar o mais rápido?

Onde está lógica destes algorítmos?

1: No caso algorítmos foram inteligentemente inventados (por meios de tentantivas e observações) pelos proprios computadores?

ou...

2: por equações matemáticas criadas pelo Homem?

alguém sabe? rs

expliquei direito?

abraço

ateh!

[bbzinhodomal 0]

Será q U2, conta como apenas 1 ou dos movimentos?

O movimento, S, M, M', conta como 1 ou 2 movimentos?

[Pedro 279]

Será q U2, conta como apenas 1 ou dos movimentos?

O movimento, S, M, M', conta como 1 ou 2 movimentos?

U2 = 1 movimento

S, M e E = 2

[Willian 230]

Isso no Half Metric.

Sei que tem 3 tipos diferentes de contar movimentos, não lembro quais são. Mas o que a WCA usa é o half.

[fauseta 1]

porque u2 conta como 1 movimento soh?

[Carlos de Alcântara 2.765]

tem vários jeitos de medir... nesse aí, o que é considerado é o giro da face. Aí mesmo se fosse U3 seria considerado como um movimento só

acho que não tem um motivo específico, são só maneiras diferentes analisar

acredito que essa é a métrica mais usada porque meio que considera o mais importante, porque contar cada giro da face acaba contando muito giro prá pouco resultado =]

[fauseta 1]

ahhhh saquei ...

=) valeu

[Pepperoach 1]

Uma tradução decente aí pra vocês XD (por mim mesmo)

"Com um total de 1.28 milhões de posições resolvidas, nós demonstramos que toda posição do Cubo Mágico pode ser resolvida em 22 ou menos movimentos.

Foi necessária uma quantidade absurda de CPUs contribuídos por John Welborn e Sony Pictures Imageworks.

Não foram encontradas posições a 21 movimentos da solução na pesquisa, apesar de ter resolvido mais de 25 sextilhões de posições.

Há um pequeno artigo na New Scientist (edição de 9 de Agosto) a respeito dessa pesquisa e desse resultado.

A mesma idéia da prova dos 25 movimentos foi usada, desta vez com muito mais computadores.

Eu encontrei 310 posições a 18, e aproximadamente 82,000 a 19 movimentos da solução; todas as outras estavam a 20 ou menos.

Agradeço profundamente a John Welborn, Sony Pictures Imageworks, Herbert Kociemba, e Silviu Radu, e muitos outros que me ajudaram durante os últimos anos.

Chegou a hora atualizar os documentos!"

Um pouco tarde, mas cheguei agora no forum

[Carlos de Alcântara 2.765]

heuheuh valeu a boa vontade, vou substituir esse texto na mensagem principal do tópico então. dá uma olhada lá

[Pedro Fernandes 1]

valeu Pepperoach!!