序列生成/广度首次搜索

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

这样，您可以将序列从任意符号的字母列举为任意深度。这也可以按照您想要的迭代为止，并且每个深度都会生成整个可能的序列。正如吉安（Gian）所说，这也可以通过递归来完成，这可能更优雅。在Python中，我会为此使用发电机功能，但是我不熟悉Java中类似的内容。

Answer 2

听起来您需要一个递归解决方案，因此您的功能会生成一个以输入为序列的后继移动列表，在这种情况下，您只需在其自身输出中以其自身的输出来调用该功能，尽可能多次。

Answer 3

递归功能会这样做吗？您可以限制递归深度并逐渐加深它。

更新]通过指定深度的功能传递函数；每次重新浏览时，降低值 - 检查是否为零，如果是零，则返回。

对于这些值，请将字符串或字符串构建器的集合传递到递归函数中。每个级别读取（并删除）上一个级别的值，将所有可能的接下来的所有可能移动并将结果放回集合中（实际上，您可以迭代地做到这一点，而不是递归如果您愿意).

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

正如Wikipedia关于广度优先搜索的文章所建议的那样，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中，我想您必须实现迭代器接口（类似于Philip Uren的类）。