资源描述：
《人工智能 哈工大 第3 章 搜索推理技术2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第第33章章搜索推理技术搜索推理技术讲师讲师::单丽莉单丽莉IT&NLPIT&NLPhttp://http://www.insun.hit.edu.cnwww.insun.hit.edu.cn2005-4-20IT&NLPLilyShan1第第33章章搜索推理技术搜索推理技术3.13.1图搜索策略图搜索策略3.23.2盲目搜索盲目搜索3.33.3启发式搜索启发式搜索3.43.4消解原理消解原理3.53.5规则演绎系统规则演绎系统3.63.6产生式系统产生式系统3.73.7系统组织技术系统组织技术3.83.8不确定性推理不确定性推理2
2、005-4-20IT&NLPLilyShan23.13.1图搜索策略图搜索策略3.1.13.1.1问题求解的过程问题求解的过程3.1.23.1.2图搜索的一般过程图搜索的一般过程2005-4-20IT&NLPLilyShan33.1.13.1.1问题求解的过程问题求解的过程1.1.问题的表示问题的表示::主要采用状态空间法主要采用状态空间法((状态空间状态空间图图))和问题归约法和问题归约法((与或图与或图).).2.2.问题的求解问题的求解::通过在图通过在图((““状态空间图状态空间图””或或””与与或图或图””))中进行搜索中
3、进行搜索,,寻找一条路径的方法寻找一条路径的方法..–一般搜索:从初始节点出发,扩展节点,并沿子节点推进,继续扩展选择的子节点,直到找到通向目标结点的路径,或找到解树为止.¢肓目搜索:是按预定的控制策略进行搜索,在搜索过程中获得的中间信息并不改变控制策略。¢启发式搜索:是在搜索过程中加入了与问题有关的启发性信息,缩小问题的搜索范围，指导搜索朝着最有希望的方向前进，以尽快地找到问题的（最优）解.43.1.23.1.2图搜索的一般过程图搜索的一般过程¢数据结构:–OPEN:未扩展节点表–CLOSED:已扩展节点表¢算法过程(1)建立一个
4、只含有起始节点S的搜索图G,把S放到一个叫作OPEN的未扩展节点表中;(2)建立一个叫做CLOSED的已扩展节点表,其初始为空表;(3)LOOP:若OPEN表是空表,则失败退出;(4)选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中,称此节点为节点n;(5)若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第(7)步中设置);53.1.23.1.2图搜索的一般过程图搜索的一般过程((续续))(6)扩展节点n,同时生成不是n的祖先的那些后继节点的集合M.把M的这些成员
5、作为n的后继节点添入图G中;(7)对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表中出现过的)M成员设置一个通向n的指针,把M的这些成员加进OPEN表.对已经在OPEN或CLOSED表上的每一个M成员,确定是否需要更改通到n的指针方向.对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向;(8)按某一任意方式或按某个探试值,重排OPEN表;(9)GoLoop.2005-4-20IT&NLPLilyShan63.1.23.1.2图搜索的一般过程图搜索的一般过程((续续))开始把S放入O
6、PEN表是OPEN表为空?失败否把第一个节点(n)从OPEN表移至CLOSED表是n是否为目标节点?成功否把n的后继节点n放入OPEN表的末端,提供返回节点n的指针修改指针方向重排OPEN表图3.1图搜索过程框图73.1.23.1.2图搜索的一般过程图搜索的一般过程((续续))过程说明过程说明::①①搜索图搜索图::图搜索的一般过程生成一个明确图图搜索的一般过程生成一个明确图G,G,称为搜索图称为搜索图..②②搜索树搜索树::图搜索的一般过程生成图搜索的一般过程生成GG的一个子的一个子集集TT称为搜索树称为搜索树..由步骤由步骤(7
7、)(7)中设置的指针来中设置的指针来确定确定..③③GG中每个节点中每个节点(S(S除外除外))都有一个只指向都有一个只指向GG中一中一个父辈节点的指针个父辈节点的指针,,该父辈节点就定为树中该父辈节点就定为树中那个节点的惟一父辈节点那个节点的惟一父辈节点..④④OPENOPEN表上的节点都是搜索图上未被扩展的表上的节点都是搜索图上未被扩展的端节点端节点,,而而CLOSEDCLOSED表上的节点表上的节点,,或者是已或者是已被扩展但没有生成后继节点的端节点被扩展但没有生成后继节点的端节点,,或者或者是搜索树的非端节点是搜索树的非端节
8、点..2005-4-20IT&NLPLilyShan83.1.23.1.2图搜索的一般过程图搜索的一般过程((续续))⑤⑤步骤步骤(8)(8)对对OPENOPEN表上的节点进行排序表上的节点进行排序,,以便以便选出一个选出一个””最好
