序列生成/广度优先搜索

Question

本质上，我所做的就是尝试解决一个魔方，并对所有可能的移动进行广度优先搜索。我知道这不是解决立方体的最佳方法，但我只需要它来处理非常短的序列(因此搜索的深度不太可能大于3)，并且我不需要存储除当前序列之外的任何内容。

我正试图找到一种方法来打印出不断增加的数字字符串(0,1,2,00,01,02…)，所以我可以将每个字符串插入一个函数中，以检查特定的移动序列是否解决了立方体，但我很难找到一种方法来无限期地继续这个序列。

到目前为止，我所管理的都是嵌套的for循环，但每次搜索深入时都需要另一个循环。有人知道我该怎么解决这个问题吗?

如果我说得太模糊了，我可以写一篇关于我想做的事情的文章，但我想尽量保持简单。

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

一个递归函数不会这样做吗?你可以限制递归的深度，逐渐加深。

[Update]传递给函数一个int指定深度;每次递归时，递减值-检查它是否为零，并返回。

对于值，将字符串或stringbuilder的集合传递给递归函数。每一层读取(并删除)前一层的值，附加所有可能的下一步移动，并将结果放回集合(实际上，如果您想要，可以迭代而不是递归地执行此操作)。

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_firstrongearch所建议的那样。

我在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块与一个yield返回和改变方法签名，在Java中，我猜你必须实现一个迭代器接口(类似于Philip Uren的类)。