Hello all,
This is my first post here. I've exhausted every resource I can think of in hopes of figuring out what I'm doing wrong, but I can't seem to get it right. I'm doing a homework assignment where I have to solve the 8puzzle problem using BFS, DFS, Iterative DFS and A*. I've gotten all of the search methods working pretty well except for A*. I believe I have the concept down correctly, but something about my implementation must be off because it crashes about 50% of the time.
I'll try to explain how I implemented it so you don't have to try to decipher my code.
Basically, I made a struct called State that has 4 member variables: (1) a 3x3 array with the puzzle layout (2) a pointer to a copy of its parent (3) an integer representing depth in the tree (4)an Enum that saves the direction that the empty space was moved from the parent
I made a stack that will hold the active states, and a list that will hold the ones that have already been expanded.
I then implemented a while loop that ends naturally when the number of expanded nodes exceeds the limit (this was a homework specification). It also breaks when the goal state is found (checked at the beginning of the loop)
From there, I expand the current node, called mCurrState, which is the node at the top of the stack. Before I expand the node, I remove it from the top of the stack. Then, I create a temporary node and move it in one of the four directions if it is a valid direction and if the node was not previously expanded.
After I move the temporary node, I set all of its values to make mCurrState its parent. Then, I do the heuristics check. I send the temporary node to a method that chooses one of the three heuristics to apply to it based on which one the user picked. The simplest one is what I have been using for testing. All it does is count the number of nodes that are not in the correct spot. If the value that it returns is less than or equal to mCurrState, I push it to the top of the stack.
I then reset the temporary node to be exual to mCurrState, and repeat the process for the other three directions. Theoretically, anywhere from 1-4 new nodes should be placed onto the stack every time the loop iterates, depending on how many adjacent nodes were already expanded, and how many had heuristic values less than or equal to the current node.
The problem that I am running into is that my program crashes about 50% of the time. It happens at the bottom of the loop on the very last command which is "mCurrState = tree.top();" The while loop removes exactly one node from the stack every time, and if working properly should add at least 1 node to the stack, so the tree (the stack I am putting the nodes on) should never be empty, but it is. I can't figure out why the tree would ever be empty, and there is way too much information to track if I were to debug it and try to do all the work by hand.
I was hoping you could take a look at it and see if you can figure out how the tree is ending up empty. I am positive that my heuristics function is returning the correct values because I calculated those by hand. I am also fairly positive that my function removes exactly one node from the stack per iteration of the loop. The only thing that I know of that could be causing the problem is no new nodes are being added to the top of the stack for several iterations, and the tree gets emptied out.
Here is the function in question for reference, and I will link the full source code so that it doesn't take too much space. Thank you, I really appreciate it. If I end up fixing it before anyone gets back to me I will let you know so you don't end up wasting your time. https://rapidshare.com/files/162640463/cEightPuzzle.h
https://rapidshare.com/files/696912117/cEightPuzzle.cpp
https://rapidshare.com/files/2401003262/proj1main.cpp
int cEightPuzzle::AstarSolver(int maxNodes, int heuristicChoice)
{
int numExpandedNodes = 0;
mCurrState.depth = 0;
mCurrState.parent = NULL;
mCurrState.dir = INITIAL_STATE;
State tempState;
stack<State> tree;
tree.push(mCurrState);
bool foundSolution = false;
while (numExpandedNodes < maxNodes)
{
if (IsGoalState(mCurrState, mGoalState)) {foundSolution = true; break;}
tempState = mCurrState;
if (WasExpanded(&mCurrState)) {
tree.pop();
if(tree.empty()) {foundSolution = false; break;}
mCurrState = tree.top();
continue;
}
numExpandedNodes++;
tree.pop();
if(MovePiece(&tempState, RIGHT) && !WasExpanded(&tempState)) {
tempState.parent = new State(mCurrState);
tempState.depth = tempState.parent->depth + 1;
tempState.dir = RIGHT;
if ((heuristicSplitter(heuristicChoice, tempState) <= heuristicSplitter(heuristicChoice,mCurrState))
||(heuristicSplitter(heuristicChoice, tempState) <= heuristicSplitter(heuristicChoice,tree.top()))){tree.push(tempState);}
}
tempState = mCurrState;
if(MovePiece(&tempState, LEFT) && !WasExpanded(&tempState)) {
tempState.parent = new State(mCurrState);
tempState.depth = tempState.parent->depth + 1;
tempState.dir = LEFT;
if ((heuristicSplitter(heuristicChoice, tempState) <= heuristicSplitter(heuristicChoice,mCurrState))){tree.push(tempState);}
}
tempState = mCurrState;
if(MovePiece(&tempState, UP) && !WasExpanded(&tempState)) {
tempState.parent = new State(mCurrState);
tempState.depth = tempState.parent->depth + 1;
tempState.dir = UP;
if ((heuristicSplitter(heuristicChoice, tempState) <= heuristicSplitter(heuristicChoice,mCurrState))){tree.push(tempState);}
}
tempState = mCurrState;
if(MovePiece(&tempState, DOWN) && !WasExpanded(&tempState)) {
tempState.parent = new State(mCurrState);
tempState.depth = tempState.parent->depth + 1;
tempState.dir = DOWN;
if ((heuristicSplitter(heuristicChoice, tempState) <= heuristicSplitter(heuristicChoice,mCurrState))){tree.push(tempState);}
}
mExpandedStates.push_back(mCurrState);
if (tree.empty())
{
int a = 5;
}
mCurrState = tree.top();
}
if (foundSolution) {
while (mCurrState.depth >= 1)
{
PrintState(mCurrState);
mCurrState = *mCurrState.parent;
}
PrintState(mCurrState);
}
else {
cout << "No solution found\n ";
}
cout << "Number of expanded nodes: " << numExpandedNodes << endl;
return 1;
}