Я реализую 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);
}
}
}