A generic A-star C++ template.

driver-inl.h

#ifndef ASTAR_DRIVER_INL_H_
#define ASTAR_DRIVER_INL_H_

#include "driver.h"

namespace astar {

template<typename T, typename Explorer, typename Evaluator>
bool Driver<T, Explorer, Evaluator>::search(const T &start, const T &end) {

  // Declare a priority queue, which is a minheap. It will maintain the states
  // in a order of lower evaluation value first.
  priority_queue<state_type, vector<state_type>, greater<state_type> > que;

  // Put start state in the queue after wrap it with `state_type`.
  que.push(state_type(start));

  // Loop while queue is not empty (still have states to search.)
  while (!que.empty()) {

    // Pick the state with lowest evaluation value.
    state_type cur_state = que.top();
    que.pop();

    // If the state's payload == end state.
    if (cur_state.value() == end)
      return true;

    // Use explorer_ to discover new states.
    vector<T> new_states = explorer_(cur_state.value());
    for (typename vector<T>::iterator it = new_states.begin(); 
        it != new_states.end(); it++) {
      // Put the new state in the queue. while increase the state depth by 1, 
      // and evaluate it with evaluator_.
      que.push(state_type(*it, cur_state.depth() + 1, 
          evaluator_(*it, cur_state.depth() + 1)));
    }

  }

  return false;

}

} // namespace astar

#endif // ASTAR_DRIVER_INL_H_

driver.h

#ifndef ASTAR_DRIVER_H_
#define ASTAR_DRIVER_H_

#include <queue>
#include <vector>
#include <functional>

namespace astar {

using std::priority_queue;
using std::vector;
using std::greater;

// A naive evaluation function, which will only consider the depth. which means, 
// the A* will become to BFS.
template<typename T>
struct depth {
  int operator ()(const T &state, int state_depth) {
    return state_depth;
  }
};

template<typename T, typename Explorer, typename Evaluator = depth<T> >
class Driver {

 public:
  typedef T state_value_type;
  Driver(const Explorer &explorer = Explorer(), 
      const Evaluator &evaluator = Evaluator()) :
    explorer_(explorer), evaluator_(evaluator) {}
  bool search(const T&, const T&);

 private:

  // An interal state preserving wrapper.
  class State {

   public:
    typedef T value_type;
    State(const T &value, int depth = 0, int evaluation = 0) : value_(value), 
        depth_(depth), evaluation_(evaluation) {}
    const T &value() {
      return value_;
    }
    int evaluation() {
      return evaluation_;
    }
    int depth() {
      return depth_;
    }
    bool operator >(const State &rhs) const {
      return evaluation_ > rhs.evaluation_;
    }

   private:
    T value_;
    int depth_;
    int evaluation_;

  }; // class State

  typedef State state_type;
  Explorer explorer_;
  Evaluator evaluator_;

};

} // namespace astar

#include "driver-inl.h"

#endif // ASTAR_DRIVER_H_