为什么 BFS 算法并不总能找到魔方的解？

Question

我正在尝试编写基于 BFS 算法的 rubick 立方体求解器。如果完成一次洗牌（移动一堵墙），它就会找到方法。当我做更复杂的洗牌时，内存有问题。

我写了立方体，所以可以在上面移动，所以移动效果很好。我正在通过将多维数据集与新多维数据集进行比较（而不是随机播放）来检查多维数据集是否已解决。我知道它并不完美，但无论如何它应该可以工作...

有一些代码：

void search(Node &problem)
{
    int flag;
    Node *curr;
    Node* mvs[12]; //moves
    std::vector<Cube> explored; //list of position cube's already been in
    std::queue<Node*> Q; //queue of possible ways 
    if (problem.isgoal() == true) return problem.state;
    Q.push(&problem);
    explored.push_back(problem.state);
    while (!Q.empty())
    {
        flag = 0;
        curr = Q.front();
        if (curr->isgoal() == true)
        {
            return curr->state;
        }
        if (std::find(explored.begin(), explored.end(), curr->state)!=explored.end()) //checking if cube's been in curr position
        {
            flag = 1;
            break;
        }
        if (flag == 1) break;
        explored.push_back(Q.front()->state);
        for (int i = 0; i < 12; i++) {
            Q.push(curr->expand(i)); //expand is method that 
                        //spread tree of possible moves from curr node
        }
        Q.pop();
    }
}

Answer 1

红方块有大量可能的状态 (https://www.quora.com/In-how-many-ways-can-a-Rubiks-cube-be-arranged)。

从概念上讲，您的算法可能需要将所有 43,252,003,274,489,856,000 个状态包含到队列中，然后才能得出正确的结果。您不会有这么多内存来进行广度优先搜索。

Answer 2

TLDR；太宽泛了。

正如@tarkmeper 所说，魔方有大量的组合。
一个简单的洗牌算法不会给你答案。我建议你制作基于初始状态求解立方体的算法。当我自己解决立方体时，有两种基本方法：
1。一层层解立方体，初学者的方法https://www.youtube.com/watch?v=MaltgJGz-dU
2. CFOP(Cross F2l(First 2 Layers) OLL PLL(oll, pll are algorithms))
https://www.youtube.com/watch?v=WzE7SyDB8vA（相当高级）
已经开发出解决立方体的机器，但它们将输入作为立方体的图像。

我认为实施 CFOP 实际上可以解决您的问题，因为它不会检查立方体的随机洗牌，而是系统地解决它，但这将非常困难。

对于您的实施，将数据作为矩阵会更好。
魔方有 3 个部分：1.中心（1 种颜色）2.边缘（2 种颜色）3.Corner（3 种颜色）
有6个中心12个边8个角。您还必须考虑有效的初始状态，因为您无法将其随机化。
对于这种规模的问题，我现在能想到的是制作 4 种算法：

Cross():
.... which takes the cube and makes the cross which is basically all white edges
aligned to white center and their 2nd colored center.
F2L():
.... to make 2nd layers of the cube with the corner pieces of the first layer,
this could use backtracking as there are lot of invalid case occurences
OLL():
.... based on your state of cube after F2L transformation there is a straight
forward set of moves, Same for PLL():

深入了解立方体本身：
您还需要执行 F、F'、R、R'、L、L'、B、B' 等动作。
这些是立方体上的移动，带有“'”的移动表示相对于您正在查看的立方体的当前面逆时针方向移动该面。
想象您拿着立方体，F 代表前面顺时针，R顺时针右，L顺时针左，B顺时针退

Answer 3

有些状态没有导致解决方案，因为它们不属于它们的旋转，它们属于所有排列。让我们考虑一个例子 1,2,3,4。在 1,2,3,4 的旋转中找不到 3,1,2,4 它在所有排列中都找到

Answer 4

有些答案需要 18 步，当你每步至少有 12 步时，使用广度优先搜索最坏情况下你有 12^18。计算机速度很快，但还不够快，无法使用 BFS 求解立方体。很难看出是否可以将所有解决方案存储在数据库中，因为只需要存储解决立方体的移动，但这很可能（参见国际象棋残局表）。

为什么 BFS 算法并不总能找到魔方的解？

Why BFS algorithm doesn't always find solution of rubick's cube?

c++

out-of-memory

breadth-first-search

rubiks-cube