银河美术馆-Beautyyu

这里是Beautyyu言醴的独立博客
越是孤单 越是向前 越是疲倦 越不能歇
——《未来的我》

a*学习笔记

#a*学习笔记

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

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

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

###a*基本概念

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

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

###a*操作方式

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

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

###值得注意的是

  1. 当一个状态被放入openset之后,它可能还会被其他状态所拓展来的替代,即上边的3-2-1的情况,因此:goal进入openset中后,我们并未得到最优路径,当它进入offset时的路径才是最优的,这点与朴素的bfs是不同的
  2. 对于上边的3-2-2的情况:由于新状态的G值优于原有状态的G值,因此它的F值也更优,直接扔进堆中一定在原有的状态之上,也就是说:3-2-2和3-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;
    }

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
如非注明,所有图片均来源于网络,如若侵删
Link to this article: https://blog.beautyyuyanli.ml/2018/03/04/2018-3-04-astarNote/