MissionariesCannibals Class Reference

the missionaries and cannibals problem More...

#include <PBeFS/astar/MissionariesCannibals.h>

Public Types
using	state_type = std::uint64_t
	the packed state
using	cost_type = int
	the cost type

Public Member Functions
	MissionariesCannibals (int m, int c, int b)
	constructor of the problem with m missionaries, c cannibals and a boat of b seats, \( m , c \leq 65535 \)
std::uint64_t	initial_state (void) const noexcept
bool	is_goal (std::uint64_t s) const noexcept
std::uint64_t	hash (std::uint64_t s) const noexcept
int	heuristic (std::uint64_t s) const noexcept
	with \( n \) people on the left bank, a full boat carries \( b \) of them over and brings 1 back: at least \( 2 \lceil ( n - b ) / ( b - 1 ) \rceil + 1 \) crossings if \( n > b \), 1 if \( 0 < n \leq b \), one more if the boat is on the right bank
template<class F>
void	for_each_successor (std::uint64_t s, int, F &&f) const
	calls f( t , 1 , h( t ) ) for each safe crossing of dm missionaries and dc cannibals, \( 1 \leq d_m + d_c \leq b \), in increasing \( d_m \) and then \( d_c \)
std::size_t	num_features (void) const noexcept
	the number of features: the counts on the left bank and the boat
template<class F>
void	for_each_feature (std::uint64_t s, F &&f) const
	calls f( m ), f( M + 1 + c ) and f( M + C + 2 + boat ) for the m missionaries and c cannibals on the left bank of s
std::uint64_t	perfect_hash (std::uint64_t s) const noexcept
	the perfect hash: the packed state

Static Public Member Functions
static int	missionaries (std::uint64_t s) noexcept
	the missionaries on the left bank in the state s
static int	cannibals (std::uint64_t s) noexcept
	the cannibals on the left bank in the state s
static bool	boat_left (std::uint64_t s) noexcept
	true if the boat is on the left bank in the state s

Detailed Description

the missionaries and cannibals problem

Everybody is on the left bank at the start, with the boat; a crossing carries from 1 to \( b \) people, and on neither bank may the missionaries be outnumbered by the cannibals, if any missionary is there. Every crossing costs 1, and the heuristic is the least number of crossings that would carry the people left over the river with the boat always full, which is admissible. A state packs the missionaries on the left bank in the bits \( 0 , \ldots , 15 \), the cannibals there in the bits \( 16 , \ldots , 31 \), and the bank of the boat in the bit 32 (0 = left); the word is also its perfect hash.

The features of Zobrist hashing are the number of the missionaries on the left bank ( \( m + 1 \) features), that of the cannibals there ( \( c + 1 \)) and the bank of the boat (2).

Member Typedef Documentation

cost_type

using cost_type = int

the cost type

state_type

using state_type = std::uint64_t

the packed state

Constructor & Destructor Documentation

MissionariesCannibals()

MissionariesCannibals ( int m, int c, int b )

inline

constructor of the problem with m missionaries, c cannibals and a boat of b seats, \( m , c \leq 65535 \)

Member Function Documentation

boat_left()

bool boat_left ( std::uint64_t s )

inlinestaticnodiscardnoexcept

true if the boat is on the left bank in the state s

cannibals()

int cannibals ( std::uint64_t s )

inlinestaticnodiscardnoexcept

the cannibals on the left bank in the state s

for_each_feature()

template<class F>

void for_each_feature ( std::uint64_t s, F && f ) const

inline

calls f( m ), f( M + 1 + c ) and f( M + C + 2 + boat ) for the m missionaries and c cannibals on the left bank of s

for_each_successor()

template<class F>

void for_each_successor ( std::uint64_t s, int , F && f ) const

inline

calls f( t , 1 , h( t ) ) for each safe crossing of dm missionaries and dc cannibals, \( 1 \leq d_m + d_c \leq b \), in increasing \( d_m \) and then \( d_c \)

hash()

std::uint64_t hash ( std::uint64_t s ) const

inlinenodiscardnoexcept

heuristic()

int heuristic ( std::uint64_t s ) const

inlinenodiscardnoexcept

with \( n \) people on the left bank, a full boat carries \( b \) of them over and brings 1 back: at least \( 2 \lceil ( n - b ) / ( b - 1 ) \rceil + 1 \) crossings if \( n > b \), 1 if \( 0 < n \leq b \), one more if the boat is on the right bank

initial_state()

std::uint64_t initial_state ( void ) const

inlinenodiscardnoexcept

is_goal()

bool is_goal ( std::uint64_t s ) const

inlinenodiscardnoexcept

missionaries()

int missionaries ( std::uint64_t s )

inlinestaticnodiscardnoexcept

the missionaries on the left bank in the state s

num_features()

std::size_t num_features ( void ) const

inlinenodiscardnoexcept

the number of features: the counts on the left bank and the boat

perfect_hash()

std::uint64_t perfect_hash ( std::uint64_t s ) const

inlinenodiscardnoexcept

the perfect hash: the packed state

---

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

• PBeFS/astar/MissionariesCannibals.h