第三章 搜索(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