State Space Searching

Listing 2

#include "search.h"

class state_t {...}; // A state
class op_t {...}; // An operator

class op_gen_t // Generate operators
{
   std::set<op_t> gen_ops(const state_t &state) {...}
};
class op_apply_t // Apply an operator to a state
{
   std::pair<state_t, double>
   apply_op(const state_t &state, const op_t &op) {...}
};
class goal_test_t // Check if a state is a goal state
{
   bool is_goal(const state_t &state) {...}
};
class check_t // User-defined repeated state checker
{
   void clear_state() {...}
   bool seen_before(const state_t &state) {...}
};
class heuristic_t // Estimate the cost to the nearest goal
{
   double apply_heuristic(const state_t &state) {...}
};
typedef dct::search_engine_t<state_t, op_t, op_gen_t,
                   op_apply_t, goal_test_t,
                   repeated_state_checker_t<4, check_t>,
                   heuristic_t> se_t;
int main()
{
   // Construct the initial state
   state_t initial_state(/* Constructor arguments */); 
   se_t se;
   se_t::search_result_t solution;

   // Perform the search using A*, for example.
   solution = se.a_star(initial_state);

   // Now go do something with the solution...
}