Генерация последовательности/ ширина Первый поиск

Question

По сути, то, что я делаю, пытается решить куб Рубика с широкой поиском всех возможных движений. Я знаю, что это не лучший способ решить куб, но мне это нужно только для очень коротких последовательностей (так что глубина поиска вряд ли будет глубже, чем 3), и мне не нужно хранить ничего, кроме как текущая последовательность.

Я пытаюсь найти способ распечатать все увеличивающиеся строки числа (0,1,2,00,01,02 ...), поэтому я могу просто подключить каждую функцию, чтобы проверить, конкретная последовательность Движения решают куб, но у меня проблемы с поиском способа продолжения последовательности на неопределенный срок.

До сих пор все, что мне удалось, вкладывается для петли, но должен быть еще один цикл каждый раз, когда поиск становится все глубже. У кого -нибудь есть представление о том, как я могу подойти к этой проблеме?

Извините, если бы я был слишком расплывчатым, я мог бы написать эссе о том, что я пытаюсь сделать, но подумал, что постараюсь сделать это просто.

Answer 1

Я не очень знаком с тем, что находится в библиотеках Java, поэтому извиняюсь, если это реализует что -то, что уже есть, но если бы я писал это с нуля, я бы, вероятно, сделал что -то вроде этого:

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

Таким образом, вы можете перечислять последовательности из алфавитов произвольных символов к произвольной глубине. Это также делает то, что вы хотите, поскольку оно итерация на глубине, и для каждой глубины генерирует полный набор возможных последовательностей. Это также может быть сделано с рекурсией, как говорит Джан, что может быть более элегантным. В Python я использовал бы функцию генератора для этого, но я не знаком с чем -то подобным на Java.

Answer 2

Похоже, вы хотите рекурсивное решение, так что ваша функция генерирует список перемещений преемника, учитывая последовательность в качестве ввода, и в этом случае вы можете просто называть функцию на собственном выходе столько раз, сколько необходимо.

Answer 3

Разве рекурсивная функция не сделает это? Вы можете ограничить глубину рекурсии и постепенно углубить ее.

Обновление] пройти функцию int, указав глубину; Каждый раз, когда вы повторяете, уменьшаете значение - проверьте, является ли оно нулю, и возвращайте, если да, то.

Для значений передайте коллекцию строк или строкостей в рекурсивной функции. Каждый уровень считывает (и удаляет) значения с предыдущего уровня, добавляет все возможные следующие движения и помещает результаты обратно в коллекцию (На самом деле, вы могли бы сделать это итеративно, а не рекурсивно, если хотите).

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

Очередь FIFO может быть лучшим подходом, чем рекурсия, как было предложено в статье Википедии о поиске в ширине: http://en.wikipedia.org/wiki/breadth_first_search.

Мое решение в 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);
        }
    }
}

Если вам нужен итератор, вы можете поменять блок, если блок с возвратом доходности и изменить подпись метода, в Java, я думаю, вам придется реализовать интерфейс итератора (аналогично классу Филиппа Урен).