Почему алгоритм BFS не всегда находит решение кубика Рубика? - PullRequest
Новая
       60

Почему алгоритм BFS не всегда находит решение кубика Рубика?

0 голосов
/ 19 апреля 2019

Я пытаюсь написать решатель кубиков Рубика на основе алгоритма BFS. Он находит способ, если одна перестановка сделана (одна стена сдвинута). Есть проблема с памятью, когда я делаю более сложные перетасовки.

Я написал куб, так что на нем можно делать ходы, поэтому ходы работают хорошо. Я проверяю, решает ли куб, сравнивая его с новым (не перемешивает). Я знаю, что это не идеально, но все равно должно работать ...

есть код: 

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();
    }
}

Ответы [ 2 ]

1 голос
/ 19 апреля 2019

TLDR;Слишком широкий.

Как уже упоминалось @tarkmeper, у кубика Рубика огромное количество комбинаций.
Простой алгоритм перетасовки не даст вам ответа.Я бы предложил вам создать алгоритмы, которые решают куб, основываясь на его начальном состоянии.Когда я решаю куб самостоятельно, есть 2 основных метода:
1.Решите куб слой за слоем, что является методом новичка https://www.youtube.com/watch?v=MaltgJGz-dU
2. CFOP (Cross F2l (первые 2 слоя) 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 назад по часовой стрелке.

1 голос
/ 19 апреля 2019

Кубики Рубика имеют огромное количество возможных состояний (https://www.quora.com/In-how-many-ways-can-a-Rubiks-cube-be-arranged).

Концептуально вашему алгоритму может потребоваться включить все 43 252 003 274 489 856 000 состояний в очередь, прежде чем он достигнет правильного результата. У вас не будет столько памяти для поиска в ширину.

...