百度一下 藏锋者 就能快速找到本站! 每日资讯归档 下载藏锋者到桌面一键访问

当前位置:主页 > 人工智能 > 人工智能之爬山法

人工智能之爬山法

所在栏目:人工智能 时间:10-15 10:16 分享:

爬山方法是一种局部择优的方法,是采用启发式方法,对深度优先搜索的一种改进。前面讲述的“生成与测试”搜索只是扩展搜索空间,并且在该空间中检测目标是否出现。这种方法几乎是一种耗尽式搜索,效率很低,于是人们考虑是否可以利用反馈信息以帮助决定生成什么样的解,这就是爬山法。爬山法采用了前面定义的评估函数f(x)用来估计目标状态和当前状态的“距离”。当一个节点被扩展以后,对节点x进行评估得到f(x),按f(x)的升序排列这些函数值,并把这些节点按f(x)的升序压入栈。所以,栈顶元素具有最小的f(x)值。

现在弹出栈顶元素并和目标节点比较,如果栈顶元素不是目标,则扩展栈顶元素,并计算其所有子状态的f值,同时按升序把这些子状态压入栈中。如果栈顶元素是目标,则算法退出,否则该过程会循环下去,直到栈为空。下面给出它的搜索过程:算法3.5 爬山法。

ProcedureHill-ClimbingBegin(1)确定可能的开始状态并测量它们和目标节点的距离(f);以f升序排列把这些节点压入栈;(2)Repeat弹出栈顶元素;If栈顶元素=goal;返回并结束;Else把该元素的子女以f升序排列压入栈中;Until栈为空;End.爬山法一般有下面3个问题:

(1)局部最大:

由于爬山法每次选择f值最小的节点时都是从子节点范围内选择,选择范围较窄。因此爬山法是一种局部择优的方法。局部最大一般比状态空间中全局最大要小,一旦到达了局部最大,算法就会停止,即便该答案可能并不能让人满意。

(2)平顶(Plateau):

平顶是状态空间中评估函数值基本不变的一个区域,也称为高地,在某一局部点周围f(x)为常量。一旦搜索到达了一个平顶,搜索就无法确定要搜索的最佳方向,会产生随机走动,这使得搜索效率降低。

(3)山脊(Ridge):

山脊可能具有陡峭的斜面,所以搜索可以比较容易地到达山脊的顶部,但是山脊的顶部到山峰之间可能倾斜得很平缓。除非正好有合适的操作符直接沿着山脊的顶部移动,否则该搜索可能会在山脊的两面来回震荡,搜索的前进步伐会很小。

在每种情况中,算法都会到达一个点,使得算法无法继续前进。如果出现这种情况,可以从另外一个点重新启动该算法,这称为随机重启爬山法。爬山法是否成功和状态空间“表面”的形状有很大的关系:如果只有很少的局部最大,随机重启爬山法将会很快地找到一个比较好的解答。如果该问题是NP完全的,则该算法不可能好于指数时间,这是因为一定具有指数数量的局部最大值。然而,通常经过比较少的步骤,爬山法一般就可以得到比较合理的解答。

人工智能之爬山法 免费邮件订阅: 邮件订阅

图片推荐

热点排行榜

CopyRight? 2013 www.cangfengzhe.com All rights reserved