class Compare
{
public:
bool operator()(shared_ptr<Puzzle> puzzA, shared_ptr<Puzzle> puzzB)
{
if (Search::F(puzzA) > Search::F(puzzB))
return true;
else
return false;
}
};
shared_ptr<Puzzle> Search::AStar(shared_ptr<Puzzle> puzzle)
{
//Phase IV: A* Graph Search.
shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
set<string> closedlist;
fringe.push(puzzle);
while (!fringe.empty())
{
shared_ptr<Puzzle> current = fringe.top();
fringe.pop();
if (current->isSolved())
{
solution = current;
break;
}
else
{
if (!closedlist.count(current->uniqueID())) //if not in closedlist
{
closedlist.insert(current->uniqueID());
vector<shared_ptr<Puzzle> > successors = current->Successors();
vector<shared_ptr<Puzzle> >::iterator it;
for (it = successors.begin(); it != successors.end(); it++)
{
if (!closedlist.count((*it)->uniqueID()))
{
if ((*it)->isSolved())
return (*it);
else
fringe.push((*it)); //add successor if not in closedlist
}
}
}
}
}
return solution;
}
int Search::heuristic(shared_ptr<Puzzle> puzzle)
{
//h(n); Manhattan distance heuristic.
int distance = 0;
int counter = 1;
for (int i = 1; i < puzzle->N+1; i++)
{
for (int j = 1; j < puzzle->N+1; j++)
{
//For each block in order:
//Look at its coordinates.
//What's the difference along each axis to the correct place?
int diffx = abs(i - puzzle->index[counter]->posX);
int diffy = abs(j - puzzle->index[counter]->posY);
int manhattan = diffx + diffy;
distance += manhattan;
counter++;
}
}
return distance;
}
int Search::pathCost(shared_ptr<Puzzle> puzzle)
{
//g(n); Path cost function. Distance from initial to current state.
//We count the number of moves made so far.
return puzzle->moveQueue.size();
}
int Search::F(shared_ptr<Puzzle> puzzle)
{
//f(n) Total cost; used by A*.
//f(n) = g(n) + h(n)
return pathCost(puzzle) + heuristic(puzzle);
}
shared_ptr<Puzzle> Search::IDAStar(shared_ptr<Puzzle> puzzle)
{
//Phase IV Bonus: Iterative Deepening A* Graph Search.
shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
set<string> closedlist;
int Flimit = 0;
while (!solution)
{
Flimit++;
//cout << "Current F limit: " <<Flimit <<endl;
closedlist.clear();
while (!fringe.empty())
fringe.pop(); //empty the fringe
fringe.push(puzzle);
while (!fringe.empty())
{
shared_ptr<Puzzle> current = fringe.top();
fringe.pop();
if (current->isSolved())
{
solution = current;
break;
}
else
{
if (!closedlist.count(current->uniqueID())) //if not in closedlist
{
closedlist.insert(current->uniqueID());
if (F(current) < Flimit) //if within F limit
{
vector<shared_ptr<Puzzle> > successors = current->Successors();
vector<shared_ptr<Puzzle> >::iterator it;
for (it = successors.begin(); it != successors.end(); it++)
{
if (!closedlist.count((*it)->uniqueID()))
{
if ((*it)->isSolved())
return (*it);
else
fringe.push((*it)); //add successor if not in closedlist
}
}
}
}
}
}
}
return solution;
}