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