《人工智能_第三搜索推理技术讲解》由会员分享，可在线阅读，更多相关《人工智能_第三搜索推理技术讲解（181页珍藏版）》请在金锄头文库上搜索。
1、第三搜索推理技术 从问题的表示到问题的解决是一个求解的过程 ，也就是搜索过程。在这一过程中，采用适当的搜 索技术，包括各种规则、过程和算法等推理技术， 力求找到问题的解答。本章首先介绍图搜索策略的 一般过程，接着讨论一些早期的搜索技术或用于解 决比较简单问题的搜索原理，然后研究一些比较新 的能够求解比较复杂问题的推理技术。 第三确定性推理 3.1图搜索策略 3.2盲目搜索 3.3启发式搜索 3.4消解原理 3.5规则演绎系统 3.6产生式系统 3.7非单调推理 第三搜索推理技术 一般一个问题可以用 好几种搜索技术解决, 选 择一种好的搜索技术对解 决问题的效率很有关系, 甚至关系到求解问题有没
2、 有解。 搜索方法好的标准, 一 般认为有两个： (1)搜索空间小; (2)解最佳。 Sg 3.1图搜索策略 3.1图搜索策略 一.问题描述(图搜索问题描述) 把求解问题看成一个状态图，求初始节点到 目标节点的路径。 3.1.1图搜索策略 回顾一下图论中几个术语的含义。 节点深度：根节点的深度为0, 其他节点的深度规定为父节 点深度加1, 即dn+1=dn+1。 路径：设一节点序列为(n0、n1,ni,nk), 对i=1,2, k, 若节点ni-1都具有一个后继节点ni, 则该节点序列称为节点n0 到节点nK长度为k的一条路径。 路径耗散值：令C(ni,nj)为节点ni到nj 这段路径(或弧线
3、)的 耗散值, 一条路径的耗散值等于连接这条路径各节点间所有 弧线耗散值的总和。路径耗散值可按如下式递归公式计算: C(ni,t)=C(ni,nj)+C(nj,t) C(nj,t)为nit这条路径的耗散值。 3.1.1图搜索策略 回顾一下图论中几个术语的含义。 扩展一个节点: 后继节点操作符(相当于可应用规则)作用到 节点(对应于某一状态描述)上, 生成出其所有后继节点(新状 态), 并给出连接弧线的耗散值(相当于使用规则的代价), 这个 过程叫做扩展一个节点。扩展节点可使定义的隐含图生成为 显式表示的状态空间图。 3.1.1图搜索策略 二.图搜索过程 S起始结点 G搜索图 OPEN 表存放未
4、扩展节点 CLOSED 表存放已扩展节点 1.图搜索过程 (1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做 OPEN的未扩展节点表中。 (2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。 (3)LOOP: 若OPEN表是空表，则失败退出。 (4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进 CLOSED表中，称此节点为节点n。 3.1.1图搜索策略 (5) 若n为一目标节点n，则有解并成功退出。此解是追踪图G 中沿着指针从n到s这条路径而得到的。 (6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合 M。把M的这些成员作为n的后继结点添入图G中。 (7)
5、 对于那些未曾在G中出现过的(既未曾在OPEN表上或 CLOSED表上出现过的)M成员设置一个通向n的指针。把M的 这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每 一个M成员，确定是否需要更改通到n的指针方向。对已经在 CLOSED表上的每一个M成员，确定是否需要更改图G中通向 它的每个后裔节点的指针方向。 (8) 按某一任意方式或按某个探试值，重排OPEN表。 (9)GO LOOP 3.1.1图搜索策略 举例： S AB CDE MFS 1.S OPEN(S) CLOSED( ) 2.A OPEN(A, B) CLOSED(S) 3.B OPRN(B, C, D) CLOSE
6、D(S, A) 4.C OPEN(C, D, E) CLOSED(S, A, B) 5.D OPEN(D,E) CLOSED(S, A,B,C) 6.E OPEN(E,M,F) CLOSED(S, A,B,C,D) 7.N 求解 目标节点 23 5 64 7 38 4 3.1.1图搜索策略 2.流程图 开始 把S放表入OPEN表中 OPEN表为空表 把第一个节点n从OPEN 表移至CLOSED表 N为目标节点 把节点n的后继节点放入OPEN表 ，提供返回节点n的指针 修正指针方向 重排OPEN表 失败 成功 是 是 3.1.1图搜索策略 3.1.1图搜索策略 3.1.1图搜索策略 3.1.1图
7、搜索策略 3.1.1图搜索策略 3.1.1图搜索策略 3.遗留问题 n的某后继节点已在OPEN表中或CLOSED表中有了 是否需要修改指针，对已存在的后继节点 按什么方式重排OPEN表 宽度优先搜索 深度优先搜索 等代价搜索 搜索控制方法 3.2盲目搜索 盲目搜索是不利用问题的有关信息, 而根 据事先确定好的某种固定的搜索方法进行搜 索，又叫做无信息搜索。一般只适用于求解 比较简单的问题。 典型的盲目搜索方法是深度优先搜索和 宽度优先搜索(亦称广度优先搜索), 这是两处 基本搜索方法。 3.2盲目搜索 一.宽度优先搜索 (一).宽度优先搜索 以接近起始节点的程度依次扩展节点 从根结点开始, 每
8、次都要扫遍同层的各个结点, 若没有找到目 标, 则再往下一层扫描(扫描下一层的所有子结点), 直到找到目标 或没有找到目标退出系统(此种属于没有解的情况)。 3.2盲目搜索 (二).流程算法 扩展节点：把它的后继节点放入OPEN表的末端 1.搜索算法 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则 求得一个解答) 如果OPEN表是一个空表，则没有解，失败退出；否则继续。 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的 扩展节点表中。 扩展节点n。如果没有后继节点，则转向第步。 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节 点回到n的指针。 如果n的任
9、一个后继节点是个目标节点，则找到一个解答，成 功退出；否则转向第步 3.2盲目搜索 2.流程图 开始 把S放表入OPEN表 OPEN表为空表 把第一个节点n从OPEN 表移至CLOSED表 把节点n的后继节点 放入OPEN表的末端， 提供返回节点n的指针 失败 成功 是 是 是否有 任何后继节点 为目标节点 ？ 3.2盲目搜索 3.举例：八数码难题 初始棋局 目标棋局 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 8
10、3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1
11、5 2 8 3 7 14 6 5 1 2 3 7 8 4 6 5 1 2 3 8 4 7 5 6 1 2345 678910111213 1415161718192021 222325262728 S0 Sg 3.2盲目搜索 (三).宽度优先搜索的性质 当问题有解时，一定能找到解 当问题为单位耗散值，且问题有解时，一定能找到最 优解 方法与问题无关，具有通用性 效率较低 属于图搜索方法 3.2盲目搜索 二深度优先搜索 (一).深度优先搜索 总是先扩展最新产生的节点 3.2盲目搜索 (二).OPEN表的排列算法 对于许多问题，其状态搜索树的深度可能为无限深 或者可能至少要比某个可接受的解答序列的
12、已知深 度上限还要深，为了避免考虑太长的路径： 1.深度界限：规定的一个节点扩展的最大深度 2.扩展节点：若不等于最大深度，将后裔节点放入 OPEN表的前头。 3.2盲目搜索 3.搜索算法 把起始节点放到OPEN表中(如果该起始节点为一目标 节点，则求得一个解答) 如果OPEN表是一个空表，则失败退出。 把第一个节点(节点n)从OPEN表移到CLOSED表。 如果节点n的深度等于最大深度，则转向第步。 扩展节点n，产生其全部后裔，并把它们放入OPEN表 的前头。如果没有后裔，则转向(2.) 如果后继节点中有任一个为目标节点，则求得一个解 答，成功退出；否则转向第步 3.2盲目搜索 4.流程图
13、开始 把S放表入OPEN表 OPEN表为空表 把OPEN表中第一个 节点n移至CLOSED表 扩展节点n，把后裔 放入OPEN表的前头 失败 成功 是 是 是否有 任何后继节点为 目标节点？ S是否 为目标节点？ 节点n的深度是否等于 深度界限？ 是 成功 是否 3.2盲目搜索 5.举例 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4
14、 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 4 5 6 78 9 ab c d 1 2 3 8 4 7 6 5 目标 3.2盲目搜索 (三).深度优先搜索的性质 一般不能保证找到最优解 当深度限制不合理时，可能找不到解，可以将算法改 为可变深度限制 最坏情况时，搜索空间等同
