a-star学习笔记

#a*学习笔记

这篇文章是鄙人学习aStar主要参考的文章,私以为对aStar的讲解十分有逻辑了

aStar本质上是一个宽度优先算法 -对于一个状态拓展出它能转移的所有状态将这些状态推入队列再逐个拓展直到目标状态

但不同的是aStar算法中的队列变成了优先队列-对于更有可能优的状态我们优先去拓展它。而优的判定就通过一个启发函数来实现

###a*基本概念

a*一般用于解决最小花费/最大价值问题

起始状态start: 由题面给出的起始状态
目标状态goal: 由题面给出的目标状态
已使用花费g_cost: 由start转移到now的花费
估计花费h_cost : 由now转移到goal的估计花费,在寻路问题中一般使用曼哈顿估价
花费评估f_cost: 评估本条道路的总花费,即f_cost = g_cost + h_cost
开启列表openset: 目前已拓展出的状态,一般是一个以f_cost作为优先度的堆
关闭列表offset: 禁用拓展的状态和处理完成的状态
追溯表comeFrom: 存储父子关系,一般在询问拓展路径的情况下用到

###a*操作方式

从openset中取出F最小的点now,并加入offset
判读该点是否为goal,真则完成搜索过程
对于now转移得neighbor,对于一个neighbor而言:
1. 它在offset中:它被continue了
2. 它在openset中:
  1. 它的G值优于openset中的那位,则将其替代,更新comeFrom
  2. 它的G值不如openset中的那位,则不管它
3. 它不在openset中:加入openset

a*的操作原理大约是这样更具体的讲解可以翻阅篇首提到的博客

###值得注意的是

当一个状态被放入openset之后,它可能还会被其他状态所拓展来的替代,即上边的3-2-1的情况,因此:当goal进入openset中后,我们并未得到最优路径,当它进入offset时的路径才是最优的,这点与朴素的bfs是不同的
对于上边的3-2-2的情况:由于新状态的G值优于原有状态的G值,因此它的F值也更优,直接扔进堆中一定在原有的状态之上,也就是说:3-2-2和3-3并不需要区别处理
offset即bfs中的判重操作,可以是布尔数组也可以是其他东西

##a* 模板

以下均为个人向,c++内容

//status
struct node{
    int ;// value about the state
    int f,g,h;//three cost function
    void forecast(){//update the f_cost and g_cost
        f = g + (h = /*pass*/);
        return ;
    }
    bool ifgoal(){//check if it is goal
        return ;
    }
    bool operator < (const node &al) const{//declear the priority
        return f > al.f;
    }
    void putoffset(){//put the state into the offset
        return;
    }
    bool ifoffset(){//check if the state is in the offset
        return;
    }
};
priority_queue<node> openset;
/*(?) offset*/
bool astar(){
    while (!openset.empty()){
        node r = openset.top();openset.pop();
        if (r.ifgoal()) return 1;
        // when the goal node in the offset ,it is the real best way;
        r.putoffset();
        for (){
            node th = /*a new state*/;
            if (/*it is forbidden*/ || th.ifoffset()) continue;
            th.forecast();
            openset.push(th);
        }
    }
    return 0;
}