2

本质上，我正在做的是尝试通过广度优先搜索所有可能的动作来解决魔方。我知道这不是解决多维数据集的最佳方法，但我只需要非常短的序列（因此搜索的深度不太可能超过 3），我不需要存储任何东西当前序列。

我正在尝试找到一种打印出不断增加的数字字符串（0,1,2,00,01,02 ...）的方法，因此我可以将每个字符串插入一个函数中以检查该特定序列是否移动解决了多维数据集，但我无法找到无限期地继续序列的方法。

到目前为止，我所管理的只是嵌套 for 循环，但每次搜索更深入时都需要另一个循环。有谁知道我该如何解决这个问题？

抱歉，如果我太含糊了，我可以写一篇关于我正在尝试做的事情的文章，但我想我会尽量保持简单。

4

4 回答 4

0

听起来您想要一个递归解决方案，这样您的函数会生成一个给定序列作为输入的后续移动列表，在这种情况下，您可以根据需要多次在其自己的输出上调用该函数。

于 2011-11-28T22:00:46.130 回答
0

递归函数不会这样做吗？您可以限制递归的深度并逐渐加深它。

[更新] 向函数传递一个指定深度的 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
于 2011-11-28T22:01:46.350 回答
0

正如维基百科关于广度优先搜索的文章所建议的那样，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 块与 yield return 交换并更改方法签名，在 Java 中我想您必须实现一个迭代器接口（类似于 Philip Uren 的类）。

于 2011-11-28T23:25:01.507 回答
0

我对 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 中的类似内容。

于 2011-11-29T01:17:16.840 回答