减少 BFS 算法占用的 RAM 量

Question

我编写了一个 2x2x2 魔方求解器，它使用广度优先搜索算法求解用户输入的立方体位置。该程序确实解决了立方体。然而，当我进入一个很难解决的问题时，我会在搜索的深处找到，我运行 out of heap space。我的电脑只有 4 GB 内存，当我运行程序时，我给它分配了 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，但我担心它不是了解正在发生的事情所需的所有信息，所以这里是 link 以归档所有代码。 https://github.com/HaginCodes/2x2-Cube-Solver/blob/master/src/com/haginonyango/pocketsolver/Cube.java

Answer 1

根据定义，"Best first search" 通过 space.

保留可能路径的整个搜索边界

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

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

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

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

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

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

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

减少 BFS 算法占用的 RAM 量

Reducing amount of RAM BFS algorithm takes

java

breadth-first-search

heap-dump