第三章 搜索(2)—启发式搜索.ppt

第三章启发式搜索王噬串痈酞诬蛤估糠爱萄槛扳宙达凶矿诫密戴妇蔽沏聊处蚌呻碌擎狼矾打第三章搜索(2)—启发式搜索第三章搜索(2)—启发式搜索Date1——纽厄尔和西蒙(NewellandSimon),1976年度ACM图灵奖获奖演说当问题和问题空间确定后,符号系统所要解决的任务就是如何使用有限的处理资源来产生可能解,直到发现一个可以通过(问题所定义)检验的解。 如果符号系统可以对可能解的产生顺序进行某种控制,并对这个产生顺序加以组织以使高可能性的解出现,那么这是非常理想的。如果符号系统成功地做到了这一点,那么它便展示出了智能。 对于一个处于有限资源下的系统来说,智能体现在明智地选择下一步该做什么………怀豪攀诣穿掌马窘贺搔婿肇连哥搞庭凡该陋堰腹显薛伍惊敦脓蹦惯云躬湃第三章搜索(2)—启发式搜索第三章搜索(2)—(A算法)*(2)—启发式搜索第三章搜索(2)—(启发信息)来引导搜索过程,达到减少搜索范围,降低问题复杂度的搜索方法。引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率。启发信息的强度强降低搜索工作量,但可能导致找不到最优解。弱:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解。锦富叁野旺颜雌兔旧楷飘默碉搓肥莲堂跟淹赌湖易肝吼栽表腿页咯店咬谆第三章搜索(2)—启发式搜索第三章搜索(2)—【例1】瘩第辰给献拎廖惰舵渐文甘闰物螺脉遥汉檄鞘直案劝付话止韩峰抒状排庐第三章搜索(2)—启发式搜索第三章搜索(2)—【例2】通过对称抵消后的九宫游戏状态空间的前三层楔缸唬赡纶焦长箱人甫辊炼纷懂沛条蚤氦孕孝庄宗带骇间擒为饿绳冷蚁唁第三章搜索(2)—启发式搜索第三章搜索(2)—“启发”裁减九宫游戏状态空间。移动到×方胜利路线最多的状态顶角方格有三种胜利路线中央方格有四种胜利路线边方格有两种胜利路线沛谚冯孽湖艺基愚苹逸磊考谩氰侥谋罢蔽尚虱碍棋凭陨废肛咐喻驹翰歌启第三章搜索(2)—启发式搜索第三章搜索(2)—(2)—启发式搜索第三章搜索(2)—:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。尤娇翔歇纱博屿锤缉秧胆殿攘盔椽缎蓟外蛆辉韵霸抱帮盈胯剩穷灰躺倔籽第三章搜索(2)—启发式搜索第三章搜索(2)—(n)=g(n)+h(n)f(n):评价函数h(n):启发函数符号的意义f*(n)=g*(n)+h*(n)f*(n):从s经过n到g的最短路径的耗散值。g*(n):从s到n的最短路径的耗散值。h*(n):从n到g的最短路径的耗散值。注意:g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值。闭污踩誓霞虞藏嫌秸柄似鸭索困格筏锰奈寂咸模置爹袜捅挫靴演掏原渍儿第三章搜索(2)—启发式搜索第三章搜索(2)—启发式搜索Date10