0

我正在尝试基于 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();
    }
}
4

4 回答 4

3

TLDR；太宽泛。

正如@tarkmeper 所提到的，魔方有大量的组合。
一个简单的洗牌算法不会给你答案。我建议您根据初始状态制定求解立方体的算法。当我自己解决立方体时，有两种基本方法：
1. 逐层求解立方体，这是初学者的方法https://www.youtube.com/watch?v=MaltgJGz-dU
2. CFOP(Cross F2l(First 2层）OLL PLL（oll，pll是算法））
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' 的移动。
这些是立方体上的移动，带有“'”的移动表示相对于您正在查看的立方体的当前面逆时针方向移动该面。
想象你拿着立方体，F代表顺时针前，R代表顺时针右，L代表顺时针左，B代表顺时针后。

于 2019-04-19T19:06:39.493 回答
1

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

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

于 2019-04-19T18:33:17.540 回答
0

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

于 2020-09-25T06:06:26.323 回答
0

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

于 2020-10-07T09:19:12.257 回答