MissionariesCannibals
Declared in astar/MissionariesCannibals.h; the same class on the site of Doxygen.
-
class MissionariesCannibals
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).
Public Types
-
using state_type = std::uint64_t
the packed state
-
using cost_type = int
the cost type
Public Functions
-
inline 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 \)
-
inline std::uint64_t initial_state(void) const noexcept
-
inline bool is_goal(std::uint64_t s) const noexcept
-
inline std::uint64_t hash(std::uint64_t s) const noexcept
-
inline 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>
inline 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 \)
-
inline std::size_t num_features(void) const noexcept
the number of features: the counts on the left bank and the boat
-
template<class F>
inline 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
-
inline std::uint64_t perfect_hash(std::uint64_t s) const noexcept
the perfect hash: the packed state
Public Static Functions
-
static inline int missionaries(std::uint64_t s) noexcept
the missionaries on the left bank in the state s
-
static inline int cannibals(std::uint64_t s) noexcept
the cannibals on the left bank in the state s
-
static inline bool boat_left(std::uint64_t s) noexcept
true if the boat is on the left bank in the state s
-
using state_type = std::uint64_t