HillClimbingSolver Class Reference

Implementation of a hill-climbing optimization algorithm for the 8-puzzle. More...

#include <HillClimbingSolver.hpp>

Inheritance diagram for HillClimbingSolver:

Collaboration diagram for HillClimbingSolver:

Public Member Functions
	HillClimbingSolver (Heuristic *h)
	Initializes a regular hill-climbing 8-puzzle solver. More...
	HillClimbingSolver (Heuristic *h, bool steepest)
	Initializes a hill-climbing 8-puzzle solver. More...
	~HillClimbingSolver ()
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
bool	steepest

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

Implementation of a hill-climbing optimization algorithm for the 8-puzzle.

Author

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

Date

2017-6-26Implementation of a hill-climbing optimization algorithm for the 8-puzzle.

Definition at line 15 of file HillClimbingSolver.hpp.

Constructor & Destructor Documentation

HillClimbingSolver() [1/2]

HillClimbingSolver::HillClimbingSolver ( Heuristic *  h )

inlineexplicit

Initializes a regular hill-climbing 8-puzzle solver.

Parameters

h	the heuristic to be minimized

Definition at line 25 of file HillClimbingSolver.hpp.

                                            : heuristic(h), steepest(false) {
    // not steep by default
  }

Here is the caller graph for this function:

HillClimbingSolver() [2/2]

HillClimbingSolver::HillClimbingSolver ( Heuristic *  h, bool  steepest  )

inlineexplicit

Initializes a hill-climbing 8-puzzle solver.

Parameters

h	the heuristic to be minimized
steepest	if true, always look for the best among all child states, otherwise choose the first one that is better than the parent state.

Definition at line 32 of file HillClimbingSolver.hpp.

                                                           : heuristic(h), steepest(steepest) {
  }

Here is the caller graph for this function:

~HillClimbingSolver()

HillClimbingSolver::~HillClimbingSolver ( )

inline

Definition at line 35 of file HillClimbingSolver.hpp.

                        {
    delete heuristic;
  }

Member Function Documentation

compare()

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

inlinestatic

Compares two states using the available heuristic.

The state that has the lowest heuristic is considered a more promising exploration candidate.

Parameters

a
b

Returns

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

Definition at line 44 of file HillClimbingSolver.hpp.

                                                 {
    Manhattan h;

    if (h.calc(*a) < h.calc(*b)) return 1;

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

    return 0;
  }

Here is the call graph for this function:

solve()

LinkedList<GameState *> HillClimbingSolver::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 54 of file HillClimbingSolver.hpp.

                                                           {
    // this algorithm has no memory, so no data structure to keep expanded states
    GameState *only_one = &g0;
    const clock_t start = clock();

    while (true) {
      // check for goal
      if (*game.getGoal() == *only_one) {
        solved = true;
        return endSearch(only_one, start);
      }

      // expand children
      LinkedList<GameState *> children = visit(only_one);

      //variable to keep whether a child node has been chosen for exploration next
      bool changed = false;
      while (! children.isEmpty()) {
        GameState *child = children.remove(0);

        // compare child with parent
        if (compare(only_one, child) < 0) {
          changed = true;
          only_one = child;

          // if not steepest, stop after the first child that is better than the parent is found
          if (! steepest) break;
        }
      }

      // if no new child nodes have been found, a local maximum has been found
      if (! changed) {
        cout << "WARNING: hill climbing procedure reached a local minimum\n";
        solved = false;
        return endSearch(only_one, start);
      }
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

heuristic

Heuristic* HillClimbingSolver::heuristic

private

Definition at line 18 of file HillClimbingSolver.hpp.

steepest

bool HillClimbingSolver::steepest

private

Definition at line 19 of file HillClimbingSolver.hpp.

---

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

• include/HillClimbingSolver.hpp