I am implementing A* algorithm
in C++ to solve the n-puzzle problem.
I tried to implement the pseudocode in this link.
Total cost(F=H+G) calculation is "cost depends on the number of misplaced tiles (Heuristics) + steps from initial state (G)". The algorithm of the AStar
function given below.
The problem is, I am having an infinite loop situation. How can I solve this?
PS: I can give the implementations of the other functions used in AStar
, if requested.
Any help would be appreciated.
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);
}
}
}
Because of the possibility of loops, i.e. a sequence of moves that takes you back to a state you've already visited, it's important to check for duplicate states (not a problem with tree search, obviously). I can't quite follow what you're doing with your checking for this, but that's likely to be where the problem lies. I had a similar sort of problem to you when writing a Haskell implementation (details here and here), and it came down to a problem of handling the explored set. Get that right, and everything works. (Getting solutions for the 4x4 puzzle remains a bit of a hit-and-miss affair, especially if you start from a state a long way from the goal in state space, but that's mostly down to the deficiencies of A* and the naïve way we're dealing with possible moves.)