人工智能-第三章节搜索推理技术1课件

《人工智能-第三章节搜索推理技术1课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能主讲:吴顺祥教授模式识别与智能系统研究所Powerpoint第三章搜索推理技术3.6产生式系统3.7系统组织技术3.8不确定性推理3.9非单调推理3.10小结3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统第三章搜索推理技术讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。3中南大学智能系统与智能软件研究所第三章搜索推理技术从问题表示到问题的解决，有一个求解的过程。接下来要研究的是实现求解的过程，采用的基本方法包括搜索和推理。本章先介绍搜索技术，将要讨论问题求解的搜索原理

2、，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，包括算法、遗传算法和模拟退火算法等。4中南大学智能系统与智能软件研究所3.1图搜索策略例子：从某王姓家族的四代中找王A的后代且其寿命为X的人。　　王A：寿命47，有儿子王B1、王B3、王B2王B1：寿命77，有儿子王C1、王C2王B3：寿命52，有儿子王D1王B2：寿命65，有儿子王E1、王E2王F1：寿命32王G1：寿命96王C2：寿命87，有儿子王F1王D1：寿命77，没有儿子　　王E1：寿命57，有儿子王G1王E2：寿命92，有儿子王H1王C1：寿命27，没有儿子

3、　　王H1：寿命51若X=57，下面讨论一种可通用的图搜索策略求解此问题。5中南大学智能系统与智能软件研究所3.1图搜索策略如果是一个N代的家族表中找其寿命为X的人，我们最可能用的手工方法是从家族表的开始往下，例中还要求所找的人是某人的后代，就比较复杂了。如果用图来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后顺序。图示为：6中南大学智能系统与智能软件研究所3.1图搜索策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变

4、换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程图7中南大学智能系统与智能软件研究所图搜索过程图搜索(GRAPHSEARCH)的一般过程如下：(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。(2)建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G

5、中沿着指从n到S这条路径而得到的(指针将在第7步中设置)。8中南大学智能系统与智能软件研究所图搜索过程(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)GOL

6、OOP。9中南大学智能系统与智能软件研究所图搜索过程图搜索算法中的几个重要名词1．OPEN表：包括节点和父节点。2．CLOSED表：包括节点编号、节点和父节点。3．搜索图与搜索树此过程生成一个明确的图G(称为搜索图)和一个G的子集T(称为搜索树)，树T上的每个节点也在图G中。搜索树是由第7步中设置的指针来确定的。G中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。图搜索过程图如下：10中南大学智能系统与智能软件研究所开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n

7、的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.1图搜索策略11中南大学智能系统与智能软件研究所图搜索方法的几点分析：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路