当前位置: 永利棋牌 > 书评随笔 > 正文

www34511com经典算法研究系列,算法的原理

时间:2019-10-01 13:17来源:书评随笔
启发式算法区别于盲目搜索算法,是搜索策略的一种。主要特点是可以利用问题自身的一些特征信息(启发式信息)来指导搜索的过程,从而可以缩小搜索范围,提高搜索效率。 第一部

启发式算法区别于盲目搜索算法,是搜索策略的一种。主要特点是 可以利用问题自身的一些特征信息(启发式信息)来指导搜索的过程,从而可以缩小搜索范围,提高搜索效率。

第一部分:A*算法简介
    写这篇文章的初衷是应一个网友的要求,当然我也发现现在有关人工智能的中文站点实在太少,我在这里 抛砖引玉,希望大家都来热心的参与。 
    还是说正题,我先拿A*算法开刀,是因为A*在游戏中有它很典型的用法,是人工智能在游戏中的代表。 
    A*算法在人工智能中是一种典型的启发式搜索算法,为了说清楚A*算法,我看还是先说说何谓启发式算法。 

经典算法研究系列:一、A*搜索算法              

实际上,启发式算法也代表了"大拇指准则"(在大多数情况下是成功的,但不能保证一定成功的准则)。

一、何谓启发式搜索算法:  

                     

启发式算法离不开启发式信息,而启发式信息反映在评估函数中。

    在说它之前先提提状态空间搜索。状态空间搜索,如果按专业点的说法就是将问题求解过程表现为从 初始状态到目标状态寻找这个路径的过程。通俗点说,就是在解一个问题时,找到一条解题的过程可以从 求解的开始到问题的结果(好象并不通俗哦)。由于求解问题的过程中分枝有很多,主要是求解过程中求 解条件的不确定性,不完备性造成的,使得求解的路径很多这就构成了一个图,我们说这个图就是状态空 间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜 索。  

作者:July、二零一一年一月

博主说明:
1、本经典算法研究系列,此系列文章写的不够好之处,还望见谅。
2、本经典算法研究系列,系我参考资料,一篇一篇原创所作,转载必须注明作者本人July及出处。
3、本经典算法研究系列,精益求精,不断优化,永久更新,永久勘误。

欢迎,各位,与我一同学习探讨,交流研究。

评估函数f(x)定义为:从初始节点S0出发,约束地经过节点X到达目标节点Sg的所有路径中最小路径代价的估计值。

    常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标 为止。深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。这两种算 法在数据结构书中都有描述,可以参看这些书得到更详细的解释。 

有误之处,不吝指正。

引言
    1968年,的一篇论文,“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。从此,一种精巧、高效的算法------A*算法横空出世了,并在相关领域得到了广泛的应用。

启发式搜索算法
    要理解A*搜寻算法,还得从启发式搜索算法开始谈起。
    所谓启发式搜索,就在于当前搜索结点往下选择下一步结点时,可以通过一个启发函数来进行选择,选择代价最少的结点作为下一步搜索结点而跳转其上(遇到有一个以上代价最少的结点,不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索)。

    DFS和BFS在展开子结点时均属于盲目型搜索,也就是说,它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中,均需要试探完整个解集空间, 显然,只能适用于问题规模不大的搜索问题中。

    而与DFS,BFS不同的是,一个经过仔细设计的启发函数,往往在很快的时间内就可得到一个搜索问题的最优解,对于NP问题,亦可在多项式时间内得到一个较优解。是的,关键就是如何设计这个启发函数。

A*搜寻算法
    A*搜寻算法,俗称A星算法,作为启发式搜索算法中的一种,这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。

    A*算法最为核心的部分,就在于它的一个估值函数的设计上:
        f(n)=g(n)+h(n)

    其中f(n)是每个可能试探点的估值,它有两部分组成:
    一部分,为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。
    另一部分,即h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值,
    h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

   一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是:
      1、搜索树上存在着从起始点到终了点的最优路径。
      2、问题域是有限的。
      3、所有结点的子结点的搜索代价值>0。
      4、h(n)=<h*(n) (h*(n)为实际问题的代价值)。

    当此四个条件都满足时,一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法,并一定能找到最优解。

    对于一个搜索问题,显然,条件1,2,3都是很容易满足的,而条件4: h(n)<=h*(n)是需要精心设计的,由于h*(n)显然是无法知道的,所以,一个满足条件4的启发策略h(n)就来的难能可贵了。

    不过,对于图的最优路径搜索和八数码问题,有些相关策略h(n)不仅很好理解,而且已经在理论上证明是满足条件4的,从而为这个算法的推广起到了决定性的作用。

    且h(n)距离h*(n)的呈度不能过大,否则h(n)就没有过强的区分能力,算法效率并不会很高。对一个好的h(n)的评价是:h(n)在h*(n)的下界之下,并且尽量接近h*(n)。 

 

A*搜寻算法的实现
      先举一个小小的例子:即求V0->V5的路径,V0->V5的过程中,可以经由V1,V2,V3,V4各点达到目的点V5。下面的问题,即是求此起始顶点V0->途径任意顶点V1、V2、V3、V4->目标顶点V5的最短路径。

www34511com 1

//是的,图片是引用rickone 的。
           通过上图,我们可以看出::A*算法最为核心的过程,就在每次选择下一个当前搜索点时,是从所有已探知的但未搜索过点中(可能是不同层,亦可不在同一条支路上),选取f值最小的结点进行展开。
      而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列(即优先队列)进行排列。
      这样,在整体的搜索过程中,只要按照类似广度优先的算法框架,从优先队列中弹出队首元素(f值),对其可能子结点计算g、h和f值,直到优先队列为空(无解)或找到终止点为止。

      A*算法与广度、深度优先和Dijkstra 算法的联系就在于:当g(n)=0时,该算法类似于DFS,当h(n)=0时,该算法类似于BFS。且同时,如果h(n)为0,只需求出g(n),即求出起点到任意顶点n的最短路径,则转化为单源最短路径问题,即Dijkstra算法。这一点,可以通过上面的A*搜索树的具体过程中将h(n)设为0或将g(n)设为0而得到。

A*算法流程:
    首先将起始结点S放入OPEN表,CLOSE表置空,算法开始时:
      1、如果OPEN表不为空,从表头取一个结点n,如果为空算法失败。
      2、n是目标解吗?是,找到一个解(继续寻找,或终止算法)。
      3、将n的所有后继结点展开,就是从n可以直接关联的结点(子结点),如果不在CLOSE表中,就将它们放入OPEN表,并把S放入CLOSE表,同时计算每一个后继结点的估价值f(n),将OPEN表按f(x)排序,最小的放在表头,重复算法,回到1。

//OPEN-->CLOSE,起点-->任意顶点g(n)-->目标顶点h(n)
closedset := the empty set                 //已经被估算的节点集合  
    openset := set containing the initial node //将要被估算的节点集合
    g_score[start] := 0                        //g(n)
    h_score[start] := heuristic_estimate_of_distance(start, goal)    //h(n)
    f_score[start] := h_score[start]    
     
    while openset is not empty    //若OPEN表不为空
        x := the node in openset having the lowest f_score[] value //x为OPEN表中最小的
        if x = goal                                               //如果x是一个解
            return reconstruct_path(came_from,goal)             //
        remove x from openset
        add x to closedset                            //x放入

CLSOE表
        for each y in neighbor_nodes(x)
            if y in closedset
                continue
            tentative_g_score := g_score[x] + dist_between(x,y)

            if y not in openset
                add y to openset
                tentative_is_b

作者:July、二零一一年一月 ---------------------------------- 博主说明: 1、本经典算法研究系列,此系列文...

其一般形式为f(x)=g(x)+h(x),g(x)表示从初始节点S0到节点X的实际代价;h(x)表示从X到目标节点Sg的最优路径的估计代价。但是实际的形式要根据问题特性确定。

    前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状 态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率 实在太低,甚至不可完成。在这里就要用到启发式搜索了。 

A搜索算法

我们通过一个八数码的例子来解释A搜索算法。

(问题描述及插图转载自)

问题描述:

 3×3九宫棋盘,放置数码为1 -8的8个棋牌,剩下一个空格,只能通过棋牌向空格的移动来改变棋盘的布局。

要求:根据给定初始布局(即初始状态)和目标布局(即目标状态),如何移动棋牌才能从初始布局到达目标布局,找到合法的走步序列。

问题讨论:

A搜索算法如何解决八数码问题呢?还记得启发式算法离不开估价函数(f(x)=g(x)+h(x)),那么对于八数码问题我们赋予估价函数实际意义,g(x)是当前被考察和扩展的节点n在搜索图中的节点深度,h(x)是节点X与目标状态Sg相比较,不在目标位的棋牌个数(不包含空格)。

那么初始状态的f(x)=0+4=4。

在解决的过程中,我们还要借助OPEN表,CLOSE表。

OPEN表中存放还未扩展的节点,CLOSE表中存放已扩展的节点。

解题流程:

1,将初始节点装入OPEN表

2,如果OPEN表为空,则失败,退出;否则,取出OPEN表中第一个节点,加入到CLOSE表中。

3,如果节点是目标节点,则成功,退出。

4,如果节点可扩展,将节点的扩展节点加入到OPEN表中,将OPEN表按照估价函数由小到大排列;

否则跳转第2步。

    启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置 进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是 十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 

A*搜索算法

我们同样用八数码问题来解释A* 算法。

A*算法中估价函数的定义:g(x)是当前被考察和扩展的节点n在搜索图中的节点深度,h(x)是节点X与目标状态Sg相比较,每个错位棋牌在假设不受阻拦的情况下,移动到目标状态相应位置所需移动次数的总和(不包含空格)。

A*算法比A算法更有效率。

    启发中的估价是用估价函数表示的,如: 

    f(n) = g(n) + h(n) 

    其中f(n) 是节点n的估价函数,g(n)实在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目 标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。如果说详细 点,g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时,可以省略g(n),而提高效率。这些就深了, 不懂也不影响啦!我们继续看看何谓A*算法。 

二、初识A*算法: 

    启发式搜索其实有很多的算法,比如:局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法 都使用了启发函数,但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法,就是在搜索的过程中 选取“最佳节点”后舍弃其他的兄弟节点,父亲节点,而一直得搜索下去。这种搜索的结果很明显,由于舍 弃了其他的节点,可能也把最好的节点都舍弃了,因为求解的最佳节点只是在该阶段的最佳并不一定是全局 的最佳。最好优先就聪明多了,他在搜索时,便没有舍弃节点(除非该节点是死节点),在每一步的估价中 都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的 丢失。那么A*算法又是一种什么样的算法呢?其实A*算法也是一种最好优先的算法。只不过要加上一些约束 条件罢了。由于在一些问题求解时,我们希望能够求解出状态空间搜索的最短路径,也就是用最快的方法求 解问题,A*就是干这种事情的!我们先下个定义,如果一个估价函数可以找出最短的路径,我们称之为可采 纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数克表示为: 

    f’(n) = g’(n) + h’(n) 

    这里,f’(n)是估价函数,g’(n)是起点到终点的最短路径值,h’(n)是n到目标的最断路经的启发值。由 于这个f’(n)其实是无法预先知道的,所以我们用前面的估价函数f(n)做近似。g(n)代替g’(n),但 g(n)>=g’(n) 才可(大多数情况下都是满足的,可以不用考虑),h(n)代替h’(n),但h(n)<=h’(n)才可(这一点特别的重 要)。可以证明应用这样的估价函数是可以找到最短路径的,也就是可采纳的。我们说应用这种估价函数的 最好优先算法就是A*算法。哈!你懂了吗?肯定没懂!接着看! 

编辑:书评随笔 本文来源:www34511com经典算法研究系列,算法的原理

关键词: