State Space Searching

Listing 1

// search.h
namespace dct
{
   template <typename STATE_T, typename OP_T>
   struct search_result_template_t
   {
      STATE_T           goal_state_reached;
      double            cost;
      std::vector<OP_T> operators;
   };
   template <...> // See article text for template parameters
   class search_engine_t: ... // Inherit from policy classes
   {
      public:
         typedef std::set<
                         search_result_template_t<STATE_T, OP_T>,
                         result_comp_t<STATE_T, OP_T> // Not shown
                         > search_result_t;
         search_result_t a_star(
                                const STATE_T &initial_state,
                                bool          return_all = false
                               );
         search_result_t breadth_first(
                                const STATE_T &initial_state,
                                bool          return_all = false
                                      );
         search_result_t depth_first(
                                const STATE_T &initial_state,
                                bool          return_all = false
                                    );
         search_result_t depth_limited(
                                const STATE_T &initial_state,
                                unsigned int  depth_limit,
                                bool          return_all = false
                                      );
         search_result_t greedy(
                                const STATE_T &initial_state,
                                bool          return_all = false
                               );
         search_result_t iterative_deepening(
                                const STATE_T &initial_state,
                                unsigned int  depth_limit
                                            );

         search_result_t uniform_cost(
                                const STATE_T &initial_state,
                                bool          return_all = false
                                     );
   };
}