人工智能与知识工程_03_搜索推理技术01.ppt

《人工智能与知识工程_03_搜索推理技术01.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能原理第三章搜索推理技术1从问题表示到问题的解决，有一个求解的过程。接下来要研究的是实现求解的过程，采用的基本方法包括搜索和推理。本章先介绍搜索技术，将要讨论问题求解的搜索原理，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，包括A*算法。23.1图搜索策略可把图搜索策略看成一种在图中寻找路径的方法图中的节点对应于状态，而连线对应于操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记初始节点和目标节点之间的路径。即求得把

2、一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题3例子：从某王姓家族的四代中找王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，有儿子王G14王E2：寿命92，有儿子王H1王C1：寿命27，没有儿子　　王H1：寿命51若X=57，下面讨论

3、一种可通用的图搜索策略求解此问题。　　如果是一个N代的家族表中找其寿命为X的人，我们最可能用的手工方法是从家族表的开始往下，例中还要求所找的人是某人的后代，就比较复杂了。如果用图来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后顺序。图示为：5图3.1用图表示方法的家族表6图搜索(GRAPHSEARCH)的一般过程如下：(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。(2)建立一个叫做CLOSED的已扩展节点表（简称CLOSE

4、D表），其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设

5、置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。7图搜索算法中的几个重要名词1．OPEN表2．CLOSED表节点父节点编号节点父节点83．搜索图与搜索树此过程生成一个明确的图G(称为搜索图)和一个G的子集T(称为搜索树)，树T上的每个节点也在图G中。搜索树是由

6、第7步中设置的指针来确定的。G中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。910图搜索方法的几点分析：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针

7、向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。113.2盲目搜索盲目搜索：无需重新安排OPEN表的搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。宽度优先搜索深度优先搜索等代价搜索123.2.1宽度优先搜索回顾上一节的寻找寿命为X的人的例子，如果搜索时，从节点A开始，对他的三个儿子按从左至右搜索，然后对他的所有孙子按从左至右搜索，依此下去。这种搜索方

8、式就是宽度优先搜索。宽度优先搜索(breadth-firstsearch)的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)，如图3.3所示。13从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。图3.3宽度优先搜索示意图1415宽度优先搜索算法如下：(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解