Indexando em um banco de dados padrão - a solução ideal para cubos de rubik da Korf

11

Como um projeto divertido, eu tenho trabalhado na implementação em C # de Richard Korf - Encontrar soluções ideais para o cubo de Rubik usando bancos de dados padrão.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

Na verdade, estou funcionando, só estou tentando melhorar minha solução.

Uma coisa que Korf examina em seu artigo é como ele armazena e indexa nos bancos de dados de padrões. Idealmente, acho que queremos usar uma instância do cubo de um rubik para gerar um índice em uma matriz.

Minha pergunta é sobre a melhor maneira de gerar esse índice.

Minha solução é gerar um hash perfeito mínimo. Isso envolve manter TODOS os cubos na memória até que eu descubra o banco de dados de padrões inteiro, gerando um hash mínimo perfeito com base nisso. O MPH leva algumas horas para ser executado, dependendo do tamanho do banco de dados padrão, mas eu preciso fazê-lo apenas uma vez desde que o salve no disco. No final, eu posso jogar fora os próprios cubos armazenando apenas o MPH. Dessa forma, eu posso pegar um cubo de rubik aleatório, aplicar o padrão e procurar o índice da matriz no MPH para obter um tamanho estimado da solução.

Acredito que Korf e Shultz descrevem uma maneira melhor de determinar o índice do cubo em seu artigo de 2005 chamado "Pesquisa em Larga Escala em Primeira Escala"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Este artigo descreve um algoritmo para gerar um índice baseado na ordem lexicográfica de uma permutação. Basicamente, você pode usar a permutação {1, 2, 3} e descobrir que é o menor com um índice de 0. {1, 3, 2} é o próximo com um índice de 1 e assim por diante.

Eu sinto que deveria ser capaz de aplicar esse algoritmo ao cubo de um rubik para obter seu índice dentro de um banco de dados padrão, mas estou tendo dificuldade em descobrir como funcionaria na prática.

O único banco de dados de padrões de cantos, por exemplo, contém todos os cubos de rubik que tiveram seus adesivos de borda removidos. Existem exatamente 88.179.840 cubos neste conjunto. Qualquer cubo de canto em um cubo de rubiks pode estar em um dos 24 estados diferentes. O estado do 8º cubo de canto pode ser calculado com base nos outros 7, portanto, os cubos nos bancos de dados de padrão somente de cantos têm 7 valores entre 0 e 23

por exemplo, {0, 3, 6, 9, 12, 15, 18, 21} define o cubo "resolvido" com todos os adesivos de borda removidos.

se eu girar a face frontal em 90 graus, a permutação pode ser: {0, 3, 11, 23, 12, 15, 8, 20}

Existe uma maneira de obter um índice desse tipo de permutação?

Cosmosis
fonte
Você provavelmente achará isso interessante.
Tom van der Zanden
interessante! você diz que ele "encobre" algo no jornal. seria melhor ser mais específico sobre a seção que não é "detalhada". você também diz que está funcionando. qual é a sua implementação inicial de indexação? este é um projeto da escola? sugerir mais bate - papo sobre ciência da computação . também, por exemplo, escrever um blog sobre o assunto ou abrir o código pode ser útil para outras pessoas e gerar mais detalhes. também o papel não parecem referir-se a quaisquer funções hash ...
vzn
Eu implementei o algoritmo do Korf: github.com/benbotto/rubiks-cube-cracker . Também achei a indexação difícil, então escrevi um artigo sobre isso no Medium: medium.com/@benjamin.botto/…
avejidah

Respostas:

6

(pi,oi)(p0,,p7)(0,,7)oi{0,1,2}o7o0,,o68!37=88179840{0,,23}(pi,oi)(p0,,p7)o0,,o637p+o8!o+p

Yuval Filmus
fonte
Hey Yuval, obrigado pelo comentário. Para mim, de 0 a 23 é como identifico a posição / orientação exclusiva em que um cubo de canto pode estar. 8 posições vezes 3 orientações por posição = 24. Felizmente, posso facilmente dividir esse valor em tuplas de posição / orientação separadas. Sua resposta me levou a este código, que é uma implementação do algoritmo que você está descrevendo. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c Precisarei trabalhar um pouco para tornar isso mais genérico (para que eu possa lidar com padrões diferentes de "apenas cantos"), mas agora Estou no caminho certo thx!
precisa