Решение n-головоломки с использованием алгоритма A* с использованием C++

Я реализую A* algorithm в C++, чтобы решить проблему n-головоломки.
Я попытался реализовать псевдокод в этой ссылке.
Общая стоимость (F=H+G) вычисляется так: "стоимость зависит от количества неуместных плиток (эвристика) + шаги от начального состояния (G)". Алгоритм AStar функция приведена ниже.

Проблема в том, что у меня ситуация с бесконечным циклом. Как я могу решить это?

PS: я могу дать реализации других функций, используемых в AStar, если требуется.

Любая помощь будет оценена.

void AStar(const int size, int** puzzle)
{
int moveCount = 0;                                                                  // initialize G(n)
int**goalState = GoalState(size);                                                   // initialize  and assign goal state
int openListIndex = 0;                                                              // initialize open list index
vector<node> openList;                                                              // initialize open list
vector<node> closedList;                                                            // initialize closed list

node startNode;                                                                     // initialize start node
startNode.puzzleArray = puzzle;                                                     // assign start node's state
startNode.cost = moveCount + Heuristics(goalState,puzzle,size);                     // assign start node's cost

node goalNode;                                                                      // initialize goal node
goalNode.puzzleArray = goalState;                                                   // assign goal node's state

openList.push_back(startNode);                                                      // push start node to the open list

while (!openList.empty())                                                           // loop while open list is not empty
{
    node currentNode = CalculateLowestCost(&openList, &closedList);                 // initialize current node which has the lowest cost, pop it from open list, push it to the closed list
    int** currentState = currentNode.puzzleArray;                                   // initialize and assign current state array
    /*********************************************************************************************/
    if (GoalCheck(goalState, currentState, size)) break;                            // GOAL CHECK//
    /*********************************************************************************************/
    vector<char> successorDirectionList = CalculateSuccessor(size, currentState);   // initialize a char vector for the directions of the successors

    int**successor;                                                                 // initialize successor state
    node successorNode;                                                             // initialize successor node
    moveCount++;                                                                    // advance G(n)

    for (;!successorDirectionList.empty();)                                         // loop over the successor list
    {
        char direction = successorDirectionList.back();                             // take a direction from the list
        successorDirectionList.pop_back();                                          // remove that direction from the list
        successor = MoveBlank(currentState, size, direction);                       // assign successor state

        successorNode.puzzleArray = successor;                                      // assign successor node's state
        successorNode.cost = moveCount + Heuristics(goalState,currentState,size);   // assign successor node's cost

        //vector<node> stateCheckList = openList;                                   // copy the open list for the checking the nodes in that list

        bool flagOpen = false;
        bool flagClosed = false;
        int locationOpen = -1;
        int locationClosed = -1;

        for (int i=0; i<openList.size(); i++)
        {
            int** existing = openList[i].puzzleArray;
            int existingCost = openList[i].cost;

            if (StateCheck(successor, existing, size))
            {
                locationOpen = i;
                if (successorNode.cost > existingCost)
                {
                    flagOpen = true;
                    break;
                }
            }
        }
        if (flagOpen) continue;

        int** existingInOpen;
        if(locationOpen != -1) 
        {
            existingInOpen = openList[locationOpen].puzzleArray;
            openList.erase(openList.begin()+locationOpen);
        }

        for (int i=0; i<closedList.size(); i++)
        {
            int** existing = closedList[i].puzzleArray;
            int existingCost = closedList[i].cost;

            if (StateCheck(successor, existing, size))
            {
                locationClosed = i;
                if (successorNode.cost > existingCost)
                {
                    flagClosed = true;
                    break;
                }
            }
        }
        if (flagClosed) continue;

        int**existingInClosed;
        if(locationClosed != -1)
        {
            existingInClosed = closedList[locationClosed].puzzleArray;
            closedList.erase(closedList.begin()+locationClosed);
        }

        openList.push_back(successorNode);
    }    
}

}

Источник

3 ответа

Решение

Из-за возможности зацикливания, то есть последовательности ходов, которая возвращает вас в состояние, которое вы уже посетили, важно проверить наличие дублированных состояний (очевидно, это не проблема поиска по дереву). Я не совсем понимаю, что вы делаете, проверяя это, но, вероятно, именно в этом и заключается проблема. У меня была похожая проблема с вами при написании реализации на Haskell (подробности здесь и здесь), и она сводилась к проблеме обработки исследуемого набора. Получите это право, и все работает. (Получение решений для головоломки 4x4 остается делом наездов, особенно если вы начинаете с состояния, находящегося далеко от цели в пространстве состояний, но в основном это связано с недостатками A* и наивным путем мы имеем дело с возможными ходами.)

Источник

Вы удаляете состояние, которое вы выбираете из своего открытого списка? Это код на C#, который очень прост и хорошо написан, может быть, он может вам помочь: http://geekbrothers.org/index.php/categories/computer/12-solve-8-puzzle-with-a а также A* автоматически избегайте петель, потому что он принял ходы, которые вы принимаете во внимание

Источник

Я также сделал n-головоломку (сначала глубина и *), и она вошла в бесконечный цикл. Это произошло из-за следующего цикла: вверх, влево, вниз, вправо, вверх, влево... Я действительно не знаю, есть ли способ предотвратить такую ​​вещь (максимум, что я мог сделать, это предотвратить циклы, такие как лево-право -лева... вспоминая последний ход, который он сделал).

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

Источник
Другие вопросы по тегам