Indexation dans une base de données de modèles - Solution Optimal Rubik's Cube de Korf

11

Comme projet amusant, j'ai travaillé sur une implémentation C # de Richard Korf - Trouver des solutions optimales pour le cube de Rubik en utilisant des bases de données de modèles.

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

Je le fais fonctionner, j'essaie juste d'améliorer ma solution.

Une chose que Korf glaçure dans son article est la façon dont il stocke et indexe dans les bases de données de modèles. Idéalement, je pense que nous voulons utiliser une instance d'un cube rubik pour générer un index dans un tableau.

Ma question porte sur la meilleure façon de générer cet index.

Ma solution est de générer un hachage parfait minimal. Cela implique de garder TOUS les cubes en mémoire jusqu'à ce que j'aie découvert la base de données de motifs entière, puis de générer un hachage parfait minimal basé sur cela. Le MPH prend quelques heures à fonctionner en fonction de la taille de la base de données de modèles, mais je n'ai besoin de le faire qu'une seule fois depuis que je l'ai enregistré sur le disque. En fin de compte, je peux jeter les cubes eux-mêmes en ne stockant que le MPH. De cette façon, je peux prendre un cube de Rubik aléatoire, appliquer le modèle, puis rechercher l'index du tableau dans le MPH pour obtenir une longueur de solution estimée.

Je crois que Korf et Shultz décrivent une meilleure façon de déterminer l'indice du cube dans leur article de 2005 intitulé "Large Scale Breadth-First Search"

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

Cet article décrit un algorithme pour générer un indice basé sur l'ordre lexicographique d'une permutation. Fondamentalement, vous pouvez prendre la permutation {1, 2, 3} et comprendre que c'est la plus petite avec un indice de 0. {1, 3, 2} est ensuite avec un indice de 1 et ainsi de suite.

Je pense que je devrais être en mesure d'appliquer cet algorithme à un cube rubik pour obtenir son index dans une base de données de modèles, mais j'ai du mal à comprendre comment cela fonctionnerait dans la pratique.

Par exemple, la base de données des coins uniquement contient tous les cubes de rubik dont les autocollants de bord ont été enlevés. Il y a exactement 88 179 840 cubes dans cet ensemble. Tout coin cubie sur un cube rubiks peut être dans l'un des 24 états différents. L'état du 8e coin peut être calculé sur la base des 7 autres, donc les cubes dans la base de données des motifs uniquement des coins ont chacun 7 valeurs comprises entre 0 et 23

Par exemple {0, 3, 6, 9, 12, 15, 18, 21} définit le cube "résolu" avec tous les autocollants de bord supprimés.

si je fais pivoter la face avant de 90 degrés, la permutation pourrait être: {0, 3, 11, 23, 12, 15, 8, 20}

Existe-t-il un moyen d'extraire un indice de ce type de permutations?

Cosmosis
la source
Vous trouverez probablement cela intéressant.
Tom van der Zanden
intéressant! vous dites qu'il "glaçure" quelque chose dans le papier. il serait préférable d'être plus précis sur la section qui n'est pas "étoffée". vous dites également que cela fonctionne. quelle est votre implémentation d'indexation initiale? est-ce un projet d'école? suggérer davantage de chat informatique à ce sujet. aussi, par exemple, bloguer à ce sujet ou open source, le code peut être utile aux autres et conduire à plus de détails. aussi le document ne semble pas faire référence à des fonctions de hachage ...
vzn
J'ai implémenté l'algorithme de Korf: github.com/benbotto/rubiks-cube-cracker . Moi aussi, j'ai trouvé l'indexation difficile, j'ai donc écrit un article à ce sujet sur Medium: medium.com/@benjamin.botto/…
avejidah

Réponses:

6

(pi,oi)(p0,,p7)(0,,7)oi{0,1,2}o7o0,,o68!3sept=88179840{0,,23}(pje,oje)(p0,,psept)o0,,o63septp+o8!o+p

Yuval Filmus
la source
Hé Yuval, merci pour le commentaire. Pour moi, 0 à 23 sont la façon dont j'identifie la position / orientation unique dans laquelle un cube d'angle peut être. 8 positions fois 3 orientations par position = 24. Heureusement, je peux facilement diviser cette valeur en tuples de position / orientation séparés. Votre réponse m'a conduit à ce code qui est une implémentation de l'algorithme que vous décrivez. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c Je vais devoir faire un peu de travail pour le rendre plus générique (afin que je puisse gérer des motifs différents des "coins uniquement") mais maintenant Im sur la bonne voie thx!
Cosmosis