c++ - 为什么 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

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.角(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' 等 Action 。
这些是立方体上的移动，带有“'”的移动表示相对于您正在查看的立方体的当前面逆时针方向移动该面。
想象您拿着立方体，F 代表顺时针方向,R顺时针右，L顺时针左，B顺时针退。