AStar算法应用

最近在网上看到了一个关于最小操作数的问题，感觉挺有意思的，就做了一下。

    题目大概是这样的：字符数相同的一些列单词，例如“hit”、“hot”、“dot”、“dog”、“lot”、“log”、“cog”，从任意一个单词开始（比如hit），每次只能经过一次变换（只改变一个单词及，例如hit到hot），并最终达到目的单词（例如cog），使此过程中经历的变换次数最少，如果存在多条最短变换，则同时输出。

    看到这个问题时，脑袋里立即想到的就是图的搜索算法，深度优先和广度优先，但是我们知道深度优先和广度优先算法都是比较盲目的算，不具有智能想，也就是启发性。于是，自然想到了A Star算法，但标准的A Star算法不能符合要求，需要进行些扩展。下面先简要的介绍A Star算法。

    A Star算法是一种启发式算法，其效果相当于Dijkstra算法（找到最佳路径），在简单的情况下，其速度相当于BFS算法，它具有Dijkstra算法的准确性，也具有BFS的效率，它是两者的结合。这是因为，Dijkstra算法是按着靠近初始点的结点进行贪婪搜索的(设到初始点的距离为f)这样会产生大量的盲目搜索，而BFS 算法是按着靠近目标点结点进行贪婪搜索的（设到目的节点的距离里为g）这样在遇到障碍物时不能及早的躲避，A Star算法是将两者结合在了一起（h=f+g）按着到初始点和目的地之和最短进行搜索，也即按着h值最小进行路径选择的。在这个过程中，一个重要的概念就是距离的定义，例如在游戏中，为NPC的移动选择最短路径时，我们可以按着欧氏距离也可以按着曼哈顿距离（横纵坐标差的绝对值之和），而在上面单词问题中，我选择的是相同位置处的单词是否相同，不同时距离加一（如hit和hot的距离为1，hot与dog的距离为2）。

    上面就是A Star的主要内容啦，下面开始介绍我是如何利用A Star算法去解决最小操作数问题的。首先按着上面所说的方法及距离的定义我们可以很容易的找出一条最短的匹配路径，现在的问题是如果存在不止一条匹配路径时，该如何去做呢？为了解决这个问题，我为每个节点加上了一个指向其“父节点”的指针（例如节点A是节点B的父节点，也就是在进行搜索时，如果现在搜到了A那么下一个所选择的节点为B）这里可能不同节点存在同一个父节点，即多对一的关系。这样我们就可以从目的节点的父节点回溯出整条路径啦。下面给出主要代码

class node_property{
public:
    double f;
    double g;
    double h;
public:
    node_property(const double v_f,const double v_g,const double v_h):f(v_f),g(v_g),h(v_h){}
    node_property():f(0),g(0),h(0){}
};

class node{
public:
    node():parent(NULL){}
    node(const std::string &str,node *p=NULL):node_value(str),parent(p){}
public:
    friend class a_star;
public:
    void set_node_property(const node_property& p){
        memcpy(&property,&p,sizeof(node_property));
    }
    void set_node_property(const double v_f,const double v_g,const double v_h){
        node_property n(v_f,v_g,v_h);
        set_node_property(n);
    }
    void set_node(const node& n){
        node_value = n.node_value;
        parent = n.parent;
        set_node_property(n.property);
    }
public:
        friend size_t calc_distance(const node& lhs,const node& rhs){
            typedef std::string::const_iterator c_iter_type;

            size_t rst = 0;
            c_iter_type lhs_it_b = lhs.node_value.begin();
            c_iter_type lhs_it_e = lhs.node_value.end();
            c_iter_type rhs_it_b = rhs.node_value.begin();
            c_iter_type rhs_it_e = rhs.node_value.end();

            for(;lhs_it_b != lhs_it_e && rhs_it_b != rhs_it_e;)
                if(*lhs_it_b++ != *rhs_it_b++)
                    ++rst;
            return rst;
        }

        node& operator = (const node& rhs){
            if(this != &rhs)
                set_node(rhs);
            return *this;
        }

        bool operator == (const node& n){
            return node_value == n.node_value;
        }

        bool operator != (const node& n){
            return ! this->operator==(n);
        }

        bool operator < (const node &rhs){
            return property.h< rhs.property.h;
        }
private:
    node_property property;
    std::string node_value;
    node *parent;
};

class a_star{
public:
    a_star(const std::list<std::string>&dic,const std::string src,const std::string dstn){
        source.node_value = src;
        destination.node_value = dstn;
        fomat_dictionary(dic);
    };
    ~a_star(){
        destroy(dictionary);
        destroy(open_list);
        destroy(close_list);
    }
private:
    void destroy(std::list<node>nlist){
        nlist.clear();
    }
private:
    void fomat_dictionary(const std::list<std::string>& str){
        for(std::list<std::string>::const_iterator iter = str.begin();
            iter != str.end();)
            dictionary.push_back(node(*iter++));
    };
public:
    //参数为返回的最小匹配集合，返回值为这样最小匹配集合有几个
    size_t begin_a_star(std::list<std::list<std::string> > &rst){
        rst.clear();
        if(source == destination){
            return 0;
        }
        open_list.push_front(source);
        std::multimap<double,node>rst_vector;
        node *cur_node = 0;
        do{
            open_list.sort();
            close_list.push_front(open_list.front());
            open_list.pop_front();
            cur_node = &(close_list.front());
            if(1 == calc_distance(close_list.front(),destination)){
                if(!rst_vector.empty())
                    if(rst_vector.begin()->first < cur_node->property.h+1)
                        break;
                rst_vector.insert(std::make_pair(
                    cur_node->property.h+1,*cur_node));
                continue;
            }
            insert_open_list(*cur_node);
        }while(!open_list.empty());
        if(0 == rst_vector.size())
            std::cout<<"不存在最小操作数"<<std::endl;
        else{
            std::multimap<double,node>::iterator begin = rst_vector.begin();
            std::multimap<double,node>::iterator end = rst_vector.end();
            std::list<std::string>tmp_list;
            for(;begin != end;){
                node *tmp_node = &((begin++)->second);
                for(; NULL && * source;){
                    tmp_list.push_front(tmp_node->node_value);
                    tmp_node = tmp_node->parent;
                }
                tmp_list.push_front(source.node_value);
                tmp_list.push_back(destination.node_value);
                rst.push_back(tmp_list);
                tmp_list.clear();
            }
        }
        return rst_vector.size();
    }
private:
    void insert_open_list(const node& n){
        std::list<node>::iterator traver = dictionary.begin();
        std::list<node>::iterator end = dictionary.end();
        for(;traver != end;){
            if(1 == calc_distance(n,*traver)){
                double f = n.property.f+1;
                double g = calc_distance(*traver,destination);
                traver->set_node_property(f,g,f+g);
                traver->parent = const_cast<node*>(&n);
                open_list.push_front(*traver);
                traver = dictionary.erase(traver);
            }
            else
                ++traver;
        }
    }
private:
    node source,destination;
    std::list<node>     open_list;
    std::list<node>     close_list;
    std::list<node> dictionary;
};

参考文献：