南邮自动化人工智能3--确定性推理.ppt

3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 消解原理 3.5 规则演绎系统 1 第三章 搜索推理技术 3.6 产生式系统 3.7非单调推理 3.8小结 问题：知识表示有那些方法？知识表示的目的是 什么？构建智能系统的关键是什么？ 3.1 图搜索策略 思考：状态空间法的基本特点？基本推理方法？其 求解结果是什么？简单回顾实例：猴子与香蕉。 2 用一个四元表列（W，x，Y，z）表示这个问题状态 W 猴子的水平位置 x 当猴子在箱子顶上时取 x = 1；否则取 x = 0 Y 箱子的水平位置 z 当猴子摘到香蕉时取 z=1；否则取 z=0 算符： Goto（U）， （W，0，Y，z） goto（U） （U，0，Y，z） Pushbox（V）， （W，0，W，z） pushbox（V） （V，0，V，z） Climbbox， （W，0，W，z） climbbox （W，1，W，z） Grasp， （c，1，c，0） grasp （c，1，c，1） 3 3.1 图搜索策略 4 (b，1，b，0) （U，0，b，0） （V，0，V，0） （c，1，c，0）（U，0，V，0） （c，1，c，1） （a，0，b，0） U=b，climbbox 猴子和香蕉问题的状态空间图 提问：人工搜索求解的解答？ 目标状态 goto（U） goto（U） goto（U） U=b, pushbox（V） pushbox（V） goto（U） Vc，climbbox V=c，climbbox 3.1 图搜索策略 5 猴子和香蕉问题自动演示 ： 猴子 香蕉 箱子 猴子 香蕉 箱子 Ha!Ha! 3.1 图搜索策略 思考：计算机的搜索策略？ 图搜索控制策略:一种在图中寻找路径的方法。 图中每个节点对应一个状态; 每条连线对应一个操作符。 图搜索过程（GraphSearch） 6 3.1 图搜索策略 7 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 n为目标节点吗？ 把n的后继节点放入OPEN表的 末端，提供返回节点n的指针 修改指针方向 重排OPEN表 失败 成功 图3.1 图搜索过程框图 是 是 否 否 3.1 图搜索策略 (1) (3) (4) (5) (6) (7) (7) (8) (9) OPEN CLOSED (1)(2) 宽度优先 图搜索的一般过程如下： 1）建立一个只含有起始节点S的搜索图G，把S放到 一个叫做OPEN 的未扩展节点表中。 2）建立一个叫做CLOSED的已扩展节点表，其初始为 空表. 3）LOOP：若OPEN表是空表，则失败退出。 4）选择OPEN表上的第一个节点，把它从OPEN表移 出并放进CLOSED表中。称此节点为节点n 5）若n为一目标节点，则有解并成功退出，此解是追 踪图G中沿着指针从n到S这条路径而得到的(指针将在 第7步中设置)。 8 3.1 图搜索策略 6）扩展节点n，同时生成不是n的祖先的那些后继节点的 集合M。把M的这些成员作为n的后继节点添入图G中。 7）对那些未曾在G中出现过的M成员设置一个通向n的指 针。把M的这些成员加进OPEN表。对已经在OPEN或 CLOSED表上的每一个M成员，确定是否需更改通到n的指 针方向。对已在CLOSED表上的每个M成员，确定是否需 要更改图G中通向它的每个后裔节点的指针方向。 8）按某一任意方式或按某个探试值，重排OPEN表。 9）GO LOOP。 9 3.1 图搜索策略 图搜索策略 图搜索的实质是从问题空间中找出一张包含目标节点的子 图。 图搜索的结果：1，一个完整的搜索图G。2一个解路径，用 指针表示的解路径。 Procedure Graph Search 1 G=G0(G0=s),open=(s) /s:初始状态 2 closed=() 3Loop:if open=() then exit(fall) 4 nfirst(open) remove(n,open), add(n,closed) 5 if goal(n) then exit(success) 6mj expand(n), /mj不含n的先辈节点 7 openadd(open，mj) / mj不在open，closed中 *10 标记mj每个到n节点指针 确定是否需要修改已在open，closed中的每个节点到n的 指针 确定是否需要修改已在closed中的每个节点的后继节点原 来的指针。 8 按照某种方式排列open表中的节点，go loop *11 *12 *13 思考： （1）结果路径的形成中，为什么其节点顺序是明确的？ （2）OPEN表中的节点具有什么特点？ （3）CLOSED表中的节点具有什么特点？ （4）对OPEN表节点的排序有何意义？ 提出：盲目搜索与启发式搜索。 14 3.1 图搜索策略 3.2 盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较 简单的问题。 特点：不需重排OPEN表； 种类：宽度优先、深度优先、等代价搜索等。 15 3.2.1 宽度优先搜索（Breadth-first ） v 定义： 以接近起始节点的程度逐层扩展节点的搜索方法。 v 特点： 一种高代价搜索，但若有解存在，则必能找到它。 16 S LO M F PQ N F FF 宽度优先搜索示意图 1）把起始节点放到OPEN表中(如果该起始节点为一目标节点， 则求得一个解答)。 2）如果OPEN是个空表，则没有解，失败退出；否则继续。 3）把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的 扩展节点表中。 4）扩展节点n。如果没有后继节点，则转向上述第(2)步。 5）把n的所有后继节点放到OPEN表的末端，并提供从这些后 继节点回到n的指针。 6）如果n的任一个后继节点是个目标节点，则找到一个解答， 成功退出；否则转向第(2)步。 17 宽度优先搜索算法： 3.2 盲目搜索 18 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 是否有后继节点 为目标节点？ 扩展n，把n的后继节点放入OPEN 表的末端，提供返回节点n的指针 失败 成功 图3.2 宽度优先算法框图 是 否 是 否 3.2 盲目搜索 思考：与原始算法比较异同，宽度优先的体现？ *19 宽度优先算法 Procedrue breadth-First-Search 1 G=G0(G0=s),open=(s),closed=() /s:初始状态 2 Loop: if open=() then exit(fall) 3 nfirst(open) 4 if goal(n) then exit(success) 5remove(n,open), add(n,closed) 6mj expand(n), /mj不含n的先辈节点 7 openadd(open，mj) / mj不在open，closed 中 *20 标记每个到n节点指针，按照节点深度递 增顺序排列open中的节点 8 go loop 理论上可以利用宽度优先搜索能够找到解 ，如果问题有解的话。 讨论：宽度优先算法和深度优先算法可能 出现组合爆炸。都没有利用任何启发式信 息，所以称为无信息搜索策略。 *21 ： 宽度优先例题： 由一张桌子T、三个积木A、B、C组成一个 积木世界，初始状态是A在B上，B在桌子上 ，C在桌子上；目标状态是：A、B、C依次 从上到下排列在桌子上。如图 *22 解：1）状态描述（P1，P2，P3）表示按A 、B、C顺序依次分别在P1,P2,P3上其中Pi是 积木或者桌子。初始状态时（B、T、T）,目 标状态 可以表示（B、C、T） 2）定义操作:move(x,y)表示将积木x移到Y上 ； 约束条件:a X顶部必须是空的 b 如果Y是积 木，Y的顶部必须是空的 c 同一种状态出现不得多于一次。 *23 1）解题过程 2）open表和closed表 3）节点样子画出整个图G 和解路径 4）程序何时结束 5）改用深度优先如何？ 例子 八数码难题（8-puzzle problem） 24 1 238 4 567 123 84 567 （目标状态） （初始状态） 规定：将牌移入空格的顺序为：从空格左边 开始顺时针旋转。不许斜向移动，也不返回 先辈节点。从图可见，要扩展26个节点，共 生成46个节点之后才求得解（目标节点）。 3.2 盲目搜索 25 3.2 盲目搜索 3.2.2 深度优先搜索(Dephth-first) 26 v 定义 ： 首先扩展最新产生的(即最深的)节点。 v 特点 ： 防止搜索过程沿着无益的路径扩展下去，往往给 出一个节点扩展的最大深度深度界限。 与宽度优先搜索算法最根本的不同在于：将扩展 的后继节点放在OPEN表的前端。 3.2 盲目搜索 深度优先搜索示意图 27 S LO M F PQ N F FF 3.2 盲目搜索 28 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 是否有后继节点 为目标节点？ 扩展n，把n的后继节点放入OPEN 表的前端，提供返回节点n的指针 失败 成功 图3.6 深度优先算法框图 是 否 是 否 3.2 盲目搜索 节点n的深度等于最大深度？ 否 *29 深度优先算法 Procedrue depth-First-Search 1 G=G0(G0=s),open=(s),closed=() /s:初始状态 2 Loop:if open=() then exit(fall) 3 nfirst(open) 4 if goal(n) then exit(success) 5remove(n,open), add(n,closed) 6mj expand(n), /mj不含n的先辈节点 7 openadd(open，mj) / mj不在open，closed中 标记mj每个到n节点指针，按照节点深度递减顺 序排列open中的节点 8 go loop 示范：有界深度(4)优先的八数码问题深度优先 搜索树？ 30 3.2 盲目搜索 1 238 4 567 123 84 567 （目标状态） （初始状态） 31 3.2 盲目搜索 *32 讨论1：如果问题有解，用深度优先搜索算 法，是否能够找到解？ 不一定. 解空间是否有限？ 讨论2：本算法的改进之处是open中节点按 照深度优先排列，但是没有对深度加以控 制，可能造成搜索代价太大 3.2.3 等代价搜索 33 v 定义 是宽度优先搜索的一种推广，不是沿着等长度路 径断层进行扩展，而是沿着等代价路径断层进行扩展 。 搜索树中每条连接弧线上的有关代价,表示时间、 距离等花费。 v 算法 在等价搜索算法中，把从节点i到其后续节点j的连 接弧线记为c(I,j),把从起始节点S到任一节点I的路径代 价记为g(i)。在搜索树上，假设g(i)也是从起始节点S到 节点的最少代价路径上的代价。 3.2 盲目搜索 思考：如何动态计算g(i)? 34 开始 把S放入OPEN表 OPEN表为空表？ 把具有最小g(i)值的节点i从OPEN表 移至CLOSED表 是否有后继节点 为目标节点？ 失败 成功 图3.8 等代价搜索算法框图 是 否 是 否 令g(s)=0 S是否目标节点？ 是 成功 否 3.2 盲目搜索 扩展i，计算其后继节点j的g(j) ，并把后继节点放入OPEN表 课后例题讲解 1. 设有如图所示的一棵与/或树，请用与/或 树的宽度优先搜索及与/或树的深度优先搜 索求出解树。 35 解：（1）与/或树的宽度优先搜索 I.先扩展节点A，得到节点B和C； II.再扩展节点B, 得节点t1、t2，因为t1、t2为可解节点，故 节点B可解，从而可节点A可解。 III. 所以求得解树为： 36 （2）与/或树的深度优先搜索 I.先扩展节点A, 得到节点B和C； II.再扩展节点C, 得节点D和t5； III. t5为可解节点，再扩展节D，得节点t3、t4； IV. t3、t4为可解节点，故节点D可解，因为节点D和t5可解 故节点C可解，从而可节点A可解。 V.所以求得解树为： 37 2.下图是5个城市的交通图，城市之间的连 线旁边的数字是城市之间路程的费用。要 求从A城出发，经过 其它各城市一次且仅 一次，最后回到A城，请找出一条最优线 路。 等代价搜索 38 3.3 启发式搜索 启发式信息：用来加速搜索过程的问题领域信息，一般与有关问题具 体领域背景有关，不一定具有通用性。 启发式搜索：利用启发式信息的搜索方法 特点：重排OPEN表，选择最有希望的节点加以扩展 种类：有序搜索、A*算法等 39 v基本步骤：初始化，判断OPEN表是否为空，选择节点n，判断n是否 目标节点，扩展节点n，重排OPEN表、调整指针，循环。 v各自特点：重排OPEN表的依据不同。 v盲目搜索可能带来组合爆炸。 思考： （1）图搜索方法的基本步骤？ （2）宽度优先、深度优先、等代价方法的特点 ？ （3）盲目搜索的缺点？ 有序搜索（Ordered Search） 总是选择“最有希望”的节点作为下一被扩展节点 估价函数（Evaluation Function） 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法 ，以便确定哪个节点最有可能在通向目标的最佳路径上 。 f(n)表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN表；有序搜索 也称为最佳优先搜索； 估价函数举例： （1）棋局的得分； （2）距离目标状态的距离量度； （3）TSP问题中的路径； 思考：f 函数的计算，重排序的方法？ 40 3.3.1 启发式搜索策略和估价函数 3.3 启发式搜索 41 3.3.2 有序搜索（Ordered Search； Bestfirst Search） v实质：选择OPEN表上具有最小 f 值的节点作为下 一个要扩展的节点。 3.3 启发式搜索 vNilsson（尼尔逊）方法：一个节点的“希望” 越大，则其 f 值越小。被选择的节点是估价函数最 小的节点。 思考：如果把宽度优先、深度优先、等代价搜索方法作 为有序搜索的特例，那么它们的 f 函数如何计算 ？ 举例示范。 42 开始 把S放入OPEN表， 计算估价函数 f (s) OPEN表为空表？ 选取OPEN表中f值最小的节点i放入CLOSED表 i为目标节点吗？ 扩展i，得后继节点j，计算f(j)，提供返回 节点i的指针，利用f(j)对OPEN表重新排 序，调整亲子关系及指针 失败 成功 图3.9 有序搜索算法框图 是 否 是 否 3.3 启发式搜索 v算法 八数码难题 43 （2）如下的八数码难题（8-puzzle problem） 123 84 567 （目标状态） 1 238 4 5 6 7 （初始状态） （3）八数码难题的有序搜索树见下图： 3.3 启发式搜索 （1）估价函数设置： f(n) = d(n) + W(n) d(n): 节点n的深度； W(n):错放的棋子数 44 3.3 启发式搜索 f 函数的重要性 有序搜索的有效性直接取决于 f ,是提高搜索效率的关键； 如果 f 不准确，可能失去最佳解，也可能失去全部解； f 一般选择策略 搜索时间与空间的折衷； 保证有解或有最佳解； f 选择的三种典型情况： （1）最优解答：状态空间中有多条解答路径，求解最优解答，如 A*算法； （2）搜索代价与解答质量的综合：问题类似于（1），但搜索过程 可能超出时间与空间的界限。在适当的搜索实验中找到满意解答， 并限制满意解答与最优解答的差异程度；如：TSP问题； （3）最小搜索代价：不考虑解答的最优化（只有一个解答或多个 解答间无差异），尽量使搜索代价最小；如：定理证明。 思考： （1） f 不能识别某些节点的真实“希望”值会怎么样？ （2） f 过多估计了全部节点又会怎么样？ 45 3.3 启发式搜索 3.3.3 A*算法 思考：经过节点n的最佳路径，怎么表示？怎么求 解最优解答路径。 估价函数f* ：对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始通 过节点n的一条最佳路径的代价。其中g*(n)表示从起始节点S 到n的最佳路径，h*(n)表示从n到某目标节点的最佳路径。 估价函数f ：f(n)=g(n)+h(n)； 其中g是g*的估计 ，h是h*的 估计； g 的一个选择就是搜索树中从 S 到 n 的这段路径的代价；显然有 g(n) g*(n)； h 的依赖于