WaterJugs
Declared in astar/WaterJugs.h; the same class on the site of Doxygen.
-
class WaterJugs
the water jugs problem, with up to 4 jugs of at most 65535 units
The jugs are empty at the start, and each move fills a jug from the faucet, empties it on the ground, or pours it into another jug until either the first is empty or the second is full; the goal is a jug holding exactly the given level. Every move costs 1, and the heuristic is 0 at a goal and 1 elsewhere, which is consistent. A state packs the level of the jug \( j \) in the bits \( 16 j , \ldots , 16 j + 15 \), and the word is also its perfect hash.
The features of Zobrist hashing are “the jug j holds l units”, one for each jug and each level from 0 to its capacity.
Public Types
-
using state_type = std::uint64_t
the packed levels
-
using cost_type = int
the cost type
Public Functions
-
inline WaterJugs(std::vector<int> capacity, int goal)
constructor of the jugs of the given capacities, the goal being a jug holding goal units
-
inline std::size_t jugs(void) const noexcept
the number of jugs
-
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
-
template<class F>
inline void for_each_successor(std::uint64_t s, int, F &&f) const calls f( t , 1 , h( t ) ) for each fill, empty and pour that changes s
-
inline std::size_t num_features(void) const noexcept
the number of features: one per jug and level
-
template<class F>
inline void for_each_feature(std::uint64_t s, F &&f) const calls f( i ) for the feature i of the level of each jug
-
inline std::uint64_t perfect_hash(std::uint64_t s) const noexcept
the perfect hash: the packed state
Public Static Functions
-
static inline int level(std::uint64_t s, std::size_t j) noexcept
the level of the jug j in the state s
-
using state_type = std::uint64_t