为什么BFS算法并不总能找到rubik多维数据集的解决方案?

问题描述 投票:0回答:2

我想基于BFS算法编写rubik的立方体求解器。如果有一次洗牌(一面墙移动)就会找到方法。当我做更复杂的shuffle时,内存有问题。

我写过立方体,所以人们可以移动它,所以移动效果很好。我正在检查立方体是否通过与新的立方体(不是随机播放)进行比较来解决。我知道它并不完美,但无论如何它都应该有效......

有些代码:

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();
    }
}
c++ out-of-memory breadth-first-search rubiks-cube
2个回答
1
投票

Rubik的立方体有很多可能的状态(qazxsw poi)。

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


1
投票

TLDR;太宽泛。

正如@tarkmeper所提到的,rubik的立方体有很多种组合。 简单的改组算法不会给你答案。我建议你根据它的初始状态制作解决立方体的算法。当我自己解决立方体时,有两种基本方法: 1.逐层解决立方体,这是初学者的方法https://www.quora.com/In-how-many-ways-can-a-Rubiks-cube-be-arranged 2. CFOP(交叉F2l(前2层)OLL PLL(oll,pll是算法)) https://www.youtube.com/watch?v=MaltgJGz-dU(非常先进) 已经开发出用于解决立方体的机器,但它们将输入作为立方体的图像。 我认为实施CFOP实际上可以解决你的问题,因为它不会检查多维数据集的随机混乱,但实际上系统地解决了它,但这将非常困难。 对于您的实现,将数据作为矩阵更好。 rubik的立方体有3个部分:1。中心(1种颜色)2。边缘(2种颜色)3。角度(3种颜色) 有6个中心12个8个角。您还必须考虑有效的初始状态,因为您无法随机化它。 我现在想到的关于这种规模问题的是制作4种算法:

https://www.youtube.com/watch?v=WzE7SyDB8vA

到达立方体本身的骨架: 你还需要实现F,F',R,R',L,L',B,B'的移动。 这些是立方体上的移动,带有“'”的移动表示相对于您正在查看的立方体的当前面以逆时针方向移动该面。 想象一下,你拿着立方体,F是顺时针方向前方,R方向顺时针方向,L顺时针方向是左边,B顺时针方向后方。

© www.soinside.com 2019 - 2024. All rights reserved.