Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement