《人工智能第三章搜索策略PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《人工智能第三章搜索策略PPT讲稿.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能第三章搜索人工智能第三章搜索策略策略第1页，共102页，编辑于2022年，星期三2022/9/212 简单的搜索策略：简单的搜索策略：g(n)0,f(n)=h(n),g(n)0,f(n)=h(n),局部排序局部排序只排序新扩展出来的子节点，即局部排序只排序新扩展出来的子节点，即局部排序 简单易行，适用于不要求最优解答的问题求解任务。简单易行，适用于不要求最优解答的问题求解任务。1 1）爬山法）爬山法实现启发式搜索的最简单方法。实现启发式搜索的最简单方法。类似于人爬山类似于人爬山只要好爬，总是选取最陡处，以求快速登顶。只要好爬，总是选取最陡处，以求快速登顶。求函数极大值问题求函数极大值问
2、题非数值解法，依赖于启发式知识，试探性地逐步向顶峰逼近非数值解法，依赖于启发式知识，试探性地逐步向顶峰逼近 适用于能适用于能逐步求精逐步求精的问题。的问题。爬山法特点：爬山法特点：只能向上，不准后退，从而简化了搜索算法；体现在：只能向上，不准后退，从而简化了搜索算法；体现在：*从从当当前前状状态态节节点点扩扩展展出出的的子子节节点点（相相当当于于找找到到上上爬爬的的路路径径）中中，将将h(n)h(n)最最小小的的子子节节点点（对对应于到顶峰最近的上爬路径）作为下一次考察和扩展的节点，其余子节点全部丢弃。应于到顶峰最近的上爬路径）作为下一次考察和扩展的节点，其余子节点全部丢弃。不需设置不需设置O
3、PENOPEN和和CLOSECLOSE表，因为没有必要保存任何待扩展节点；表，因为没有必要保存任何待扩展节点；爬爬山山法法对对于于单单一一极极值值问问题题（登登单单一一山山峰峰）十十分分有有效效而而又又简简便便,对对于于具具有有多多极极值值的的问问题题无无能能为为力力会错登上次高峰而失败：不能到达最高峰。会错登上次高峰而失败：不能到达最高峰。回溯策略和爬山法回溯策略和爬山法 第2页，共102页，编辑于2022年，星期三2022/9/213 2 2）回溯策略）回溯策略 可可以以有有效效地地克克服服爬爬山山法法面面临临的的困困难难保保存存了了每每次次扩扩展展出出的的子子节节点点，并并按按h(n)h
4、(n)值值从从小小到到大大排列。排列。相相当当于于爬爬山山的的过过程程中中记记住住了了途途经经的的岔岔路路口口路路径径搜搜索索失失败败时时回回溯溯（后后退退），向向另另一一路路径径方向搜索方向搜索 回溯策略和爬山法回溯策略和爬山法 第3页，共102页，编辑于2022年，星期三2022/9/214 2 2）回溯策略）回溯策略 递归过程递归过程实现回溯策略的有效方式实现回溯策略的有效方式 算法就取名为算法就取名为BACKTRACK(n),BACKTRACK(n),参数参数n n为当前被扩展的节点，为当前被扩展的节点，初次调用时初次调用时n n即为初始状态节点即为初始状态节点s s；分二个部分：分二
5、个部分：*判断当前节点判断当前节点n n的状态，的状态，*作搜索工作作搜索工作扩展节点扩展节点n n，递归递归调用该算法，处理返回结果。调用该算法，处理返回结果。回溯策略和爬山法回溯策略和爬山法 第4页，共102页，编辑于2022年，星期三2022/9/215令令PATHPATH、SNLSNL、n n、n n 为局部变量：为局部变量：PATH-PATH-节点列表，指示解答路径；节点列表，指示解答路径；SNL-SNL-当前节点扩展出的子节点列表；当前节点扩展出的子节点列表；MOVE-FIRST(SNL)-MOVE-FIRST(SNL)-把把SNLSNL表首的节点移出，作为下一次要加以扩展的节点；
6、表首的节点移出，作为下一次要加以扩展的节点；n n、n n-分别指示当前考察和下一次考察的节点。分别指示当前考察和下一次考察的节点。该该递递归归过过程程的的算算法法就就取取名名为为BACKTRACK(n),BACKTRACK(n),参参数数n n为为当当前前被被扩扩展展的的节节点点，算算法法的的初初次次调调用用式式是是BACKTRACK(s),sBACKTRACK(s),s即为初始状态节点。算法的步骤如下：即为初始状态节点。算法的步骤如下：（1 1）若若n n是目标状态节点，则算法的本次调用成功结束，返回空表；是目标状态节点，则算法的本次调用成功结束，返回空表；（2 2）若若n n是失败状态，
7、则算法的本次调用失败结束，返回是失败状态，则算法的本次调用失败结束，返回FAILFAIL；（3 3）扩扩展展节节点点n n，将将生生成成的的子子节节点点置置于于列列表表SNLSNL，并并按按评评价价函函数数f(k)f(k)=h(k)h(k)的的值值从从小小到到大大排序（排序（k k指示子节点）；指示子节点）；（4 4）若若SNLSNL为空，则算法的本次调用失败结束，返回为空，则算法的本次调用失败结束，返回FAILFAIL；（5 5）n=MOVE-FIRST(SNL)n=MOVE-FIRST(SNL)；（6 6）PATH=BACKTRACK(n)PATH=BACKTRACK(n)；（7 7）若若
8、PATH=FAIL,PATH=FAIL,返回到语句（返回到语句（4 4）；）；（8 8）将将nn加到加到PATHPATH表首，算法的本次调用成功结束，返回表首，算法的本次调用成功结束，返回PATHPATH。第5页，共102页，编辑于2022年，星期三2022/9/216 2 2）回溯策略）回溯策略 三种失败状态：三种失败状态：不合法状态（如传教士和野人问题中所述的那样）不合法状态（如传教士和野人问题中所述的那样）旧旧状状态态重重现现（如如八八数数码码游游戏戏中中某某一一棋棋盘盘布布局局的的重重现现，会会导导致致搜搜索索算算法法死死循环），循环），状状态态节节点点深深度度超超过过预预定定限限度度
9、（例例如如八八数数码码游游戏戏中中，指指示示解解答答路路径径不超过不超过6 6步）。步）。回溯条件回溯条件 失败状态，由算法第（失败状态，由算法第（2 2）句指示；）句指示；搜索进入搜索进入“死胡同死胡同”，由该算法的第，由该算法的第(4)(4)句定义。句定义。回溯策略和爬山法回溯策略和爬山法 第6页，共102页，编辑于2022年，星期三2022/9/217 2 2）回溯策略）回溯策略 解答路径的生成解答路径的生成从相应于目标状态节点的空表开始，递归返回从相应于目标状态节点的空表开始，递归返回PATHPATH。影响回溯算法效率的关键因素影响回溯算法效率的关键因素回溯次数回溯次数。回溯回溯搜索到
10、失败状态时的一种弥补行为，搜索到失败状态时的一种弥补行为，准确选择下一步搜索考察的节点准确选择下一步搜索考察的节点大幅度减少甚至避免回溯。大幅度减少甚至避免回溯。设计好的启发式函数设计好的启发式函数h(n)h(n)是至关重要的。是至关重要的。回溯策略和爬山法回溯策略和爬山法 第7页，共102页，编辑于2022年，星期三2022/9/218课堂练习课堂练习:提高题提高题o在应用递归回溯算法解决四皇后的问题中，若按在应用递归回溯算法解决四皇后的问题中，若按行行的的序号从小到大试探性放置各序号从小到大试探性放置各列列的皇后，请画出搜索图，并的皇后，请画出搜索图，并指出分别从算法第指出分别从算法第2步
11、和第步和第4步回溯的次数。步回溯的次数。第8页，共102页，编辑于2022年，星期三2022/9/219 定义定义L，为表示清晰起见，为表示清晰起见,L表中只记载皇后所在列表中只记载皇后所在列,皇后所在皇后所在行可由在行可由在L表中的先后位置指示表中的先后位置指示,例如例如L=(1 3)指示两个皇后位指示两个皇后位置分别为第置分别为第1行第行第1列和第列和第2行第行第3列。列。搜索图搜索图(树树)如右图所示如右图所示:共回溯共回溯22次次,其中算法第其中算法第2步的回溯步的回溯18次次,算法算法第第4次的回溯次的回溯4次。次。第9页，共102页，编辑于2022年，星期三2022/9/21103
12、.4 3.4 问题归约和与或图启发式搜索问题归约和与或图启发式搜索o问题归约问题归约是人求解问题常用的策略：是人求解问题常用的策略：n把把复杂的问题复杂的问题变换为若干需要变换为若干需要同时同时处理的较为处理的较为简单的子问题简单的子问题后再加以分别求解后再加以分别求解n只有子问题全部解决时只有子问题全部解决时，问题才算解决问题才算解决；n问题的解答问题的解答由子问题的解答联合由子问题的解答联合构成。构成。o本节主要内容：本节主要内容：n问题归约的描述（理解）问题归约的描述（理解）n与或图搜索的基本过程（理解）与或图搜索的基本过程（理解）n与或图的启发式搜索（与或图的启发式搜索（掌握掌握）第1
13、0页，共102页，编辑于2022年，星期三2022/9/2111问题归约法问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题第11页，共102页，编辑于2022年，星期三2022/9/2112o问题归约可以用三元组表示：（问题归约可以用三元组表示：（S S0 0，O O，P P），其中），其中nS S0 0是初始问题，即要求解的问题；是初始问题，即要求解的问题；nP P是本原问题集，其中的每一个问题是不用证是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或明的，自然成立的
14、，如公理、已知事实等，或已证明过的问题；已证明过的问题；nO O是操作算子集，它是一组变换规则，通过一是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。个操作算子把一个问题化成若干个子问题。第12页，共102页，编辑于2022年，星期三2022/9/2113o问题归约表示方法就是由初始问题出发，运问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直用操作算子产生子问题的子问题，这样一直进行到进行到产生的问题均为本原问题产生的问题均为本原问题，则问题得，则问题得解。解。第
15、13页，共102页，编辑于2022年，星期三2022/9/2114o看如下符号积分问题：看如下符号积分问题：初始问题初始问题f f(x x)d)dx x变换规则变换规则积分规则积分规则本原问题本原问题可直接求原函数和积分，如可直接求原函数和积分，如sin(sin(x x)d)dx x，coscos (x x)d)dx x等。等。所有问题归约的最终目的是产生本原问题。所有问题归约的最终目的是产生本原问题。第14页，共102页，编辑于2022年，星期三2022/9/2115符号积分问题符号积分问题（sin3x+x4/(x2+1)）dx=sin3xdx+(x4/(x2+1)dx=-(1-cos2x)
16、dcosx+(x2-1+1/(1+x2)dx=(-dcosx+cos2xdcosx)+(x2dx-dx+(1/(1+x2)dx）=-cosx+cos3x/3+x3/3-x+arctgx第15页，共102页，编辑于2022年，星期三2022/9/2116分子结构识别问题分子结构识别问题 如何区分分子式相同但分子结构不同的有机化合物成为重如何区分分子式相同但分子结构不同的有机化合物成为重要而又困难的问题。著名的专家系统要而又困难的问题。著名的专家系统 DENDRAL能用于有效能用于有效地识别分子结构，该系统建立了一套重写规则去把分子式重写为原地识别分子结构，该系统建立了一套重写规则去把分子式重写为
17、原子数较少的分子式和原子间结合关系的混合结构子数较少的分子式和原子间结合关系的混合结构 第16页，共102页，编辑于2022年，星期三2022/9/2117o问题归约的实质：问题归约的实质：从目标从目标(要解决的问题要解决的问题)出发逆向推理，建立出发逆向推理，建立子问题以及子问题的子问题，直至最后把初子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。始问题归约为一个平凡的本原问题集合。第17页，共102页，编辑于2022年，星期三2022/9/2118n应用应用问题归约策略问题归约策略得到的得到的状态空间图状态空间图，也称为，也称为“与或图与或图”n逻辑逻辑“与与”关
18、系关系用用圆弧圆弧将几条将几条节点间关联弧节点间关联弧连接在一起连接在一起o表示问题分解为子问题表示问题分解为子问题；o子问题的状态子问题的状态联合起来构成联合起来构成问题状态问题状态。o子问题全部解决才会导致问题的解决子问题全部解决才会导致问题的解决；n逻辑逻辑“或或”关系关系：o问题可以有问题可以有多种分解方式多种分解方式；o问题（子问题）可能激活问题（子问题）可能激活多个状态变迁操作多个状态变迁操作；o只要一种只要一种分解方式分解方式或或状态变迁操作状态变迁操作能导致最终的解答成功即可；能导致最终的解答成功即可；o导致多个可能的解答。导致多个可能的解答。与或图与或图第18页，共102页，
19、编辑于2022年，星期三2022/9/2119o用用AND-ORAND-OR图图把问题归约为子问题替换集合。把问题归约为子问题替换集合。o如，假设问题如，假设问题A A既可通过问题既可通过问题C C1 1与与C C2 2，也可通过问题，也可通过问题C C3 3、C C4 4和和C C5 5，或，或者由单独求解问题者由单独求解问题C C6 6来解决，如下图所示。图中各节点表示要求来解决，如下图所示。图中各节点表示要求解的问题或子问题。解的问题或子问题。与或图与或图第19页，共102页，编辑于2022年，星期三2022/9/2120梵塔问题梵塔问题n问题描述：问题描述：n初始状态下三个盘按初始状态
20、下三个盘按A、B、C顺序堆放在顺序堆放在1号柱子上；号柱子上；n目标状态下三个盘以同样次序顺序堆放在目标状态下三个盘以同样次序顺序堆放在3号柱子上；号柱子上；n盘子的盘子的搬移规则搬移规则：o每次只能搬一个盘子；每次只能搬一个盘子；o较大盘不能压放在较小盘之上；较大盘不能压放在较小盘之上；CAB初始状态初始状态(1 1 1)目标目标状态状态(3 3 3)CAB132132与或图与或图第20页，共102页，编辑于2022年，星期三2022/9/2121梵塔问题梵塔问题状态空间图状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3
21、)(2,2,1)132CAB(2,2,3)123ABC目标目标状态状态(3 3 3)CAB132第21页，共102页，编辑于2022年，星期三2022/9/2122梵塔问题梵塔问题状态空间图状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)第22页，共102页，编辑于2022年，星期三2022/9/2123梵塔问题梵塔问题(1,1,1)(3,3,3)(1,1
22、,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(3,1,1)(3,2,1)(1,2,3)(1,3,3)(2,2,3)(1,2,3)(1,3,3)(3,3,3)123456789子问题间有子问题间有交互作用交互作用，问题分解问题分解注意注意正确的顺序正确的顺序第23页，共102页，编辑于2022年，星期三2022/9/2124与或图搜索与或图搜索o与或图与或图视为对视为对一般图一般图(或图或图)的扩展；的扩展；n引入引入K-连接连接o父子节点父子节点间可以存在间可以存在“与与”关系关系n结果结果解图解图。o解答
23、路径往往不复存在，代之以广义的解路径解答路径往往不复存在，代之以广义的解路径解图解图。问题归约求解问题的过程问题归约求解问题的过程表示为与或图搜索表示为与或图搜索第24页，共102页，编辑于2022年，星期三2022/9/2125与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n1、K-连接连接o从从父节点父节点到到K个个子节点子节点的连接，的连接，子节点子节点间间有有“与与”关系关系；o以以圆弧圆弧指示指示这些子节点这些子节点间间的的“与与”关系关系；o一个父节点可以一个父节点可以有多个有多个K-连接连接nK-连接间连接间”或或”关系关系o当当所有的所有的K都等于都等于1时
24、，时，与或图与或图蜕化为蜕化为一般图（或图）一般图（或图）。3个子节点个子节点2个子节点个子节点第25页，共102页，编辑于2022年，星期三2022/9/2126与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n2、根、叶、根、叶、终节点终节点o根节点根节点无父节点的节点无父节点的节点n用于指示用于指示问题初始状态（和一般图一样）问题初始状态（和一般图一样）o叶节点叶节点无子节点的节点无子节点的节点o终节点终节点能用于能用于联合表示目标状态的节点联合表示目标状态的节点n终节点必定是叶节点终节点必定是叶节点，反之不然；，反之不然；n目标状态目标状态终结点的集合终结点的集合。第
25、26页，共102页，编辑于2022年，星期三2022/9/2127一些关于与或图的术语一些关于与或图的术语HMBCDEFGAN父节点父节点与节与节点点弧线弧线或节或节点点子节子节点点终节点终节点第27页，共102页，编辑于2022年，星期三2022/9/2128与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图o解图解图中，中，节点节点或或节点组间节点组间不存在不存在“或或”关系；关系；o所有叶节点都是终节点所有叶节点都是终节点第28页，共102页，编辑于2022年，星期三2022/9/2129与或图搜索与或图
26、搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成n自自根节点根节点开始选开始选K-连连接接;n从该从该K-连接连接指向的指向的每每个子节点个子节点出发，再选出发，再选一一K-连接连接;n如此反复进行，直到如此反复进行，直到所有所有K-连接连接都指向都指向终终节点节点为止为止.第29页，共102页，编辑于2022年，星期三2022/9/2130第30页，共102页，编辑于2022年，星期三2022/9/2131与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图n解图解图中，中，节点节点
27、或或节点组间节点组间不存在不存在“或或”关系；关系；n所有所有叶节点叶节点都是都是终节点终节点o与或图与或图中存在中存在“或或”关系，关系，搜索到多个解图搜索到多个解图；第31页，共102页，编辑于2022年，星期三2022/9/2132与或图搜索与或图搜索o2)解图解图、解图代价、能解节点和不能解节点的定义、解图代价、能解节点和不能解节点的定义n(1)解图解图与或图与或图（记为（记为G）任一节点（记为）任一节点（记为n）到）到终节点集终节点集合合的的解图解图（记为（记为G）是）是G的的子图子图。o(1)若若n是是终节点终节点，则，则G就就由单一节点由单一节点n构成构成；o(2)若若n有一有一
28、K-连接连接指向子节点指向子节点n1，n2，nk,且每且每个子节点都有到终节点集合的个子节点都有到终节点集合的解图解图，则，则G由该由该k-连连接接和所有这些和所有这些相应于子节点的解图相应于子节点的解图构成构成;o(3)否则不存在否则不存在n到到终节点集合终节点集合的的解图解图。第32页，共102页，编辑于2022年，星期三2022/9/2133与或图搜索与或图搜索o2)解图、解图、解图代价解图代价、能解节点和不能解节点的定义、能解节点和不能解节点的定义n(2)解图代价解图代价 以以C(n)指示节点指示节点n到到终节点集合终节点集合解图解图的代价，的代价，并令并令K-连接的代价就为连接的代价
29、就为K,则则 o(1)若若n是终节点，则是终节点，则C(n)=0；o(2)若若n有一有一K-连接连接指向子节点指向子节点n1，n2，nk,且这且这些子节点每个都有到终节点集合的解图些子节点每个都有到终节点集合的解图,则则C(n)=K+C(n1)+C(n2)+C(nk)35第33页，共102页，编辑于2022年，星期三2022/9/2134与或图搜索与或图搜索o2)解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节点的定义的定义n(3)能解节点能解节点 o(1)终节点是能解节点终节点是能解节点；o(2)若节点若节点n有有一一K-连接连接指向子节点指向子节点n1，n2，nk,且
30、这些且这些子节点都是能解节点子节点都是能解节点，则，则n是能解节点；是能解节点；能解节点能解节点能解节点能解节点能解节点能解节点能解节点能解节点第34页，共102页，编辑于2022年，星期三2022/9/2135与或图搜索与或图搜索o2)解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节点的定义的定义n(4)不能解节点不能解节点o(1)非终节点的叶节点是不能解节点非终节点的叶节点是不能解节点；o(2)若节点若节点n的的每一个每一个K-连接连接都都至少至少指向一个不能解指向一个不能解节点节点，则，则n是不能解节点。是不能解节点。能解节点能解节点不能解节点不能解节点能解节点能解
31、节点不能解节点不能解节点不能解节点不能解节点第35页，共102页，编辑于2022年，星期三2022/9/2136与或图的启发式搜索与或图的启发式搜索o与或图中搜索的是与或图中搜索的是解图解图，不是解答路径；，不是解答路径；n评价函数评价函数f(n)=h(n)nh(n)是对是对n到到终节点集合终节点集合解图最小解图代价解图最小解图代价的估计；的估计；o与或图中存在与或图中存在“或或”关系关系，会有会有多个候选的局部解图多个候选的局部解图；n选择选择局部解图中可能代价最小局部解图中可能代价最小的用于下一步搜索。的用于下一步搜索。o1)（局部）解图代价（局部）解图代价f(n0)nn0初始状态节点初始
32、状态节点n递归地计算出递归地计算出f(n0),比直接用比直接用h(n0)估算估算更为准确。更为准确。n父节点父节点n的的K-连接连接指向的子节点：指向的子节点：n1，n2，nknf(n)=K+h(n1)+h(n2)+h(nk)，代替，代替h(n)第36页，共102页，编辑于2022年，星期三2022/9/2137与或图的启发式搜索与或图的启发式搜索o2)AO*算法算法o符号说明：符号说明：nG-搜索图；搜索图；nG-被选中的被选中的待扩展局部解图待扩展局部解图；nLGS-待扩展待扩展局部解图集局部解图集；nn0-根节点根节点，即初始状态节点；，即初始状态节点；nn-被选中的被选中的待扩展节点待
33、扩展节点；nfi(n0)-第第i个个待扩展局部解图待扩展局部解图的的可能代价可能代价。第37页，共102页，编辑于2022年，星期三2022/9/2138与或图的启发式搜索与或图的启发式搜索o2)AO*算法算法o算法划分二个阶段：算法划分二个阶段：n1、初始化、初始化 o建立只包含建立只包含初始状态节点初始状态节点n0的搜索图的搜索图G:=n0；o待扩展局部解图集待扩展局部解图集LGS:=；n2、搜索循环、搜索循环o选择选择和和扩展扩展LGS中的中的局部解图局部解图；o精化精化新局部解图新局部解图代价的估计代价的估计；o传递传递节点的节点的能解性能解性。第38页，共102页，编辑于2022年，
34、星期三2022/9/2139与或图的启发式搜索与或图的启发式搜索o2、搜索循环、搜索循环n选择选择和和扩展扩展LGS中的中的局部解图局部解图；o选择选择LGS中中fi(n0)最小的待扩展解图最小的待扩展解图G；o随机随机选择选择G中一个中一个非终节点非终节点的的叶节点叶节点作为作为n；o扩展扩展nn建立建立K-连接连接，子节点，子节点ni并加入并加入G；n计算计算子节点子节点ni的的f(ni)=h(ni)o若若n存在存在j个个K-连接连接nLGS中删除中删除Gn将将j个个新的局部解图新的局部解图加入加入LGS;第39页，共102页，编辑于2022年，星期三2022/9/2140与或图的启发式搜
35、索与或图的启发式搜索o2、搜索循环、搜索循环n选择选择和和扩展扩展LGS中的中的局部解图局部解图；n精化精化新新局部解图局部解图代价的估计代价的估计o用公式用公式f(f(n n)=K+h(n1)+h(n2)+h(nk)=K+h(n1)+h(n2)+h(nk)取取代原先的代原先的f(n);f(n);o递归地递归地作用到作用到初始节点初始节点n n0 0；n传递传递新局部解图中新局部解图中节点的节点的能解性能解性o标记标记作为作为终节点终节点的子节点为的子节点为能解节点能解节点；o递归地递归地传递节点的传递节点的能解性能解性到到初始节点初始节点n n0 0。f(n)=h(n)第40页，共102页，
36、编辑于2022年，星期三2022/9/2141第41页，共102页，编辑于2022年，星期三2022/9/2142与或图的启发式搜索与或图的启发式搜索o2)AO*算法算法oAO*算法应用例算法应用例o搜索过程中，启发式函数搜索过程中，启发式函数h(ni)的的 估算如下：估算如下：oh(n0)=3oh(n1)=2oh(n2)=1oh(n3)=1oh(n4)=4oh(n5)=2oh(n6)=2oh(n7)=1oh(n8)=1oh(n13)=30123546789101112131415161718 1920第42页，共102页，编辑于2022年，星期三2022/9/2143初始化初始化候选的待扩展
37、局部解图集候选的待扩展局部解图集LGS:030第43页，共102页，编辑于2022年，星期三2022/9/2144012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:3211420第44页，共102页，编辑于2022年，星期三2022/9/2145012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:32114203120123543211420第45页，共102页，编辑于2022年，星期三2022/9/2146012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:10211420512f(n)=K+h(n1)+h(n2)+h(nk
38、)取代原先的取代原先的f(n);f1(n0)=2+h(n1)+h(n2)=5f2(n0)=3+h(n3)+h(n4)+h(n5)=10第46页，共102页，编辑于2022年，星期三2022/9/2147012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:10211420567821112第47页，共102页，编辑于2022年，星期三2022/9/2148012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:102114205781101221562342第48页，共102页，编辑于2022年，星期三2022/9/2149012354循环循环2候选的待扩
39、展局部解图集候选的待扩展局部解图集LGS:1041142077811012316623422525第49页，共102页，编辑于2022年，星期三2022/9/2150012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:104114207781101231662342131430循环循环3第50页，共102页，编辑于2022年，星期三2022/9/2151012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:104114207781101261965342131430循环循环3362第51页，共102页，编辑于2022年，星期三2022/9/2152012354循环循环4候
40、选的待扩展局部解图集候选的待扩展局部解图集LGS:104114207781101261965342131430140第52页，共102页，编辑于2022年，星期三2022/9/2153012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:104114207781101261965342131430140150第53页，共102页，编辑于2022年，星期三2022/9/2154012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:105114208781201261965342131430140150471第54页，共102页，编辑于2022年，星期三20
41、22/9/2155012354循环循环6候选的待扩展局部解图集候选的待扩展局部解图集LGS:10511420878120126196534213143014015090第55页，共102页，编辑于2022年，星期三2022/9/2156012354搜索成功！搜索成功！候选的待扩展局部解图集候选的待扩展局部解图集LGS:10511420878120126196534213143014015090第56页，共102页，编辑于2022年，星期三2022/9/2157与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o1、从局部解图、从局部解图G中选择加以扩展的节点中选择
42、加以扩展的节点nn与或图搜索的是与或图搜索的是解图解图而而非解路径非解路径；n选择选择f(n)=h(n)的值最小的值最小的节点的节点n加以扩展并不加以扩展并不一定会加速搜索过程；一定会加速搜索过程；n应选择导致解图代价发生较大变化应选择导致解图代价发生较大变化的节点的节点n优先优先加以扩展；加以扩展；o使搜索的注意力快速地聚焦到实际代价较小的候选使搜索的注意力快速地聚焦到实际代价较小的候选解图上；解图上；n简单情况下，可简单情况下，可随机选择随机选择加以扩展的节点。加以扩展的节点。第57页，共102页，编辑于2022年，星期三2022/9/2158与或图的启发式搜索与或图的启发式搜索o4）算法
43、应用的若干问题）算法应用的若干问题o2、算法算法AO*与与A*的比较的比较n解图解图解答路径解答路径，n估计估计代价最小的局部解图代价最小的局部解图加以优先扩展加以优先扩展OPEN表中表中f(n)最小的节点最小的节点；n只考虑只考虑评价函数评价函数f(n)=h(n)同时计算分量同时计算分量g(n)和和h(n)，n应用应用LGS存放存放待扩展局部解图待扩展局部解图，并依据，并依据fi(n0)值值排序排序应用应用OPEN表和表和CLOSE表分别存放表分别存放待待扩展节点扩展节点和和已扩展节点已扩展节点，并依据，并依据f(n)值值排序排序OPEN表。表。第58页，共102页，编辑于2022年，星期三
44、2022/9/2159与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o3、解图代价的重复计算、解图代价的重复计算n某些某些子节点子节点可能会有可能会有多个父节点多个父节点；n这种这种子节点子节点到终节点集合的到终节点集合的解图代价解图代价在计算自在计算自根节点根节点n0出发的解图时被出发的解图时被重复累计重复累计。17817814 1512517814221624118第59页，共102页，编辑于2022年，星期三2022/9/2160博弈博弈 n博弈提供了一个可构造的任务领域，在这个领博弈提供了一个可构造的任务领域，在这个领域中，具有明确的域中，具有明确的胜
45、利胜利和和失败失败；n博弈问题对人工智能研究提出了严峻的挑战。博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和例如，如何表示博弈问题的状态、博弈过程和博弈知识等。博弈知识等。o这里讲的博弈是这里讲的博弈是二人博弈二人博弈，二人零和二人零和、全信息全信息、非偶非偶然博弈然博弈，博弈双方的利益是，博弈双方的利益是完全对立完全对立的。的。第60页，共102页，编辑于2022年，星期三2022/9/2161n所谓所谓“二人零和二人零和”，是指在博弈中只有，是指在博弈中只有“敌、我敌、我”二方。且双方的二方。且双方的利益完全对立，利益完全对立，其赢得函数之和为零其赢得函数
46、之和为零，即，即 1+2=0 式中，式中，1为我方赢得为我方赢得(利益利益)；2为敌方赢得为敌方赢得(利益利益)。即：博弈的双方有三种结局：即：博弈的双方有三种结局：(1)我胜：我胜：10；敌负：；敌负：2=-10。(2)我负：我负：1=-20。(3)平局：平局：1=0，2=0。博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和博弈知识等。弈问题的状态、博弈过程和博弈知识等。第61页，共102页，编辑于2022年，星期三2022/9/2162n所谓所谓“全信息全信息”，是指博弈双方都了解当前的，是指博弈双方都
47、了解当前的格局及过去的历史。格局及过去的历史。n所谓所谓“非偶然非偶然，是指博弈双方都可，是指博弈双方都可根据得失大根据得失大小进行分析小进行分析，选取，选取我方赢得最大，敌方赢得最我方赢得最大，敌方赢得最小的对策小的对策，而不是偶然的随机对策。，而不是偶然的随机对策。第62页，共102页，编辑于2022年，星期三2022/9/2163（1 1）对垒的双方）对垒的双方MAXMAX和和MINMIN轮流采取行动，博弈的结果轮流采取行动，博弈的结果只能有只能有3 3种情况：种情况：MAXMAX胜、胜、MINMIN败；败；MAXMAX败，败，MINMIN胜；和局。胜；和局。（2 2）在对垒过程中，任何
48、一方都了解当前的格）在对垒过程中，任何一方都了解当前的格局和过去的历史。局和过去的历史。（3 3）任何一方在采取行动前都要根据当前的实际）任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选择对自己最为有利情况，进行得失分析，选择对自己最为有利而对对方最不利的对策，在不存在而对对方最不利的对策，在不存在“碰运气碰运气”的偶然因素，即双方都很理智地决定自己的的偶然因素，即双方都很理智地决定自己的行动。行动。o这类博弈如一字棋、象棋、围棋等。博弈的特点博弈的特点博弈的特点博弈的特点 第63页，共102页，编辑于2022年，星期三2022/9/2164o另外一种博弈是机遇性博弈，是指不可预测
49、另外一种博弈是机遇性博弈，是指不可预测性的博弈，如掷硬币游戏等。性的博弈，如掷硬币游戏等。第64页，共102页，编辑于2022年，星期三2022/9/2165例：例：o假设有七枚钱币，任一选手只能将已分好的假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆一堆钱币分成两堆个数不等个数不等的钱币，两位选的钱币，两位选手轮流进行，直到每一堆都只有一个或两个手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个选手遇到不能再钱币，不能再分为止，哪个选手遇到不能再分的情况，则为输。分的情况，则为输。第65页，共102页，编辑于2022年，星期三2022/9/2166o用数字序列加上一个说明
50、表示一个状态，其中数字表示不同用数字序列加上一个说明表示一个状态，其中数字表示不同堆中钱币的个数，说明表示下一步由谁来分，堆中钱币的个数，说明表示下一步由谁来分，o如如（7 7，MINMIN）表示只有一个由七枚钱币组成的堆，由表示只有一个由七枚钱币组成的堆，由MINMIN走，走，MINMIN有有3 3种可供选择的分法，即种可供选择的分法，即n（6 6，1 1，MAXMAX），（），（5 5，2 2，MAXMAX），（），（4 4，3 3，MAXMAX），），o其中其中MAXMAX表示另一选手，不论哪一种方法，表示另一选手，不论哪一种方法，MAXMAX在它的基在它的基础上再作符合要求的划分。础上