AStarSolver Class Reference

8-puzzle exploration based on the A* search algorithm More...

#include <AStarSolver.hpp>

Inheritance diagram for AStarSolver:

Collaboration diagram for AStarSolver:

Public Member Functions
	AStarSolver (Heuristic *h)
	~AStarSolver ()
LinkedList< GameState * >	solve (Game &game, GameState &g0)
	Explores the game tree in search of the goal state. More...
Public Member Functions inherited from Solver
double	getSecondsToSolve () const
int	getVisitedNodes () const
int	getMaxDepth () const
int	getSolutionDepth () const
bool	isSolved ()
	Solver ()
string	to_string ()
	Generates a string containing useful information from the solver run. More...

Static Public Member Functions
static int	compare (GameState *a, GameState *b)
	Compares two states using the available heuristic. More...

Private Attributes
Heuristic *	heuristic

Additional Inherited Members
Protected Member Functions inherited from Solver
bool	isVisited (GameState &g)
	Checks whether a node has already been visited by the solver. More...
LinkedList< GameState * >	visit (GameState *current)
LinkedList< GameState * >	visit (GameState *current, bool keepVisited)
	Visit a game state, adding it to the list of visited states and returning its valid child states. More...
LinkedList< GameState * >	endSearch (GameState *currentGame, const clock_t start)
	End the search, generating the steps from the initial state to the goal. More...
Protected Attributes inherited from Solver
OrderedList< GameState * >	visited = OrderedList<GameState *>(compare)
int	visitedNodes
int	maxDepth
int	solutionDepth
float	secondsToSolve
bool	solved

Detailed Description

8-puzzle exploration based on the A* search algorithm

Author

Douglas De Rizzo Meneghetti (dougl.nosp@m.asri.nosp@m.zzom@.nosp@m.gmai.nosp@m.l.com)

Date

2017-6-248-puzzle exploration based on the A* search algorithm

Definition at line 15 of file AStarSolver.hpp.

Constructor & Destructor Documentation

AStarSolver()

AStarSolver::AStarSolver ( Heuristic *  h )

inlineexplicit

Parameters

h	the heuristic to be used by A*

Definition at line 22 of file AStarSolver.hpp.

                                     : heuristic(h) {
  }

Here is the caller graph for this function:

~AStarSolver()

AStarSolver::~AStarSolver ( )

inline

Definition at line 25 of file AStarSolver.hpp.

                 {
    delete heuristic;
  }

Member Function Documentation

compare()

static int AStarSolver::compare ( GameState *  a, GameState *  b  )

inlinestatic

Compares two states using the available heuristic.

A* takes into consideration the sum of Manhattan distances between pieces in the current state to their goal state and the number of steps taken to reach the current state. The state that has the lowest sum of both of these values is considered a more promising exploration candidate.

Parameters

a
b

Returns

1 if h(a) + f(a) < h(b) + f(b), -1 if h(a) + f(a) > h(b) + f(b), 0 if h(a) + f(a) = h(b) + f(b)

Definition at line 37 of file AStarSolver.hpp.

                                                 {
    Manhattan h;

    if (h.calc(*a) + a->getDepth() < h.calc(*b) + b->getDepth()) return 1;

    if (h.calc(*a) + a->getDepth() > h.calc(*b) + b->getDepth()) return - 1;

    return 0;
  }

Here is the call graph for this function:

solve()

LinkedList<GameState *> AStarSolver::solve ( Game &  g, GameState &  gs  )

inlinevirtual

Explores the game tree in search of the goal state.

Exploration is done by applying one of the four valid actions of the 8-puzzle to intermediate, non-goal states until the goal state is reached.

Parameters

g	A description of the game.
gs	The initial state of the game.

Returns

list containing all states explored, from the initial state to the goal state.

Implements Solver.

Definition at line 47 of file AStarSolver.hpp.

                                                           {
    //big improvement: insert states in an OrderedList based on their heuristic value
    OrderedList<GameState *> expanded = OrderedList<GameState *>(compare);

    const clock_t start = clock();
    expanded.insert(&g0);

    while (! expanded.isEmpty()) {
      // need only get the first state in the list, since they are ordered! SO FAST
      GameState *currentGame = expanded.remove(0);

      // has the goal state been found?
      if (*game.getGoal() == *currentGame) {
        solved = true;
        return endSearch(currentGame, start);
      }

      // otherwise, expand children and insert them in the ordered
      // list in the position where they belong
      LinkedList<GameState *> children = visit(currentGame);
      while (! children.isEmpty()) {
        expanded.insert(children.remove(0));
      }
    }

    throw invalid_argument("This game is unsolvable!");
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

heuristic

Heuristic* AStarSolver::heuristic

private

Definition at line 18 of file AStarSolver.hpp.

---

The documentation for this class was generated from the following file:

• include/AStarSolver.hpp