人工智能 启发式算法(A,A*) | 您所在的位置:网站首页 › 盲目搜索的三种主要算法是 › 人工智能 启发式算法(A,A*) |
启发式算法区别于盲目搜索算法,是搜索策略的一种。主要特点是 可以利用问题自身的一些特征信息(启发式信息)来指导搜索的过程,从而可以缩小搜索范围,提高搜索效率。 实际上,启发式算法也代表了"大拇指准则"(在大多数情况下是成功的,但不能保证一定成功的准则)。 启发式算法离不开启发式信息,而启发式信息反映在评估函数中。 评估函数f(x)定义为:从初始节点S0出发,约束地经过节点X到达目标节点Sg的所有路径中最小路径代价的估计值。 其一般形式为f(x)=g(x)+h(x),g(x)表示从初始节点S0到节点X的实际代价;h(x)表示从X到目标节点Sg的最优路径的估计代价。但是实际的形式要根据问题特性确定。 A搜索算法我们通过一个八数码的例子来解释A搜索算法。 (问题描述及插图转载自http://www.cnblogs.com/guanghe/p/5485816.html) 问题描述: 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算法更有效率。 |
CopyRight 2018-2019 实验室设备网 版权所有 |