下载文档原格式
2005-4-20IT&NLP Lily Shan1第3 章搜索推理技术讲师: 单丽莉IT&NLPhttp://2005-4-20IT&NLP Lily Shan 2第3 章搜索推理技术3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统3.6 产生式系统3.7 系统组织技术3.8 不确定性推理2005-4-20IT&NLP Lily Shan 33.1 图搜索策略3.1.1 问题求解的过程3.1.2 图搜索的一般过程443.1.1 问题求解的过程1.问题的表示: 主要采用状态空间法(状态空间图)和问题归约法(与或图).2.问题的求解: 通过在图(“状态空间图”或”与或图”)中进行搜索, 寻找一条路径的方法.–一般搜索: 从初始节点出发, 扩展节点, 并沿子节点推进, 继续扩展选择的子节点, 直到找到通向目标结点的路径, 或找到解树为止.肓目搜索:是按预定的控制策略进行搜索, 在搜索过程中获得的中间信息并不改变控制策略。
启发式搜索: 是在搜索过程中加入了与问题有关的启发性信息, 缩小问题的搜索范围，指导搜索朝着最有希望的方向前进，以尽快地找到问题的（最优）解.553.1.2 图搜索的一般过程数据结构: –OPEN: 未扩展节点表–CLOSED: 已扩展节点表算法过程(1)建立一个只含有起始节点S 的搜索图G, 把S 放到一个叫作OPEN 的未扩展节点表中;(2)建立一个叫做CLOSED 的已扩展节点表, 其初始为空表;(3)LOOP: 若OPEN 表是空表, 则失败退出;(4)选择OPEN 表上的第一个节点,把它从OPEN 表移出并放进CLOSED 表中,称此节点为节点n;(5)若n 为一目标节点,则有解并成功退出, 此解是追踪图G 中沿着指针从n 到S 这条路径而得到的(指针将在第(7)步中设置);2005-4-20IT&NLP Lily Shan 63.1.2 图搜索的一般过程(续)(6)扩展节点n, 同时生成不是n 的祖先的那些后继节点的集合M.把M 的这些成员作为n 的后继节点添入图G 中;(7)对那些未曾在G 中出现过的(即未曾在OPEN 表上或CLOSED 表中出现过的)M 成员设置一个通向n 的指针, 把M 的这些成员加进OPEN 表. 对已经在OPEN 或CLOSED 表上的每一个M 成员,确定是否需要更改通到n 的指针方向. 对已在CLOSED 表上的每个M 成员,确定是否需要更改图G 中通向它的每个后裔节点的指针方向;(8)按某一任意方式或按某个探试值, 重排OPEN 表;(9)Go Loop.7把S 放入OPEN 表OPEN 表为空?失败开始把第一个节点(n )从OPEN 表移至CLOSED 表n 是否为目标节点?成功把n 的后继节点n 放入OPEN 表的末端,提供返回节点n 的指针修改指针方向重排OPEN 表是否是否图3.1 图搜索过程框图2005-4-20IT&NLP Lily Shan 83.1.2 图搜索的一般过程(续)过程说明:①搜索图: 图搜索的一般过程生成一个明确图G, 称为搜索图.②搜索树: 图搜索的一般过程生成G 的一个子集T 称为搜索树. 由步骤(7)中设置的指针来确定.③G 中每个节点(S 除外)都有一个只指向G 中一个父辈节点的指针, 该父辈节点就定为树中那个节点的惟一父辈节点.④OPEN 表上的节点都是搜索图上未被扩展的端节点, 而CLOSED 表上的节点, 或者是已被扩展但没有生成后继节点的端节点, 或者是搜索树的非端节点.93.1.2 图搜索的一般过程(续)⑤步骤(8)对OPEN 表上的节点进行排序, 以便选出一个”最好”的节点作为步骤(4)扩展使用.①排序可以是任意的即肓目的(盲目搜索)②可以用启发信息为依据(启发式搜索)⑥当扩展某个节点时, 搜索图已经保存了从初始节点到该节点的搜索树.⑦每当被选作扩展的节点为目标节点时,这一过程就宣告成功结束. 这时, 从目标节点按指向父节点的指针不断回溯,能够重现从起始节点到目标节点的成功路径.⑧当搜索树不再剩有末被扩展的端节点时(即OPEN 表为空时), 过程就以失败告终. 从起始节点, 达不到目标节点.10⑨步骤(6)扩展节点时, 生成一个节点的所有后继节点.⑩步骤(7)的说明: 特别地用于启发式搜索S 0312图3.2 扩展节点1以前的搜索图45图3.3 扩展节点1以后的搜索图S 0312456788762005-4-20IT&NLP Lily Shan 113.2 盲目搜索3.2.1 宽度优先搜索3.2.1 深度优先搜索3.2.3 等代价搜索12宽度优先搜索: 如果搜索是以接近起始节点的程度来依次扩展节点, 那么这种搜索叫做宽度优先搜索(breadth -first search).SL OM FP FFQ N F图3.4 宽度优先搜索示意图2005-4-20IT&NLP Lily Shan133.2.1 宽度优先搜索(续)宽度优先搜索算法如下:(1)把起始节点放到OPEN 表中(如果该起始节点为一目标节点,则求得一个解答).(2)如果OPEN 是个空表, 则没有解,失败退出;否则继续.(3)把第一个节点(节点n) 从OPEN 表移出,并把它放入CLOSED 的扩展节点表中.(4)扩展节点n. 如果没有后继节点,则转向步骤(2).(5)把n 的所有后继节点放到OPEN 表的末端, 并提供从这些后继节点回到n 的指针.(6)如果n 的任一个后继节点是个目标节点, 则找到一个解答, 成功退出; 否则转向步骤(2);2005-4-20IT&NLP Lily Shan143.2.1 宽度优先搜索(续)宽度优先搜索算法说明:(1)搜索树: 搜索过程产生的节点和指针构成一棵隐式定义的状态空间图的子树, 称为搜索树.(2)如果问题有解, 宽度优先算法能够保证找到一条通向目标节点的最短路径(即找到最优解).(3)如要问题无解,对于有限图,该算法会失败退出;对于无限图,则永远不会终止15把S 放入OPEN 表OPEN 表是否为空表?失败起始把第一个节点n 从OPEN 表移至CLOSED 表扩展n , 把n 的后继节点n 放入OPEN 表的末端,提供返回节点n 的指针是否否图3.5 宽度优先算法框图是否有任何后继节点为目标节点?成功是2005-4-20IT&NLP Lily Shan16例: 八数码难题. 在3×3的方格棋盘上,分别放置了标有数字1,2,3,4,5,6,7,8的八张牌, 初始状态如图3.6 S 0所示, 目标状态如图3.6 S g 所示, 要求应用宽度优先搜索策略寻找从初始状态到目标状态的解路径.2831476512384765图3.6 八数码难题S 0S g177652834765231476528317652831475184683247652837465112314765231476588832476512837465112347658234176588324765183247651283746512837465112347658123476582834175628137652831576442831475283147566281376542831576428317546图3.7 八数码难题的宽度优先搜索树2005-4-20IT&NLP Lily Shan18深度优先搜索: 在搜索过程中, 首先扩展最新产生的(即最深的)节点, 这种搜索叫做深度优先搜索.SL OM FP FFQ N F图3.8 宽度优先搜索示意图193.2.2 深度优先搜索(续)节点深度定义:(1) 起始节点(即根节点)的深度为0.(2) 任何其他节点的深度等于其父辈节点的深度加1.深度界限:–为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去), 往往给出一个节点扩展的最大深度, 称为深度界限.–任何节点如果达到了深度界限,那么都将把它们作为没有后继节点来处理.–即使应用了深度界限, 深度优先搜索所求得的解答路径也不一定就是最短路径.2005-4-20IT&NLP Lily Shan203.2.2 深度优先搜索(续)含有深度界限的深度优先搜索算法:(1)把起始节点S 放到未扩展节点OPEN 表中. 如果此节点为一目标节点,则得到一个解.(2)如果OPEN 为一空表,则失败退出.(3)把第一个节点(节点n)从OPEN 表移到CLOSED 表.(4)如果节点n 的深度等于最大深度,则转向步骤(2).(5)扩展节点n, 产生其全部后裔,并把它们放入OPEN 表的前头.如果没有后裔,则转向步骤(2);(6)如果后继节点中有任一个为目标节点,则求得一个解,成功退出;否则,转向步骤(2);21OPEN 表是否为空?失败把OPEN 表中的第一个节点n 移入CLOSED 表扩展节点n , 把其后裔n 放入OPEN 表的前端,提供返回节点n 的指针是否否是否有任何后继节点为目标节点?成功是图3.9 有界深度优先搜索算法框图S 是否为目标节点?成功是否节点n 的深度是否等于深度界限?是否22765283476523147652831765283147518462314765231476588123476582341765812347658123476582834175628314752831475662813765283157644281376542831576428317546234176582341576828137654248137652813754628316754...图3.10 八数码难题深度界限为4的深度优先搜索树Return to f233.2.3 等代价搜索宽度优先的局限:–在宽度优先搜索中作了一种假设, 认为状态空间中各边的代价都相同, 且都为一个单位量.从而可用路径的长度代替路径的代价.–然而, 对许多问题这种假设是不现实的, 它们的状态空间中的各个边的代价不可能完全相同.例: 城市交通问题.–为此, 需要在搜索树中给每条边都标上其代价.代价树: 在搜索树中给每条边都标上其代价. 这种边上标有代价的树称为代价树.等代价搜索: 寻找从起始状态至目标状态的具有最小代价的路径问题, 叫做等代价搜索.–在等代价搜索算法中, 是沿着等代价路径断层进行扩展的.2005-4-20IT&NLP Lily Shan24例: 城市交通问题. 设有5个城市, 它们之间的交通路线如图3.11所示, 图中的数字表示两个城市之间的交通费用,即代价. 用等代价搜索, 求从A 市出发到E 市, 费用最小的交通路线.ABCDE342453图3.11 城市交通图2005-4-20IT&NLP Lily Shan 25解: 其代价搜索树如右下图:最优解: A,C,D,E AC1D134B2E2E3图3.12 城市交通图的代价搜索树2434523B1E1D2C2ABC DE342453图3.11 城市交通图2005-4-20IT&NLP Lily Shan 263.2.3 等代价搜索(续)记号–c (i , j ): 从节点I 到其后继节点j 的连接弧线代价.–g (i ):从起始节点S 到任一节点i 的路径代价(即是从起始节点S 到节点i 的最少代价路径上的代价).2005-4-20IT&NLP Lily Shan273.2.3 等代价搜索(续)等代价搜索算法:(1)把起始节点S 放到未扩展节点有OPEN 中.如果此起始节点为一目标节点,则求得一个解;否是令g(S )=0.(2)如果OPEN 是个空表,则没有解而失败退出.(3)从OPEN 表中选择一个节点I,使其g(i )为最小.如果有几个节点都合格,那么就要选择一个目标节点作为节点i(如果有目标节点的话);否则,就从中选一个作为节点i ,把节点i 从OPEN 表移至扩展节点表CLOSED 中.2005-4-20IT&NLP Lily Shan283.2.3 等代价搜索(续)等代价搜索算法:(4)如果节点i 为目标节点,则求得一个解.(5)扩展节点i .如果没有后继节点,则转向步骤(2);(6)对于节点i 的每个后继节点j ,计算g (j )=g (i )+c (i ,j ), 并把所有后继节点j 放进OPEN 表.提供回到节点i 的指针.(7)转向步骤(2).29OPEN 表是否为空?失败把具有最小g(i )值的节点i 从OPEN 表移至CLOSED 表扩展节点i , 计算其后继节点j 的g(j)值.把后继节点j 放进OPEN 表是否否i 是否为目标节点?成功是图3.13 等代价搜索算法框图S 是否为目标节点?成功是否否令g(s)=02005-4-20IT&NLP Lily Shan 303.3 启发式搜索3.3.1 启发式搜索策略和估价函数3.3.2 有序搜索3.3.3 A*算法2005-4-20IT&NLP Lily Shan 313.3 启发式搜索(续)盲目搜索存在的问题–扩展节点数目较多.–效率低, 耗费过多的计算时间和空间.–如果选择最有希望的节点加以扩展, 搜索效率将会大为提高.2005-4-20IT&NLP Lily Shan 323.3.1 启发式搜索策略和估价函数 启发性信息: 指那种与具体问题求解过程有关的, 并可指导搜索过程朝着最有希望方向前进的控制信息.–有效地帮助确定扩展节点的信息;–有效的帮助决定哪些后继节点应被生成的信息;–能决定在扩展一个节点时哪些节点应从搜索树上删除的信息.启发式搜索: 利用启发信息的搜索方法叫做启发式搜索.2005-4-20IT&NLP Lily Shan 333.3.1 启发式搜索策略和估价函数(续)估价函数(evaluation function): 用于度量节点的”希望”(此节点在通向目标结点的最佳路径上的”希望”)的量度. 记号f (n ) : 表示节点n 的估价函数值.–用函数f (n )的值来排列图搜索的一般算法中的OPEN 表中节点.–节点按递增顺序排列, 即优先扩展具有低估价值的节点, 根据低估价值节点更有可能处在最佳路径上.2005-4-20IT&NLP Lily Shan 343.3.2 有序搜索有序搜索: 应用某个算法(例如等代价法)选择OPEN 表上具有最小f 值的节点作为下一个要扩展的节点, 这种搜索方法叫做有序搜索或最佳优先搜索, 其算法就叫做有序搜索算法或最佳优先算法.–有序搜索总是选择最有希望的节点作为下一个要扩展的节点.2005-4-20IT&NLP Lily Shan 353.3.2 有序搜索(续)有序状态空间搜索算法:(1)把起始节点S 放到OPEN 表中, 计算f (S ),并把其值与节点S 联系起来.(2)如果OPEN 表是个空表,则失败退出,无解.(3)从OPEN 表中选择一个f 值最小的节点i .结果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i .(4)把节点i 从OPEN 表中移出,并把它放入CLOSED 的扩展节点表中.(5)如果i 是个目标节点,则成功退出,求得一个解.363.3.2 有序搜索(续)(6)扩展节点i , 生成其全部后继节点.对于i 的每一个后继节点j :a)计算f (j ).b)如果j 既不在OPEN 表中,也不在CLOSED 表中,则用估价函数f 把它添入OPEN 表.从j 加一指向父辈节点i 的指针(以便找到目标节点时记住一个解答路径).c)如果j 已在OPEN 表或CLOSED 表上,则比较刚刚对j 计算过的f 值和前面计算过的该节点在表中的f 值.如果新的f 值较小,则I.以此新值取代旧值.II.从j 指向i ,而不是指向它的父辈节点III.如果节点j 在CLOSED 表中,则把它移回OPEN 表(7)转向(2),即GOTO(2);37把S 放入OPEN 表,计算f (s )OPEN 表=NIL?失败开始选取OPEN 表中f 值最小的节点i 放入CLOSED 表扩展节点i , 计算其后继节点j 的f (j)值.提供返回指针,利用f 值对OPEN 表重新排序,调整亲子关系及指针是否否i=S g成功是图3.14 有序搜索算法框图383.3.2 有序搜索(续)在有序搜索中–定义f (i )为节点i 的深度, 则退化为宽度优先算法搜索.–定义f (i )为从起始节点至节点i 这段路径的代价, 则退化为等代价搜索.估价函数的作用–f 的选择直接决定了有序搜索中被扩展节点的数目,即直接影响了搜索算法的效率.–对搜索结果具有决定性的作用.估价函数的选择–一个节点处在最佳路径上的概率；–求出任意一个节点与目标节点集之间的距离度量或差异度量；–根据格局（博弈问题）或状态的特点来打分。
一、教学内容二、教学目标1. 理解机器学习的基本原理，掌握主要的分类和回归算法。
2. 学习神经网络的架构，了解深度学习在多个领域的应用。
三、教学难点与重点教学难点：神经网络的结构与训练过程，深度学习的具体应用。
教学重点：机器学习的基本概念，各类算法的原理及实现。
四、教具与学具准备1. 电脑及投影设备，用于展示课件和实例。
3. 笔记本和教材，供学生记录重点内容。
五、教学过程2. 理论讲解：介绍机器学习的基本概念，讲解各类算法原理。
3. 实例演示：以图像识别为例，展示神经网络的构建与训练过程。
4. 随堂练习：让学生运用所学知识，完成简单的分类和回归任务。
5. 深度学习应用：介绍深度学习在自然语言处理等领域的应用案例。
六、板书设计1. 机器学习基础：分类算法、回归算法。
2. 神经网络与深度学习：结构、训练、优化。
3. 应用案例：图像识别、自然语言处理。
七、作业设计1. 作业题目：（1）简述机器学习的基本概念及其应用。
（2）比较线性回归和逻辑回归的异同点。
2. 答案：（1）机器学习是指让计算机通过数据学习，不断提高性能的过程。
应用领域包括：搜索排名、推荐系统、语音识别等。
（2）线性回归和逻辑回归的异同点：同：都是回归算法，通过优化目标函数求解参数。
异：线性回归适用于连续型输出，逻辑回归适用于二分类输出。
（3）神经网络训练过程：输入数据、前向传播、计算损失、反向传播、更新权重。
八、课后反思及拓展延伸1. 反思：关注学生在课堂上的参与度，及时解答疑问，提高教学效果。
2. 拓展延伸：鼓励学生深入学习相关领域知识，如计算机视觉、自然语言处理等，提高实际应用能力。
组织课外实践活动，让学生在实际项目中锻炼技能。
重点和难点解析：1. 教学难点：神经网络的结构与训练过程。
2. 实例演示：以图像识别为例，展示神经网络的构建与训练过程。
3. 作业设计：神经网络训练过程的详细解答。
详细补充和说明：一、神经网络的结构与训练过程1. 初始化：为神经网络中的权重和偏置赋予随机值。
