génération de séquence / largeur première recherche

Question

Essentiellement ce que je fais est d'essayer de résoudre un cube de Rubik avec une première recherche étendue de tous les mouvements possibles. Je sais que ce n'est pas la meilleure façon de résoudre le cube, mais je ne ai besoin pour des séquences très courtes (de sorte que la profondeur de la recherche est peu susceptible d'être plus profond que 3), et je ne suis pas besoin de quoi que ce soit magasin autre que la séquence en cours.

Je suis en train de trouver un moyen d'imprimer des chaînes toujours croissant de nombre (0,1,2,00,01,02 ...), donc je peux brancher chacun en fonction de vérifier si ce séquence particulière de mouvements permet de résoudre le cube, mais je vais avoir du mal à trouver un moyen de poursuivre la séquence indéfiniment.

Jusqu'à présent, tout ce que j'ai réussi est imbriqué pour les boucles, mais il doit y avoir une autre boucle à chaque fois que la recherche devient plus profonde. Est-ce que quelqu'un a une idée comment je peux aborder ce problème?

Désolé si je suis trop vague, je pourrais écrire un essai sur ce que je suis en train de faire, mais que je vais essayer et rester simple.

Answer 1

Je ne suis pas très au courant de ce qui est dans les bibliothèques Java, donc des excuses si cela est la mise en œuvre quelque chose qui est déjà là, mais si je devais écrire ce à partir de zéro, je ferais probablement quelque chose comme ceci:

public class Enumerator {
    private int maxDepth;
    private int currentDepth;
    private int currentPerm;
    private String alphabet;

    public Enumerator(String alphabet, int d) {
        this.maxDepth = d;
        this.currentDepth = 1;
        this.currentPerm = 0;
        this.alphabet = alphabet;
    }

    public boolean next() {
        int numPermutations = (int) Math.pow(alphabet.length(), this.currentDepth);
        boolean res=false;

        // finished if
        if ((this.currentDepth == this.maxDepth) && 
            (this.currentPerm == numPermutations - 1)) {
            res = false;
        }
        // next perm at this depth
        else if (this.currentPerm < numPermutations - 1) {
            this.currentPerm++;
            res = true;
        }
        // next depth
        else if (this.currentDepth <= this.maxDepth) {
            this.currentDepth++;
            this.currentPerm = 0;
            res = true;
        }
        return res;
    }

    public String getPermutation() {
        int tmpPerm = this.currentPerm;
        String res = "";
        for (int i=0; i<this.currentDepth; i++) {
          int ind = tmpPerm % this.alphabet.length();
          res = this.alphabet.charAt(ind) + res;
          tmpPerm /= this.alphabet.length();
        }
        return res;
    }

    public static void main(String args[]) {
        int depth = 3;
        String alphabet = "012";
        Enumerator e = new Enumerator(alphabet, depth); 
        do {
            System.out.println(e.getPermutation());
        } while (e.next());
    }
}

De cette façon, vous pouvez énumérer les séquences d'alphabets de symboles arbitraires à une profondeur arbitraire. Cela fait aussi ce que vous voulez dans la mesure où elle effectue une itération sur la profondeur et pour chaque profondeur génère l'ensemble des séquences possibles. Il pourrait également être fait avec récursion, comme le dit Gian, qui pourrait être plus élégant. En Python j'utiliser une fonction de générateur pour cela, mais je ne suis pas au courant de quelque chose de similaire à Java.

Answer 2

On dirait que vous voulez une solution récursive, de sorte que votre fonction génère une liste de mouvements de successeur donné une séquence en entrée, dans ce cas, vous pouvez simplement continuer à appeler la fonction sur sa propre sortie autant de fois que nécessaire.

Answer 3

ne serait pas une fonction récursive faire cela? Vous pouvez limiter la profondeur de récursivité et d'approfondir progressivement.

[Mise à jour] Passe la fonction d'un int spécifiant la profondeur; chaque fois que vous RECURSE, décrémenter la valeur -. vérifier si elle est égale à zéro, et le retour si oui

Pour les valeurs, passer une collection de chaînes ou stringbuilders dans la fonction récursive. Chaque niveau se lit (et supprime) les valeurs du niveau précédent, ajoute tous les possibles prochains mouvements et les lieux les résultats de retour dans la collection ( en fait, vous pouvez le faire de manière itérative plutôt que récursive si vous voulez ) .

Level 1 generates 0,1,2,...

Level 2 removes 0 and replaces it with 00,01,02,...
Level 2 removes 1 and replaces it with 10,11,12,...
etc

Answer 4

Une file d'attente FIFO pourrait être une meilleure approche que récursion, comme le suggère l'article de Wikipédia sur la recherche en largeur: http://en.wikipedia.org/wiki/Breadth_first_search .

Ma solution en C #:

string SolveRubiks()
{
    string[] singleMoves = {"0","1","2"};
    Queue<string> queue = new Queue<string>(singleMoves);
    while (true)
    {
        string moveSequence = queue.Dequeue();
        if (isSolution(moveSequence))
        {
            return moveSequence;
        }
        foreach (string singleMove in singleMoves)
        {
            queue.Enqueue(moveSequence + singleMove);
        }
    }
}

Si vous avez besoin d'un itérateur, vous pouvez échanger le si bloc avec un rendement de rendement et changer la signature de la méthode, en Java, je suppose que vous devrez implémenter une interface iterator (similaire à la classe de Philippe Uren).