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

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

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

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

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

Источник

4 ответа

Решение

Я не очень знаком с тем, что находится в библиотеках 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.

Источник

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

Источник

Очередь 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);
        }
    }
}

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

Источник

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

[Update] Передайте функцию 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
Источник
Другие вопросы по тегам