java - 减少 BFS 算法占用的 RAM 量

Question

我编写了一个 2x2x2 魔方求解器，它使用广度优先搜索算法求解用户输入的立方体位置。该程序确实解决了立方体。然而，当我进入一个很难解决的问题时，我会在搜索的深处发现这个问题，我用完了堆空间。我的电脑只有 4 GB 的 RAM，当我运行程序时，我给它分配了 3GB。我想知道我能做些什么来减少搜索所需的内存量。可能通过改变 BFS 的几个方面。

static private void solve(Cube c) {

    Set<Cube> cubesFound = new HashSet<Cube>();
    cubesFound.add(c);

    Stack<Cube> s = new Stack<Cube>();
    s.push(c);

    Set<Stack<Cube>> initialPaths = new HashSet<Stack<Cube>>();
    initialPaths.add(s);

    solve(initialPaths, cubesFound);
}

static private void solve(Set<Stack<Cube>> livePaths, Set<Cube> cubesFoundSoFar) {
    System.out.println("livePaths size:" + livePaths.size());
    int numDupes = 0;

    Set<Stack<Cube>> newLivePaths = new HashSet<Stack<Cube>>();

    for(Stack<Cube> currentPath : livePaths) {

        Set<Cube> nextStates = currentPath.peek().getNextStates();

        for (Cube next : nextStates) {
            if (currentPath.size() > 1 && next.isSolved()) {
                currentPath.push(next);
                System.out.println("Path length:" + currentPath.size());
                System.out.println("Path:" + currentPath);
                System.exit(0);

            } else if (!cubesFoundSoFar.contains(next)) {
                Stack<Cube> newCurrentPath = new Stack<Cube>();
                newCurrentPath.addAll(currentPath);
                newCurrentPath.push(next);
                newLivePaths.add(newCurrentPath);
                cubesFoundSoFar.add(next);
            } else {
                numDupes += 1;
            }
        }
    }
    String storeStates = "positions.txt";
    try {
        PrintWriter outputStream = new PrintWriter(storeStates);
        outputStream.println(cubesFoundSoFar);
        outputStream.println(storeStates);
        outputStream.close();

    } catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

    System.out.println("Duplicates found " + numDupes + ".");
    solve(newLivePaths, cubesFoundSoFar);
}

那是 BFS，但我担心它不是了解正在发生的事情所需的全部信息，所以这里是指向包含所有代码的文件的链接。 https://github.com/HaginCodes/2x2-Cube-Solver/blob/master/src/com/haginonyango/pocketsolver/Cube.java

Answer 1

根据定义，“最佳优先搜索”保留整个空间中可能路径的搜索边界。

这可能呈指数级增长。用3x3x3的魔方，我想有12个吧？每个点可能的移动，因此可以说要解决的 10 个移动序列需要 12^10 种组合，这远远超过十亿 (10^9)。有了这么多状态，您将希望最小化状态的大小以最小化总存储。 (呃，你实际上打印所有状态？“outputStream.println(cubesFoundSoFar);”这不是大量的输出吗？)

在 2x2x2 中，每个点只有 8 种可能的移动。我在这里不知道随机问题的解决方案长度。如果它的长度仍然是 10，你会得到 8^10，这仍然相当大。

现在，许多移动序列导致相同的立方体配置。要识别这一点，您需要检查生成的移动不会重新生成已经访问过的位置。您似乎正在这样做(好!)并跟踪点击次数；我希望命中数相当高，因为许多路径应该导致相同的配置。

您没有显示的是您如何对每个移动序列进行评分以指导搜索。接下来扩展到什么节点？这就是最佳发挥作用的地方。如果您没有任何指导(例如，所有枚举的移动序列都具有相同的值)，您真的会在一个巨大的空间中徘徊，因为所有的移动序列都同样好。是什么引导您的求解器找到解决方案？您需要诸如节点优先级队列之类的东西，其优先级由分数确定，而我在此处提供的代码中没有看到。

我不知道将分数作为移动序列的质量来衡量有什么好的启发式方法，但您可以先用到达该位置所需的移动次数对移动序列进行评分。下一个要尝试的“最佳移动”是路径最短的移动。这可能会有很大帮助。

(一个可能有效的简单增强功能是计算脸上的颜色数量；3 种颜色暗示 [这是真的吗？] 可能需要 3-1 --> 最少 2 次移动才能删除错误的颜色。然后分数可能是#moves+#facecolors-1，以估计解决方案的移动次数；显然您想要最短的移动序列。这可能是所谓的“可接受的”启发式分数)。

您还必须调整方案以检测重复的移动序列。当您找到一个已经遇到的状态时，该状态现在可能会附加到达该状态所需的分数(移动计数)。当你命中时，你找到了另一种方法来达到相同的状态......但是新路径的分数可能小于记录在状态中的分数。在这种情况下，您需要用较小的新分数修改发现的重复状态的分数。这样，得分为 20 的路径/状态实际上可能被发现得分为 10，这意味着它突然得到改善。