Existem máximos locais no número de movimentos necessários para resolver um cubo de Rubik?

22

Peter Shor levantou um ponto interessante em relação a uma tentativa de responder a uma pergunta anterior sobre a complexidade de resolver o cubo Rubiks. Eu havia postado uma tentativa bastante ingênua de mostrar que ela deveria estar contida no NP. Como Peter apontou, minha abordagem falha em alguns casos. Um caso potencial de tal instância é onde existe um máximo local no comprimento do caminho. Por este Quer dizer que ele pode tomar movimentos para resolver o cubo de configuração , e quer ou move-se para resolver o cubo a partir de qualquer posição que pode ser alcançada em um movimento a partir de . Agora, isso não é necessariamente um problema seS A A S A S A - 1 A S An×n×nSAASASA1ASAé o número máximo de movimentos necessários para resolver o cubo em geral ( o número de Deus para esse cubo), mas é definitivamente um problema se SA for estritamente menor que o número de Deus para esse cubo. Então, minha pergunta é: existem tais máximos locais? Mesmo uma resposta para o cubo 3×3×3 seria interessante para mim.

Joe Fitzsimons
fonte
Embora eu não tenha um exemplo, eu ficaria surpreso se não houver, porque isso parece implicar que podemos calcular o número de Deus apenas encontrando uma configuração que seja um máximo local (embora esse argumento não seja rigoroso).
Tsuyoshi Ito
@Tsuyoshi Ah, mas talvez não se saiba se havia ou não máximos locais até depois que o número de Deus foi calculado! Mas concordo que espero que esses máximos locais existam. Só não sei ao certo e estaria interessado em descobrir.
Joe Fitzsimons
@ Joe: Sim, isso é exatamente o que não é rigoroso sobre o meu argumento. Eu ficaria mais rigorosamente surpreso :) se for possível provar que não existem máximos locais sem realizar a pesquisa exaustiva.
Tsuyoshi Ito
1
@Tsuyoshi Parece que o máximo local não pode ocorrer por comprimentos de caminho muito curtos, e parece provável que exista próximo ao número de Deus, e é por isso que acho que não é tão claro que eles existem.
Joe Fitzsimons
1
Eu sei que os gráficos de Cayley para grupos arbitrários podem ter máximos locais. Eu esqueço onde vi esse resultado, mas tenho certeza de que vi em algum lugar. Portanto, a menos que o grupo de cubos de Rubik seja de alguma forma especial, espera-se que ele tenha máximos locais também.
quer

Respostas:

9

Ao fazer a Tomas Rokicki esta pergunta, imediatamente deu a resposta correta ("sim, existem máximos locais"):

Se uma posição exibe simetria total, é necessariamente um máximo local (todos, exceto o início). Um pouco de reflexão deve deixar claro por que esse é o caso na QTM [métrica de um quarto de volta]. Para o HTM [métrica de meia volta], é um pouco mais sutil, mas não muito ruim.

...

Essa posição é pons asinorum, que é a distância 12 em QTM e a distância 6 em HTM (U2D2F2B2L2R2).

Não vejo por que esse é o caso da métrica de meia volta; mas para a métrica de um quarto de volta, é claro. Em uma posição com simetria total, todas as posições vizinhas devem ter o mesmo comprimento de caminho (já que todos os movimentos são equivalentes por simetria). Portanto, uma posição com simetria total deve ser um máximo local ou um mínimo local estrito. Mas mínimos locais estritos não podem existir ... deve haver algum movimento que reduza a distância ao estado resolvido, apenas pela definição da distância. O argumento de simetria se traduz no cubo , assim como a posição de exemplo fornecida.n×n×n

mjqxxxx
fonte
Que argumento simples, isso é brilhante!
Hsien-Chih Chang
Excelente, esse é um argumento muito bom!
Joe Fitzsimons
2

Aqui está um argumento extremamente heurístico que sugere onde os máximos locais podem ser encontrados. Seja o número de posições que exigem exatamente movimentos para resolver. Cada movimento dessa posição leva o cubo para a distância , ou ; portanto, há um total de posições acessíveis. Existem movimentos de cada posição, levando a novas posições; uma posição na distância é o máximo local quando nenhuma dessas posições está na distância d d - 1 d d + 1 N d - 1 + N d + N d + 1 M M d M d + 1Nddd1dd+1Nd1+Nd+Nd+1MMdMd+1. Se considerarmos que essas posições são desenhadas uniformemente aleatoriamente a partir das posições acessíveis (que, é claro, elas não são; essa é a parte heurística), temos:

Xd=P[ a given position at d is a local max ]=(Nd1+NdNd1+Nd+Nd+1)M=(1+Nd+1Nd1+Nd)M.

O número esperado de máximos locais na distância é .dNdXd

Para o cubo , o número de movimentos de uma determinada posição é e as estimativas para são fornecidas no Número de Deus é 20 . Usando esses valores, descobrimos que o número esperado de máximos locais é , e . Portanto, é improvável que exista um máximo local para . Em , o número total de posições é estimado em , portanto, pode-se esperar testar um bilhão de posições antes de encontrar um máximo local. Finalmente, em3×3×3M=18NdN16X16=0.2N17X17=9×109N18X18=1.5×1019d16d=1712×1018d=18, espera-se um máximo local em cada vinte posições.

mjqxxxx
fonte
Obrigado. No entanto, não está claro para mim que é o número correto de estados acessíveis a partir dos estados da distância . Se, por exemplo, houver máximos locais da distância isso parece não se sustentar. Também parece quebrar para qualquer estado de distância para o qual todos os estados vizinhos tenham distância ou , pois esse estado não pode ser alcançado em 1 movimento de qualquer um dos estados da distância . Não tenho ideia de quão comuns ou raras serão essas situações. N d d d - 1 d d - 1 d + 1 dNd1+Nd+Nd+1Nddd1dd1d+1d
Joe Fitzsimons