32个重要算法之A星算法

20030阅读　0评论2013-09-08　bl竹子
分类：C/C++

    和上一篇一样(http://blog.chinaunix.net/uid-28311809-id-3874518.html)，都是对网站()算法的总结与实现，这篇博文首先总结下A星算法，然后给出一个基于C++的A星算法的模板。下面是正文
    我们知道在求解搜索问题的最优解时经常会用到Dijkstra算法，Dijkstra是一种盲目的搜索算法，它会遍历整个解空间然后找到其中的最优解。Dijkstra算法可以准确的找到最优解，但它是以时间为代价的，其时间复杂度为O(n^2)。我们仔细观察Dijkstra算法会发现，它每次得到的解都是距原点最近的那条路径，这样当它遍历到目标点时，得到的路径自然是最优路径，Dijkstra速度之所以慢是因为它毫无例外的盲目遍历每个点，这自然带来许多不必要的开销。如果我们知道关于目的节点的更多信息，比如每个点到目的节点的距离，这样就可以更加有目的的选择一些点，而放弃另一些点，也就是启发式算法啦。如果我们仅仅只考虑当前节点到目的节点的距离，进行贪心选择，那就是所谓的最佳优选(BFS)搜索，我们知道贪心算法获得的解不一定是最优解(只有局部最优解等于全局最优解时贪心算法得到的解才是最优解)，比如在图的搜索过程中遇到障碍物时，BFS算法就不能找到最优路径。于是人们自然地将这两种算法结合起来，也就是每次选择得点到源节点和目的节点之和最小的点。由上所述，很容易得到下面的公式：
                      f(n) = g(n)+h(n)
g(n)表示节点n到源节点的距离，h(n)表示到目的节点的距离。下面对上述公式作简要说明：
    1)当h(n)=0时，A星算法就转化为了Dijkstra算法，即：每次只考虑到源节点最近的节点。
    2)当g(n)=0时，A星算法就转化为了BFS算法，即：每次只考虑到目的节点最近的节点
    3)h(n)是一种对当前节点到目的节点的估计值，如果此估计值精确度等于实际值，那么A星算法可以非常高速的找到最优路径(搜索过程中几乎不会走
       弯路) ，如果h(n) 经常都比从n节点移动到目的节点的实际代价小或等于，那么A星算法保证能找到一条最短路径。如果h(n) 有时比从n节点移动到目       的节点的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。也就是说我们在利用A星算法求解时，应该把握准确性与速度的均衡。
下面给出A星算法的程序模板，如下：

点击(此处)折叠或打开

  1. #include <list>
  2. #include <set>
  3. #include <queue>
  4. #include <stack>
  5. #include <utility>
  6. #include <algorithm>

  8. template <typename Type=double>
  9. class property{
  10. public:
  11.     property():h(Type(0)),g(Type(0)),f(Type(0)){};
  12. public:
  13.     Type h;
  14.     Type g;
  15.     Type f;
  16. };

  18. template <typename Node_Type,typename Property_Type=double>
  19. class node{
  20. public:
  21.     typedef node<Node_Type,Property_Type> Type;
  22. public:
  23.     node(){}
  24.     node(const Node_Type& _v,const property<Property_Type>& _p)
  25.         :value(_v),prprt(_p){}
  26.     ~node(){}
  27. public:
  28.     bool const operator < (const Type& other)const{
  29.         return prprt.f < other.get_property_f();
  30.     }
  31.     bool const operator == (const Type& other)const{
  32.         return prprt.f == other.get_property_f();
  33.     }
  34.     bool const operator != (const Type& other)const{
  35.         return !(operator==(other));
  36.     }
  37. public:
  38.     const Property_Type& get_property_h(void)const{return h;}
  39.     const Property_Type& get_property_g(void)const{return g;}
  40.     const Property_Type& get_property_f(void)const{return f;}
  41.     const Node_Type& get_node_value(void)const{return value;}
  42.     
  43.     void set_property_h(const Property_Type& _h){h = _h;}
  44.     void set_property_g(const Property_Type& _g){g = _g;}
  45.     void set_property_f(const Property_Type& _f){f = _f;}
  46. private:
  47.     property<Property_Type> prprt;
  48.     Node_Type value;
  49. };

  51. template <typename Node_Type,typename Property_Type=double>
  52. class distance{
  53. public:
  54.     typedef node<Node_Type,Property_Type> Data_Type;
  55. public:
  56.     distance(const Data_Type& _n):_node(_n){}
  57.     distance(){}
  58. public:
  59.     const void operator()(const Data_Type& rhs)const{
  60.         if(Property_Type(1) == calc_distance(rhs)){
  61.             Property_Type f = rhs.get_property_f()+Property_Type(1);
  62.             Property_Type g = calc_distance(rhs,dstntn);
  63.             open_collection.push(rhs);
  64.         }
  65.     }
  66. public:
  67.     Property_Type calc_distance(const Data_Type& rhs){
  68.         Property_Type rst;
  69.         //自己定义符合要求的距离
  70.         return rst;
  71.     }
  72. private:
  73.     Data_Type _node;
  74. };

  76. template<typename Node_Type,typename Property_Type=double,
  77.     typename Collection_Type = std::priority_queue<node<Node_Type,Property_Type> > >
  78. class a_star{
  79. public:
  80.     typedef node<Node_Type,Property_Type> Data_Type;
  81. public:
  82.     a_star(Data_Type s,Data_Type d):src(s),dsntn(d){}
  83.     a_star(){}
  84.     ~a_star(){}
  85. private:
  86.     void fomat_data(const Node_Type& s){
  87.         s.set_property_h(0);
  88.         s.set_property_g(0);
  89.         s.set_property_f(0);
  90.         
  91.         data_collection.push(s);
  92.     };
  93. public:
  94.     void init_data(std::set<Node_Type>v){
  95.         for_each(v.begin(),v.end(),fomat_data);
  96.     }
  97. private:
  98.     void insert_open_list(const Data_Type& n){
  99.         for_each(data_collection.begin(),data_collection.end(),distance<Node_Type>(n));
  100.     }
  101. public:
  102.     void a_star_start(){
  103.         open_collection.push(src);
  104.         do{
  105.             close_collection.push(open_collection.front());
  106.             open_collection.pop();
  107.             cur_node = &(close_collection.top());
  108.             if(close_collection.top() == dsntn)
  109.                 break;
  110.             insert_open_list(&(close_list.top()));
  111.         }while(!open_collection.empty());
  112.     }
  113. private:
  114.     friend class distance<Node_Type>;
  115. private:
  116.     std::set<Data_Type> data_collection;
  117.     std::stack<Data_Type> close_collection;
  118.     Collection_Type open_collection;
  119. private:
  120.     Data_Type src;
  121.     Data_Type dsntn;
  122. };
下面对上面代码进行简要的说明 ：A星算法主要涉及到两方面，一是集合的选择，二是h(n)的评估，上面的代码对这两方面进行了抽象，每次只需选择适合的集合，已经定义一种估计h(n)的方法即可。

本文出处：http://blog.chinaunix.net/uid-28311809-id-3890698.html
上一篇：32个重要算法之动态规划算法
下一篇：Boost Asio之Resolver