32个重要算法之A星算法

    和上一篇一样(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星算法的程序模板，如下：

#include <list>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>

template <typename Type=double>
class property{
public:
    property():h(Type(0)),g(Type(0)),f(Type(0)){};
public:
    Type h;
    Type g;
    Type f;
};

template <typename Node_Type,typename Property_Type=double>
class node{
public:
    typedef node<Node_Type,Property_Type> Type;
public:
    node(){}
    node(const Node_Type& _v,const property<Property_Type>& _p)
        :value(_v),prprt(_p){}
    ~node(){}
public:
    bool const operator < (const Type& other)const{
        return prprt.f < other.get_property_f();
    }
    bool const operator == (const Type& other)const{
        return prprt.f == other.get_property_f();
    }
    bool const operator != (const Type& other)const{
        return !(operator==(other));
    }
public:
    const Property_Type& get_property_h(void)const{return h;}
    const Property_Type& get_property_g(void)const{return g;}
    const Property_Type& get_property_f(void)const{return f;}
    const Node_Type& get_node_value(void)const{return value;}

    void set_property_h(const Property_Type& _h){h = _h;}
    void set_property_g(const Property_Type& _g){g = _g;}
    void set_property_f(const Property_Type& _f){f = _f;}
private:
    property<Property_Type> prprt;
    Node_Type value;
};

template <typename Node_Type,typename Property_Type=double>
class distance{
public:
    typedef node<Node_Type,Property_Type> Data_Type;
public:
    distance(const Data_Type& _n):_node(_n){}
    distance(){}
public:
    const void operator()(const Data_Type& rhs)const{
        if(Property_Type(1) == calc_distance(rhs)){
            Property_Type f = rhs.get_property_f()+Property_Type(1);
            Property_Type g = calc_distance(rhs,dstntn);
            open_collection.push(rhs);
        }
    }
public:
    Property_Type calc_distance(const Data_Type& rhs){
        Property_Type rst;
        //自己定义符合要求的距离
        return rst;
    }
private:
    Data_Type _node;
};

template<typename Node_Type,typename Property_Type=double,
    typename Collection_Type = std::priority_queue<node<Node_Type,Property_Type> > >
class a_star{
public:
    typedef node<Node_Type,Property_Type> Data_Type;
public:
    a_star(Data_Type s,Data_Type d):src(s),dsntn(d){}
    a_star(){}
    ~a_star(){}
private:
    void fomat_data(const Node_Type& s){
        s.set_property_h(0);
        s.set_property_g(0);
        s.set_property_f(0);

        data_collection.push(s);
    };
public:
    void init_data(std::set<Node_Type>v){
        for_each(v.begin(),v.end(),fomat_data);
    }
private:
    void insert_open_list(const Data_Type& n){
        for_each(data_collection.begin(),data_collection.end(),distance<Node_Type>(n));
    }
public:
    void a_star_start(){
        open_collection.push(src);
        do{
            close_collection.push(open_collection.front());
            open_collection.pop();
            cur_node = &(close_collection.top());
            if(close_collection.top() == dsntn)
                break;
            insert_open_list(&(close_list.top()));
        }while(!open_collection.empty());
    }
private:
    friend class distance<Node_Type>;
private:
    std::set<Data_Type> data_collection;
    std::stack<Data_Type> close_collection;
    Collection_Type open_collection;
private:
    Data_Type src;
    Data_Type dsntn;
};

下面对上面代码进行简要的说明 ：A星算法主要涉及到两方面，一是集合的选择，二是h(n)的评估，上面的代码对这两方面进行了抽象，每次只需选择适合的集合，已经定义一种估计h(n)的方法即可。

本文出处：http://blog.chinaunix.net/uid-28311809-id-3890698.html