nパズルの問題A* algorithmを解決するためにC++で実装しています。このリンク
に擬似コードを実装しようとしました。
総コスト（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);
}
}
}