Chinaunix首页 | 论坛 | 博客
  • 博客访问: 493153
  • 博文数量: 25
  • 博客积分: 111
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-10-26 20:51
文章分类

全部博文(25)

文章存档

2014年(17)

2013年(8)

分类: C/C++

2013-09-08 21:07:07

    和上一篇一样(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>

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

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

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

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

本文出处:http://blog.chinaunix.net/uid-28311809-id-3890698.html
阅读(19838) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~