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

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

2 голосов
/ 29 ноября 2011

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

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

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

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

Ответы [ 4 ]

0 голосов
/ 29 ноября 2011

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

0 голосов
/ 29 ноября 2011

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

[Обновить] Передать функцию 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
0 голосов
/ 29 ноября 2011

Очередь 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, я думаю, вам придется реализовать интерфейс итератора (аналогичный классу Филипа Урена).

0 голосов
/ 29 ноября 2011

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

...