Generación de secuencia/ amplitud Primera búsqueda

Question

Esencialmente, lo que estoy haciendo es tratar de resolver un cubo de Rubik con una primera búsqueda de todos los movimientos posibles. Sé que esta no es la mejor manera de resolver el cubo, pero solo lo necesito para secuencias muy cortas (por lo que es poco probable que la profundidad de la búsqueda sea más profunda que 3), y no necesito almacenar nada más que que la secuencia actual.

Estoy tratando de encontrar una forma de imprimir cada vez más cadenas de número (0,1,2,00,01,02 ...), por lo que puedo conectar cada una en una función para verificar si esa secuencia particular de Moves resuelve el cubo, pero tengo problemas para encontrar una manera de continuar la secuencia indefinidamente.

Hasta ahora, todo lo que he manejado es anidado para los bucles, pero debe haber otro bucle cada vez que la búsqueda se vuelva más profunda. ¿Alguien tiene alguna idea de cómo puedo abordar este problema?

Lo siento si he sido demasiado vago, podría escribir un ensayo sobre lo que estoy tratando de hacer, pero pensé que intentaría mantenerlo simple.

Answer 1

No estoy muy familiarizado con lo que hay en las bibliotecas de Java, así que me disculpan si esto está implementando algo que ya está allí, pero si estaba escribiendo esto desde cero, probablemente haría algo como esto:

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 esa manera, puede enumerar secuencias de alfabetos de símbolos arbitrarios a una profundidad arbitraria. Esto también hace lo que desea en la medida en que itera sobre la profundidad y para cada profundidad genera el conjunto completo de posibles secuencias. También podría hacerse con recursión, como dice Gian, que podría ser más elegante. En Python usaría una función de generador para esto, pero no estoy familiarizado con nada similar en Java.

Answer 2

Parece que desea una solución recursiva, de modo que su función genera una lista de movimientos sucesores dada una secuencia como entrada, en cuyo caso puede seguir llamando a la función en su propia salida tantas veces como sea necesario.

Answer 3

¿No haría esto una función recursiva? Puede limitar la profundidad de la recursión y profundizar gradualmente.

Actualizar] pasar la función y int especificando la profundidad; Cada vez que vuelva a recurrir, disminuya el valor: verifique si es cero y devuelve si es así.

Para los valores, pase una colección de cadenas o constructores de cadenas a la función recursiva. Cada nivel lee (y elimina) los valores del nivel anterior, agrega todos los siguientes movimientos posibles y coloca los resultados en la colección (De hecho, podrías hacer esto iterativamente en lugar de recursivamente si quisiera).

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 cola de FIFO podría ser un mejor enfoque que la recursión, como lo sugiere el artículo de Wikipedia sobre la búsqueda de amplitud: http://en.wikipedia.org/wiki/breadth_first_search.

Mi solución 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 necesita un iterador, puede intercambiar el bloque IF con un rendimiento de rendimiento y cambiar la firma del método, en Java, supongo que tendrá que implementar una interfaz iteradora (similar a la clase de Philip Uren).