SequenceScore< W, H > Class Template Reference

the sliding-tile puzzle with the sequence score heuristic of Nilsson More...

#include <PBeFS/astar/SequenceScore.h>

Public Types
using	Base = SlidingTile< W , H >
	the puzzle
using	state_type = typename Base::state_type
	a packed board
using	cost_type = typename Base::cost_type
	the cost type
using	board_type = typename Base::board_type
	a board

Public Member Functions
	SequenceScore (const board_type &start, const board_type &goal=Base::korf_goal())
	constructor, taking the start and the goal boards
state_type	initial_state (void) const noexcept
bool	is_goal (state_type s) const noexcept
std::uint64_t	hash (state_type s) const noexcept
cost_type	heuristic (state_type s) const noexcept
	M + W S.
template<class F>
void	for_each_successor (state_type s, cost_type, F &&f) const
const Base &	base (void) const noexcept
	the underlying puzzle

Static Public Attributes
static constexpr int	cells = Base::cells
	the cells

Detailed Description

template<int W, int H>
class PBeFS_di_unipi_it::SequenceScore< W, H >

the sliding-tile puzzle with the sequence score heuristic of Nilsson

The heuristic is h = M + W S, M being the Manhattan distance and S the sequence score: on the 3 x 3 board S counts 1 if the centre does not hold its goal tile and 2 for each tile of the border not followed, clockwise, by the tile that follows it in the goal; on the other boards S counts 1 if the first cell does not hold its goal tile and 2 for each tile not followed, in row-major order, by the tile that follows it in the goal (Nilsson, "Problem-solving methods in artificial intelligence", 1971). The heuristic is not admissible: A* finds a solution expanding fewer nodes, but not necessarily an optimal one.

Member Typedef Documentation

Base

template<int W, int H>

using Base = SlidingTile< W , H >

the puzzle

board_type

template<int W, int H>

using board_type = typename Base::board_type

a board

cost_type

template<int W, int H>

using cost_type = typename Base::cost_type

the cost type

state_type

template<int W, int H>

using state_type = typename Base::state_type

a packed board

Constructor & Destructor Documentation

SequenceScore()

template<int W, int H>

SequenceScore ( const board_type & start, const board_type & goal = Base::korf_goal() )

inlineexplicit

constructor, taking the start and the goal boards

Member Function Documentation

base()

template<int W, int H>

const Base & base ( void ) const

inlinenodiscardnoexcept

the underlying puzzle

for_each_successor()

template<int W, int H>

template<class F>

void for_each_successor ( state_type s, cost_type , F && f ) const

inline

hash()

template<int W, int H>

std::uint64_t hash ( state_type s ) const

inlinenodiscardnoexcept

heuristic()

template<int W, int H>

cost_type heuristic ( state_type s ) const

inlinenodiscardnoexcept

M + W S.

initial_state()

template<int W, int H>

state_type initial_state ( void ) const

inlinenodiscardnoexcept

is_goal()

template<int W, int H>

bool is_goal ( state_type s ) const

inlinenodiscardnoexcept

Member Data Documentation

cells

template<int W, int H>

int cells = Base::cells

staticconstexpr

the cells

---

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

• PBeFS/astar/SequenceScore.h