应用A*解决九宫问题(8数码)

#include 
#include 
#include "astar.hpp"

struct _Directs { enum Direct { north = -3, west = -1, east = 1, south = 3 }; };

struct Code8 : _Directs
{
 bool operator==(const Code8& x) const { return code == x.code; }
 int f() const { return g() + h(); }
 int g() const { return depth; }
 int h() const { return left; }
 int g(int x) { return depth = x; }
 int h(int x) { return left = x; }

 Code8(const std::tr1::array& vec, int vg, int vh) : code(0), depth(vg), left(vh)
 {
  for (unsigned int i = 0; i < 9u; ++i)
   code |= (vec[i] == 8) ? i << 27 : vec[i] << (3*i);
 }

 int at(int i) const { return i == int(code >> 27) ? 8 : (code >> 3*i) & 0x07u; }

 int index(int val) const
 {
  int x = code >> 27;
  if (val != 8)
  {
   int i8 = x;
   for (x = 0; x < 9; ++x)
    if (val == int((code >> (3*x)) & 0x07) && x != i8)
     break;
  }
  return x;
 }

 void swap(int i1, int i2)
 {
  unsigned int c1 = at(i1), c2 = at(i2);
  if (c1 == 8)
   code = (code & ~(0x07u << 27)) | (i2 << 27);
  if (c2 == 8)
   code = (code & ~(0x07u << 27)) | (i1 << 27);
  code &= ~((0x07u << (3*i1)) | (0x07u << (3*i2)));
  code |= ((c1 << (3*i2)) | (c2 << (3*i1)));
 }

 static int distance(int a, int b) { return abs(a/3 - b/3) + abs(a%3 - b%3); }

 int distance(const Code8& a) const
 {
  int x = 0;
  for (int c = 0; c < 9; ++c)
   x += distance(index(c), a.index(c));
  return x;
 }

 unsigned int code;
 int depth, left;
};

std::ostream& operator<<(std::ostream& out, const Code8& a)
{
 for (int i = 0; i < 8; ++i)
  out << a.at(i) << ((i+1)%3 ? " " : "\n");
 return out << a.at(8);
}

struct EightCode : _Directs
{
 typedef Code8 element_type;

 EightCode(const char* beg, const char* end)
  : finish_(reads(end), 0, 0), start_(reads(beg), 0, 0)
 {
  start_.h(finish_.distance(start_));
 }

 template 
 void foreach_adjacents(const Code8& a, Op op) const
 {
  for (int n = 0, i0 = a.index(0), e = north; n < 4; ++n, e += 2)
  {
   int ic = i0 + e;
   if ((e==1||e==-1) ? ic >= i0-i0%3 && ic < i0-i0%3+3 : ic >= 0 && ic < 9)
   {
    Code8 x = a;
    x.swap(i0, ic);
    x.g(x.g() + 1);
    x.h(finish_.distance(x));
    //x.h(x.h() + (Code8::distance(i0, iic) < Code8::distance(ic, iic) ? -1 : 1));
    op(x);
   }
  }
 }

 Code8 start() const { return start_; }
 Code8 finish() const { return finish_; }

 static std::tr1::array reads(const char* s)
 {
  std::tr1::array vec;
  for (int i = 0; s && i < 9; ++s)
   if (*s >= '0' && *s < '9')
    vec[i++] = *s - '0';
  return vec;
 }

 template  void result(const R& r, const R& rr) const
 {
#if 1
  for (typename R::const_iterator i = r.begin(), ie = r.end(); i != ie; ++i)
   std::cout << *i << "\n\n";
#else
  for (int n = 0; n < 3; ++n)
  {
   for (typename R::const_iterator i = r.begin(), ie = r.end(); i != ie; ++i)
   {
    for (int x = 0; x < 3; ++x)
     std::cout << i->at(3*n+x) << " ";
    std::cout << "| ";
   }
   std::cout << std::endl;
  }
#endif
 }

 Code8 finish_, start_;
};

int main()
{
 const char* beg = 
  "4 3 2"
  "1 5 0"
  "6 7 8";
 const char* end = 
  "0 1 2"
  "3 4 5"
  "6 7 8";
 EightCode ec(beg, end);
 Astar astar;
 astar.search(ec, ec.start(), ec.finish());
}

应用A*解决最短路径问题

#include 
#include "astar.hpp"

struct MatrixNode
{
 bool MatrixNode::operator==(const MatrixNode& n) const { return x == n.x && y == n.y; }
 int f() const { return g() + h(); }
 int g() const { return dist; }
 int h() const { return left; }
 int g(int val) { return dist = val; }

 MatrixNode(int a, int b, int dst, int lef) : x(a), y(b), dist(dst), left(lef) {}
 int x, y, dist, left;
};

class Matrix
{
 friend struct MatrixNode;

 char const* data;
 const int width, height;
 int endx, endy;

 bool is_passable(int x, int y) const { return data[x + width * y] != '#'; }

 int distance(int x1, int y1, int x2, int y2) const
 {
  int x = std::abs(x1 - x2);
  int y = std::abs(y1 - y2);
  return 10 * std::abs(x - y) + 14 * std::min(x, y);
 }

public:
 typedef MatrixNode element_type;

 explicit Matrix(const char* dat, int len, int w)
  : data(dat), width(w), height(len / w)
 {
  int ix = std::find(data, data + width*height-1, 'E') - data;
  endx = ix % width, endy = ix / width;
 }

 template 
 void foreach_adjacents(const MatrixNode& a, Op op) const
 {
  static int offx[] = {-1, 0,1,-1, /*0,*/ 1,-1, 0, 1};
  static int offy[] = { 1, 1,1, 0, /*0,*/ 0,-1,-1,-1};
  for (size_t i = 0; i < sizeof(offx)/sizeof(int); ++i)
  {
   int x = a.x + offx[i], y = a.y + offy[i];
   if (x >= 0 && x < width && y >= 0 && y < height && is_passable(x, y))
    op(MatrixNode(x, y, a.g() + distance(a.x, a.y, x, y), distance(x, y, endx, endy)));
  }
 }

 MatrixNode start() const
 {
  int ix = std::find(data, data + width*height-1, 'S') - data;
  int x = ix % width, y = ix / width;
  return MatrixNode(x, y, 0, distance(x, y, endx, endy));
 }

 MatrixNode finish() const { return MatrixNode(endx, endy, -1, 0); }

 template  void result(const R& r, const R& rr) const;
};

#include 
#include 

template 
void Matrix::result(const R& r, const R& rr) const
{
 using namespace std;
 string m(data, data + width*height);
 for (typename R::const_iterator i = r.begin(), ie = r.end(); i != ie; ++i)
  m[i->x + width * i->y] = '*';
 for (typename R::const_iterator i = rr.begin(), ie = rr.end(); i != ie; ++i)
  m[i->x + width * i->y] = ' ';
 if (!r.empty())
  m[r.front().x + width * r.front().y] = 'S',
  m[r.back().x + width * r.back().y] = 'E';
 for (int i = 0; i < height; ++i)
  copy(m.begin() + width*i, m.begin() + width*(i+1), ostream_iterator(cout)),
  cout << endl;
}

//struct Print { template  void operator()(const Matrix& m, const R& r, const R& rr) const { m.result(r, rr); } };

int main()
{
# define MATRIX_LINE \
 "############################################################"
# define MATRIX_DATA MATRIX_LINE \
 "#..........................................................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.......S.....................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#######.#######################################............#" \
 "#....#........#............................................#" \
 "#....#........#............................................#" \
 "#....##########............................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#...............................##############.............#" \
 "#...............................#........E...#.............#" \
 "#...............................#............#.............#" \
 "#...............................#............#.............#" \
 "#...............................#............#.............#" \
 "#...............................###########..#.............#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "############################################################"
 Matrix mat1(MATRIX_DATA, sizeof(MATRIX_DATA)-1, sizeof(MATRIX_LINE)-1);
# undef MATRIX_LINE
# undef MATRIX_DATA

# define MATRIX_LINE \
 "###################"
# define MATRIX_DATA MATRIX_LINE \
 "#.................#" \
 "#........#........#" \
 "#........#........#" \
 "#..S.....#.....E..#" \
 "#........#........#" \
 "#........#........#" \
 "#.................#" \
 "###################"
 Matrix mat2(MATRIX_DATA, sizeof(MATRIX_DATA)-1, sizeof(MATRIX_LINE)-1);
# undef MATRIX_LINE
# undef MATRIX_DATA

 Astar astar;
 astar.search(mat1, mat1.start(), mat1.finish());
 astar.search(mat2, mat2.start(), mat2.finish());
 return 0;
}

astar.hpp

#include 
#include 

template 
class Astar
{
 typedef typename Matrix::element_type Element;

 struct Node;
 typedef typename std::list::iterator Iterator;

 struct Node : Element
 {
  Iterator prev;
  Node(Iterator i, const Element& n) : Element(n), prev(i) {}
 };
 struct SelNode
 {
  const Element* node;
  SelNode(const Element& n) : node(&n) {}
  bool operator()(const Node& n) const { return *node == n; }
 };
 struct Alt
 {
  bool operator()(const Node& a, const Node& b) const { return a.f() < b.f(); }
 };

 struct result
 {
  template 
  void operator()(const Matrix& m, const R& r, const R& rr) const { m.result(r, rr); }
 };

 std::list open, closed;

 bool is_closed(const Element& node) const
 {
  return std::find_if(closed.begin(), closed.end(), SelNode(node)) != closed.end();
 }

 void extend_anode(Iterator prev, const Element& node);

public:
 template 
 void search(const Matrix& mat, const Element& beg, const Element& end, Op op);
 void search(const Matrix& mat, const Element& beg, const Element& end)
 {
  return search(mat, beg, end, result());
 }
};

#include 
#include 

template 
template 
void Astar::search(const Matrix& mat, const Element& beg, const Element&, Op op)
{
 open.clear();
 closed.clear();
 closed.push_back(Node(closed.end(), beg));
 for (Iterator i = closed.begin(); i->h(); i = closed.begin())
 {
  using std::tr1::bind;
  mat.foreach_adjacents(*i, bind(&Astar::extend_anode, this, i, _1));
  if (open.empty())
  {
   closed.pop_back();
   op(mat, open, closed);
   return;
  }
  closed.splice(closed.begin(), open,
    std::min_element(open.begin(), open.end(), Alt()));
 }
 Iterator rbeg = closed.begin();
 for (Iterator i = rbeg->prev; i != closed.end(); i = i->prev)
  closed.splice(closed.begin(), closed, i);
 open.splice(open.end(), closed, ++rbeg, closed.end());
 op(mat, closed, open);
}

template 
void Astar::extend_anode(Iterator prev, const Element& e)
{
 if (!this->is_closed(e))
 {
  Iterator i = std::find_if(open.begin(), open.end(), SelNode(e));
  if (i == open.end())
   open.push_back(Node(prev, e));
  else if (e.g() < i->g())
   i->prev = prev, i->g(e.g());
 }
}

A*

#include <list>
#include <algorithm>

class Astar
{
 struct Node;
 typedef std::list<Node>::iterator Iterator;

 std::list<Node> open, closed;
 int endx, endy;

 struct Node
 {
  int x, y;
  Iterator prev;
  int dist;
  Node(int a, int b, Iterator i, int dx) : x(a), y(b), prev(i), dist(dx) {}
 };
 struct SelNode
 {
  int x, y;
  SelNode(int a, int b) : x(a), y(b) {}
  bool operator()(const Node& n) const { return n.x == x && n.y == y; }
 };

 template <class Vm>
 struct Alt
 {
  int x, y;
  const Vm* vm;
  Alt(const Vm& m, int a, int b) : vm(&m), x(a), y(b) {}
  bool operator()(const Node& rhs, const Node& lhs) const
  {
   return rhs.dist + vm->distance(rhs.x,rhs.y, x,y)
      < lhs.dist + vm->distance(lhs.x,lhs.y, x,y);
  }
 };

 bool is_closed(int x, int y) const
 {
  return std::find_if(closed.begin(), closed.end(), SelNode(x,y)) != closed.end();
 }

 template <typename Vm>
 void extend_anode(Iterator prev, int x, int y, const Vm& m);

public:
 template <class Vm, typename Op>
 void search(const Vm& m, std::pair<int,int> beg, std::pair<int,int> end, Op op);
};

#include <tr1/tuple>
#include <tr1/functional>

template <class Vm, typename Op>
void Astar::search(const Vm& m, std::pair<int,int> beg, std::pair<int,int> end, Op op)
{
 open.clear();
 closed.clear();
 std::tr1::tie(endx, endy) = end;
 closed.push_back(Node(beg.first, beg.second, closed.end(), 0));
 for (Iterator i = closed.begin(); i->x != endx || i->y != endy; i = closed.begin())
 {
  m.foreach_adjacents(i->x, i->y,
    std::tr1::bind(&Astar::extend_anode<Vm>, this, i, _1, _2, _3));
  if (open.empty())
  {
   closed.pop_back();
   op(m, open, closed);
   return;
  }
  closed.splice(closed.begin(), open,
    std::min_element(open.begin(), open.end(), Alt<Vm>(m, endx, endy)));
 }
 Iterator rbeg = closed.begin();
 for (Iterator i = rbeg->prev; i != closed.end(); i = i->prev)
  closed.splice(closed.begin(), closed, i);
 open.splice(open.end(), closed, ++rbeg, closed.end());
 op(m, closed, open);
}

template <class Vm>
void Astar::extend_anode(Iterator prev, int x, int y, const Vm& m)
{
 if (!this->is_closed(x, y))
 {
  int dist = prev->dist + m.distance(x,y, prev->x,prev->y);
  Iterator i = std::find_if(open.begin(), open.end(), SelNode(x,y));
  if (i == open.end())
   open.push_back(Node(x, y, prev, dist));
  else if (dist < i->dist)
   i->prev = prev, i->dist = dist;
 }
}

///////////////////////////////////////////////////////////////////////////
#include <cstdlib>

class Matrix
{
 char const* data;
 const int width, height;

 bool is_passable(int x, int y) const { return data[x + width * y] != '#'; }

public:
 explicit Matrix(const char* dat, int len, int w)
  : data(dat), width(w), height(len / w)
 {}

 int distance(int x, int y, int xx, int yy) const
 {
  int a = std::abs(x - xx);
  int b = std::abs(y - yy);
  return 10 * std::abs(a - b) + 14 * std::min(a, b);
 }

 template <typename Op>
 void foreach_adjacents(int xx, int yy, Op op) const
 {
  static int offx[] = {-1, 0,1,-1, /*0,*/ 1,-1, 0, 1};
  static int offy[] = { 1, 1,1, 0, /*0,*/ 0,-1,-1,-1};
  for (int i = 0; i < sizeof(offx) / sizeof(int); ++i)
  {
   int x = xx + offx[i], y = yy + offy[i];
   if (x >= 0 && x < width && y >= 0 && y < height && is_passable(x, y))
    op(x, y, *this);
  }
 }

 std::pair<int,int> begin() const
 {
  int ix = std::find(data, data + width*height-1, 'S') - data;
  return std::make_pair(ix % width, ix / width);
 }

 std::pair<int,int> end() const
 {
  int ix = std::find(data, data + width*height-1, 'E') - data;
  return std::make_pair(ix % width, ix / width);
 }

 template <typename R> void print(const R& r, const R& rr) const;
};

#include <iostream>
#include <iterator>

template <typename R>
void Matrix::print(const R& r, const R& rr) const
{
 using namespace std;
 string m(data, data + width*height);
 for (typename R::const_iterator i = r.begin(), ie = r.end(); i != ie; ++i)
  m[i->x + width * i->y] = '*';
 for (typename R::const_iterator i = rr.begin(), ie = rr.end(); i != ie; ++i)
  m[i->x + width * i->y] = ' ';
 if (!r.empty())
  m[r.front().x + width * r.front().y] = 'B',
  m[r.back().x + width * r.back().y] = 'E';
 for (int i = 0; i < height; ++i)
  copy(m.begin() + width*i, m.begin() + width*(i+1), ostream_iterator<char>(cout)),
  cout << endl;
}

struct Print
{
 template <typename R>
 void operator()(const Matrix& m, const R& r, const R& rr) const { m.print(r, rr); }
};

int main()
{
# define MATRIX_LINE \
 "############################################################"
# define MATRIX_DATA MATRIX_LINE \
 "#..........................................................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.......S.....................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#######.#######################################............#" \
 "#....#........#............................................#" \
 "#....#........#............................................#" \
 "#....##########............................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#...............................##############.............#" \
 "#...............................#........E...#.............#" \
 "#...............................#............#.............#" \
 "#...............................#............#.............#" \
 "#...............................#............#.............#" \
 "#...............................###########..#.............#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "############################################################"
 Matrix mat1(MATRIX_DATA, sizeof(MATRIX_DATA)-1, sizeof(MATRIX_LINE)-1);
# undef MATRIX_LINE
# undef MATRIX_DATA

# define MATRIX_LINE \
 "###################"
# define MATRIX_DATA MATRIX_LINE \
 "#.................#" \
 "#........#........#" \
 "#........#........#" \
 "#..S.....#.....E..#" \
 "#........#........#" \
 "#........#........#" \
 "#.................#" \
 "###################"
 Matrix mat2(MATRIX_DATA, sizeof(MATRIX_DATA)-1, sizeof(MATRIX_LINE)-1);
# undef MATRIX_LINE
# undef MATRIX_DATA

 Astar astar;
 astar.search(mat1, mat1.begin(), mat1.end(), Print());
 astar.search(mat2, mat2.begin(), mat2.end(), Print());
}