generazione Sequenza / ampiezza prima ricerca

Question

In sostanza quello che sto facendo sta cercando di risolvere un cubo di Rubik con una ricerca in ampiezza di tutte le possibili mosse. So che questo non è il modo migliore per risolvere il cubo, ma ho solo bisogno per le sequenze molto brevi (così la profondità della ricerca è improbabile che sia più profondo di 3), e non ho bisogno di memorizzare qualcosa di diverso la sequenza corrente.

Sto cercando di trovare il modo di stampare sempre crescente numero di stringhe (0,1,2,00,01,02 ...), quindi posso solo collegare ognuno in una funzione per verificare se questo particolare sequenza di mosse risolve il cubo, ma sto avendo difficoltà a trovare un modo di continuare la sequenza a tempo indeterminato.

Finora tutto quello che sono riuscito è annidato cicli for, ma ci deve essere un altro ciclo ogni volta che la ricerca diventa più profonda. Qualcuno ha qualche idea di come posso affrontare questo problema?

Scusate se sono stato troppo vago, potrei scrivere un saggio su quello che sto cercando di fare, ma ho pensato di cercare di mantenere le cose semplici.

Answer 1

Io non sono molto familiare con ciò che è nelle librerie Java, quindi mi scuso se questo è attuare qualcosa che è già lì, ma se dovessi scrivere questo da zero, probabilmente sarei fare qualcosa di simile:

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());
    }
}

In questo modo è possibile enumerare sequenze da alfabeti di simboli arbitrari ad una profondità arbitraria. Questo fa anche quello che vuoi in quanto itera sulla profondità e per ogni profondità genera il set completo di possibili sequenze. Potrebbe anche essere fatto con la ricorsione, come dice Gian, che potrebbe essere più elegante. In Python Userei una funzione generatore per questo, ma io non sono a conoscenza qualcosa di simile a Java.

Answer 2

Sembra che si desidera una soluzione ricorsiva, in modo tale che la funzione genera un elenco di successore mosse dato una sequenza come input, nel qual caso si può solo continuare a chiamare la funzione sul proprio output come tutte le volte che è necessario.

Answer 3

Non sarebbe una funzione ricorsiva fare questo? È possibile limitare la profondità di ricorsione e gradualmente approfondirla.

[Aggiornamento] Passo la funzione di un int che specifica la profondità; ogni volta che si ricorsione, diminuire il valore. - Controllare se è pari a zero, e di ritorno, se così

Per i valori, passare una raccolta di stringhe o stringbuilders nella funzione ricorsiva. Ogni livello si legge (e rimuove) i valori del livello precedente, aggiunge tutte le possibili mosse successive e luoghi i risultati indietro nella collezione ( in effetti, si potrebbe fare questo in modo iterativo, piuttosto che in modo ricorsivo se si voleva ) .

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

Una coda FIFO potrebbe essere un approccio migliore di ricorsione, come suggerito dal l'articolo di Wikipedia sulla ricerca in ampiezza: http://en.wikipedia.org/wiki/Breadth_first_search .

La mia soluzione in 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);
        }
    }
}

Se avete bisogno di un iteratore, è possibile scambiare il blocco if con un ritorno resa e cambiare la firma del metodo, in Java immagino che dovrete implementare un'interfaccia iteratore (simile alla classe di Filippo Uren).