人工智能及其应用chapter3-071101课件.ppt

1、3.1 搜索系统的组成 搜索系统由以下三大成分构成搜索系统由以下三大成分构成：知识库：描述当前任务的范围以及要求解知识库：描述当前任务的范围以及要求解问题的目标。问题的目标。规则规则 :用于对数据库的加工处理。用于对数据库的加工处理。控制性知识：控制性知识：决定下一步应如何做？选择决定下一步应如何做？选择什么操作？在何处使用此控制？什么操作？在何处使用此控制？人工智能及其应用1 3.2 问题表示及求解方法 问题表达及其变换问题的直接求解法状态空间图搜索算法 人工智能及其应用2问题表达及其变换 n同构同态变换同构同态变换n问题分解法问题分解法v与图（树）描述问题分解。与图（树）描述问题分解。v或

2、图（树）描述同构同态变换或图（树）描述同构同态变换。原始问题原始问题同态解答同态解答同态问题同态问题原始解答原始解答h h易解易解难解难解h h-1 1人工智能及其应用3问题的直接求解法 n状态空间求解法状态空间求解法v用状态描述与问题相关的事实和事实间的关系。用状态描述与问题相关的事实和事实间的关系。v状态常表示为矢量。状态常表示为矢量。v问题的状态空间可记为三元组问题的状态空间可记为三元组(S，F，G)。问题演绎法问题演绎法 基本思想：分解原问题成若干个子问题。基本思想：分解原问题成若干个子问题。n博弈问题求解法博弈问题求解法 属于对策性课题，表示若干个体开展竞争的过程。属于对策性课题，表

3、示若干个体开展竞争的过程。人工智能及其应用4状态空间图搜索算法n搜索法求解问题的基本思想：搜索法求解问题的基本思想：v将初始状态当作当前状态。将初始状态当作当前状态。v选择适当的算符作用于当前状态得到后继状态。选择适当的算符作用于当前状态得到后继状态。v检查这组后继状态中是否有目标状态。检查这组后继状态中是否有目标状态。n已扩展节点、未扩展节点的数据结构已扩展节点、未扩展节点的数据结构状状态态结结点点父父结结点点O OP PE EN N表表结结构构编编号号父父结结点点状状态态结结点点C CL LO OS SE ED D表表结结构构人工智能及其应用5状态空间图搜索算法n状态空间搜索状态空间搜索算

4、法流程：算法流程：开 始初始化：S放入OPEN表，CLOES表置空,n=1OPEN表中的第一个结点n移至CLOSE表若n的后继未曾在搜索图G中出现，则将其放入OPEN表的末端，并提供返回结点n的指针,置n=n+1根据后继结点在搜索图G中的出现情况修改指针方向依某种准则重新排序OPEN表失败成功NYNOPEN为空表NULL？n=目标结点D吗?Y人工智能及其应用6 3.3 3.3 基本推理技术基本推理技术 推理的概念及其类型 推理的控制策略人工智能及其应用7推理的概念及其类型n定义：定义：从已有事实和知识中推出结论。从已有事实和知识中推出结论。在人工智能系统中，推理机是由程序实现的，在人工智能系统

5、中，推理机是由程序实现的，它利用知识库中的知识，按一定的控制策略求解它利用知识库中的知识，按一定的控制策略求解问题。问题。人工智能及其应用8推理的概念及其类型n推理方法分类：推理方法分类：v按途径分：按途径分：演绎推理、归纳推理、默认推理。演绎推理、归纳推理、默认推理。v按所用知识的确定性分：按所用知识的确定性分：确定性推理、不确定推理。确定性推理、不确定推理。v按结论是否单调增加分：按结论是否单调增加分：单调推理、非单调推理。单调推理、非单调推理。v按推理中是否运用启发性知识分：按推理中是否运用启发性知识分：启发式推理、非启发式推理。启发式推理、非启发式推理。人工智能及其应用9推理的控制策略

6、n推理系统构成：推理系统构成：知识库知识库 、数据库、数据库 、推理机、推理机 。n推理方向：推理方向：(1)(1)正向推理：由已知事实出发向结论方向的推理，正向推理：由已知事实出发向结论方向的推理，也称事实驱动推理。也称事实驱动推理。(2)(2)反向推理：以某个假设目标作为出发点的推理，反向推理：以某个假设目标作为出发点的推理，也称为目标驱动推理或逆向推理。也称为目标驱动推理或逆向推理。(3)(3)正反向混合推理正反向混合推理:正向和反向推理相结合的推理。正向和反向推理相结合的推理。人工智能及其应用10推理的控制策略n搜索策略：搜索策略：状态空间搜索状态空间搜索(广度优先搜索、深度优先搜索、

7、有界广度优先搜索、深度优先搜索、有界深度优先搜索等深度优先搜索等)、启发式搜索等。、启发式搜索等。n冲突解决策略：冲突解决策略：(1)(1)专一性排序专一性排序 (5)(5)上下文限制上下文限制 (2)(2)规则排序规则排序 (6)(6)按匹配度排序按匹配度排序 (3)(3)数据排序数据排序 (7)(7)按条件个数排序按条件个数排序 (4)(4)就近排序就近排序人工智能及其应用11 3.4 3.4 搜索策略的效率搜索策略的效率 穿透率 有效分支因素 提高搜索效率的一般原则 人工智能及其应用12穿透率 n定义：定义：反映目标搜索时的搜索范围。反映目标搜索时的搜索范围。P还和问题的难度相关，一般是

8、还和问题的难度相关，一般是L越大，问题越大，问题越困难，越困难，P值越小；反之值越小；反之P则越大。则越大。TLP/人工智能及其应用13有效分支因素 n定义：定义：v有效节点有效节点平均生成的子节点总数平均生成的子节点总数:v搜索策略的搜索策略的有效分支因素有效分支因素评价评价:v搜索策略的搜索策略的外显率外显率评价评价:TBBBBL.32)1/()(BBBBTL)1(/)1(LBBBLP人工智能及其应用14提高搜索效率的一般原则 n定性策略：定性策略：v特殊优先策略特殊优先策略 v新知识优先策略新知识优先策略 v差异性优先策略差异性优先策略 v其它策略其它策略 人工智能及其应用153.5 3

9、.5 基本搜索策略基本搜索策略特点特点:非启发的、解决树状结构问题非启发的、解决树状结构问题广度优先搜索 深度优先搜索 有界深度优先搜索代价推进搜索 人工智能及其应用16广度优先搜索n搜索原则：搜索原则：深度越深度越小小、越、越早早生成结点的优先级越高。生成结点的优先级越高。当最低层不止一个结点时，它选择最先生当最低层不止一个结点时，它选择最先生成的结点进行搜索。成的结点进行搜索。人工智能及其应用17广度优先搜索n例例3-4：八数码问题八数码问题(1)(1)操作规定操作规定:允许空格四周上、下、左、右的数允许空格四周上、下、左、右的数码块移入空格中，不许斜方向移动，不许返回码块移入空格中，不许

10、斜方向移动，不许返回先辈结点。先辈结点。初始布局初始布局S和目标状态和目标状态D如下图所示：如下图所示：2674138516748325SD人工智能及其应用18广度优先搜索2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 58 32 1 47 6 58 3 2 1 47 6 52 81 4 37 6 52 31 8 47 6 52 8 31 4 57 6 2 31 8 47 6 52 8 31 6 4 7 58 1 32 47 6 58 3 42 1 7 6 58 1 3 2 47 6 58 1 32 47 6

11、 5 8 32 6 41 7 52 8 37 46 1 52 8 1 6 37 5 42 8 37 1 46 52 8 31 67 5 41 2 38 47 6 51 2 37 8 4 6 52 3 41 87 6 52 3 41 8 57 6 2 81 4 37 6 52 4 81 37 6 52 8 31 4 5 7 62 8 36 41 7 52 8 31 57 4 68 1 32 6 47 52 8 3 7 46 1 52 37 8 46 1 52 8 37 46 1 52 8 37 16 5 42 8 31 6 7 5 42 8 3 6 41 7 52 8 31 4 57 62 81

12、 4 37 6 52 3 41 87 6 51 2 3 8 47 6 52 8 37 1 46 52 8 31 6 47 5 2 8 31 6 47 52 8 31 47 6 5S1234512131110987614151617222324252618192021D例例3-4的的广度优先搜索树：广度优先搜索树：人工智能及其应用19广度优先搜索n广度优先算法步骤：广度优先算法步骤：(1)初始结点初始结点S加入到队列加入到队列OPEN的尾部；的尾部；(2)若若OPEN为空，则搜索失败，问题无解；为空，则搜索失败，问题无解；(3)取出取出OPEN队头的结点队头的结点n，并放入，并放入CLOSE队列

13、中；队列中；(4)若若n是目标结点是目标结点D，则搜索成功，问题有解；，则搜索成功，问题有解；(5)若若n是叶结点，则转是叶结点，则转(2)；(6)扩展扩展n结点结点(即找出它的所有直接后继即找出它的所有直接后继)，并把它的诸子，并把它的诸子结点依次加入结点依次加入OPEN队尾，修改这些子结点的返回指队尾，修改这些子结点的返回指针，使其指向结点针，使其指向结点n。转。转(2)。人工智能及其应用20深度优先搜索n搜索原则：搜索原则：深度越深度越大大、越、越晚晚产生结点的优先级越高。产生结点的优先级越高。深度优先搜索是不完备的，属于非算法的搜深度优先搜索是不完备的，属于非算法的搜索过程。索过程。人

14、工智能及其应用21深度优先搜索n例例3-5：八数码问题八数码问题(2)(2)操作规定已在广度优先搜索算法举例中介绍过。操作规定已在广度优先搜索算法举例中介绍过。初始布局初始布局S和目标状态和目标状态D如下图所示：如下图所示：2746138516748325SD人工智能及其应用22深度优先搜索2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 31 6 7 5 42 8 31 67 5 42 8 1 6 37 5 42 81 6 37 5 4 2 81 6 37 5 42 6 81 37 5 42 6 8 1 37 5 42 6 8

15、1 3 7 5 42 6 81 5 37 42 6 81 5 3 7 42 6 81 5 37 4 2 6 81 5 7 4 32 6 1 5 87 4 32 6 81 57 4 32 5 61 87 4 3 2 61 5 87 4 32 61 5 87 4 32 5 6 1 87 4 32 5 61 8 7 4 32 5 61 4 87 32 5 61 4 8 7 32 5 61 4 87 3 2 5 61 4 7 3 82 5 61 47 3 82 5 1 4 67 3 8S123456789101112131415162 51 4 67 3 82 4 51 67 3 8 2 51 4 6

16、7 3 82 4 5 1 67 3 82 4 51 6 7 3 82 4 51 3 67 82 4 51 3 6 7 82 4 51 3 67 8 17181920例例3-5的深的深度优先搜索树：度优先搜索树：人工智能及其应用23深度优先搜索n深度优先算法步骤：深度优先算法步骤：(1)初始结点初始结点S放入堆栈放入堆栈OPEN中；中；(2)若若OPEN为空，则搜索失败，问题无解；为空，则搜索失败，问题无解；(3)弹出弹出OPEN表中最顶端结点放到表中最顶端结点放到CLOSE表中，并表中，并给出顺序编号给出顺序编号n；(4)若若n为目标结点为目标结点D，则搜索成功，问题有解；，则搜索成功，问题有

17、解；(5)若若n无子结点，转无子结点，转(2)；(6)扩展扩展n结点，将其所有子结点配上返回结点，将其所有子结点配上返回n的指针，的指针，并按次序压入并按次序压入OPEN堆栈，转堆栈，转(2)。人工智能及其应用24有界深度优先搜索n特点：特点：引入搜索深度限制值引入搜索深度限制值d，使深度优先搜索使深度优先搜索过程具有完备性过程具有完备性 。n例例3-6：八数码问题八数码问题(2)(2)设定搜索深度限制设定搜索深度限制d=5，问题同深度优先问题同深度优先算法中的八数码问题算法中的八数码问题(2)(2)。人工智能及其应用25有界深度优先搜索2 8 31 6 47 512 8 31 6 47 5

18、22 8 31 6 7 5 432 81 6 37 5 442 8 31 6 4 7 52 8 31 47 6 52 8 31 4 7 6 52 8 3 1 47 6 52 31 8 47 6 52 3 1 8 47 6 5 2 31 8 47 6 51 2 3 8 47 6 52 3 41 8 7 6 51 2 37 8 4 6 51 2 38 47 6 52 3 41 87 6 52 3 41 8 57 6 2 81 4 37 6 52 4 81 37 6 52 81 4 37 6 52 8 1 4 37 6 52 8 31 4 57 6 2 8 31 4 5 7 62 8 31 57 4

19、 62 8 31 4 57 6 8 32 1 67 5 42 8 37 1 6 5 42 8 3 1 67 5 42 8 31 67 5 42 8 31 5 67 4 2 31 8 67 5 42 3 1 8 67 5 42 8 31 5 6 7 42 8 31 5 67 4 2 81 6 37 5 42 6 81 37 5 42 81 6 37 5 42 31 8 67 5 4523262734332829302524192021151289DS18221716141311107636353231例例3-6的有界深的有界深度优先搜索树：度优先搜索树：人工智能及其应用26有界深度优先搜索n有界

20、深度优先算法步骤：有界深度优先算法步骤：(1)(1)初始结点初始结点S S放入堆栈放入堆栈OPEN中；中；(2)(2)若若OPEN为空，则搜索失败，问题无解；为空，则搜索失败，问题无解；(3)(3)弹出弹出OPEN中栈顶结点中栈顶结点n n，放入，放入CLOSE表中，并给表中，并给出顺序编号出顺序编号n n；(4)(4)若若n n为目标结点为目标结点D D，则搜索成功，问题有解；，则搜索成功，问题有解；(5)(5)若若n n的深度的深度d(nd(n)=d)=d，则转，则转(2)(2)；(6)(6)若若n n无子结点，即不可扩展，转无子结点，即不可扩展，转(2)(2)；(7)(7)扩展结点扩展结

21、点n n，将其所有子结点配上返回，将其所有子结点配上返回n n的指针，的指针，并压入并压入OPEN堆栈，转堆栈，转(2)(2)。人工智能及其应用27代价推进搜索n特点：特点：节点间有向边的代价不同节点间有向边的代价不同n算法修改：算法修改：(1)广度优先搜索法：每次从广度优先搜索法：每次从OPEN表中取出具有最小表中取出具有最小代价的节点进行扩展代价的节点进行扩展。(2)有界深度优先搜索法：用代价限制有界深度优先搜索法：用代价限制g代替深度限制代替深度限制d，用代价用代价g(n)代替节点深度代替节点深度d(n)。人工智能及其应用28代价推进搜索n例例3-7：求下图所示的旅行问题中，费用最小的路

22、线，设出发求下图所示的旅行问题中，费用最小的路线，设出发地是地是A A城，目的地是城，目的地是E E城，图中各边上的数字代表交通城，图中各边上的数字代表交通费用。费用。CEDBA245104337人工智能及其应用29代价推进搜索23441054534104545374451012534ADBCE/24A/0AB/2AC/3AD/7ABC/5ABD/6ACB/6ACD/7ACE/13ACDB/11ACDE/12ACBD/10ACBDE/15ABDC/10ABDE/11ABDCE/20ABCE/15ABCD/9ABCDE/1461020111221137ADB/11ADC/11ADE/12ADBC

23、/14ADCE/21310101718192523262214151689ADCB/14243例例3-7的代价推进的代价推进搜索树：搜索树：人工智能及其应用303.6 3.6 启发式搜索策略启发式搜索策略启发信息和估价函数 局部择优搜索 全局择优搜索 A*算法 人工智能及其应用31启发信息和估价函数n启发信息：启发信息：与具体问题解相关的控制性知识与具体问题解相关的控制性知识 。n估价函数：估价函数：估计估计OPEN表中各扩展节点的重要程度，给它表中各扩展节点的重要程度，给它们排定扩展次序。们排定扩展次序。人工智能及其应用32局部择优搜索n基本思想基本思想：选择一个节点的后继节点，是在它的所有

24、子节点中，选择一个节点的后继节点，是在它的所有子节点中，选估价选估价函数函数f(n)最优者。因此，亦称最优者。因此，亦称“瞎子爬山法瞎子爬山法”。n特点：特点：v可以取消可以取消OPEN表，每次扩展后只保留一个最优子表，每次扩展后只保留一个最优子节点，直接放入节点，直接放入CLOSE表中，丢掉其它子节点。表中，丢掉其它子节点。v主要在单因素、单极值情况下使用；在多因素，多主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳解。极值情况下，找不到最佳解。人工智能及其应用33局部择优搜索n例例3-8：在深度优先搜索算法的八数码问题在深度优先搜索算法的八数码问题(2)中，如果把中，如果

25、把估价函数定义为估价函数定义为f(n)=w(n)，其中，其中，w(n)表示结点表示结点n的格的格局与目标结点局与目标结点D格局相比位置不符的数码个数。用局部格局相比位置不符的数码个数。用局部择优搜索策略求解该问题择优搜索策略求解该问题。其搜索树如下页图所示：。其搜索树如下页图所示：人工智能及其应用342 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 52 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 5 8 32 1 47 6 52 8 37 1 4 6 58 32 1 47 6 58 1 32 47 6 58

26、32 1 47 6 58 1 3 2 47 6 58 1 32 47 6 58 1 32 6 47 5 1 38 2 47 6 58 1 37 2 4 6 51 38 2 47 6 51 2 38 47 6 51 38 2 47 6 512345678910DS44444442233333355130例例3-8的的局部择优搜索树：局部择优搜索树：人工智能及其应用35全局择优搜索n特点：特点：v在在OPEN表中保留所有已生成而未扩展的节表中保留所有已生成而未扩展的节点，并用估价函数点，并用估价函数f(nf(n)对它们全部进行估计，对它们全部进行估计，从中选出最优的节点进行扩展，因此，亦称从中选出

27、最优的节点进行扩展，因此，亦称“最好优先搜索法最好优先搜索法”。v得到的不一定是实际上的最佳解。得到的不一定是实际上的最佳解。人工智能及其应用36全局择优搜索n例例3-9：八数码问题八数码问题(2)(2)如果将广度优先搜索算法中的估计函数定义为：如果将广度优先搜索算法中的估计函数定义为：f(n)=d(n)+w(n)，其中，其中，d(n)代表结点代表结点n的扩展的扩展深度，深度，w(n)含义同例含义同例3-8。用全局择优搜索法求解此问题。其搜索树如下用全局择优搜索法求解此问题。其搜索树如下页图所示。图中，状态结点右边圆圈中的数字页图所示。图中，状态结点右边圆圈中的数字表示估价函数值。表示估价函数

28、值。人工智能及其应用37全局择优搜索2 8 31 47 6 5S12 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 52 8 31 6 47 52 8 37 1 4 6 5 8 3 2 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5D456345554444666例例3-9的全的全局择优搜索树：局择优搜索树：人工智能及其应用38A*算法n特点：特点：v对状态空间搜索算法中的扩展节点选择原则进行了对状态空间搜索算法中的扩展节点选择原则进行了限制。限制。v选用了

29、一个比较特殊的估价函数。选用了一个比较特殊的估价函数。n定义定义:vA*算法算法vA 算法算法 n性质性质:v采纳性采纳性v单调性单调性v信息性信息性人工智能及其应用393.7 3.7 基于规划的启发式搜索原理基于规划的启发式搜索原理 基本规划 多层规划 人工智能及其应用40基本规划 n规划解决问题的方法规划解决问题的方法:v引入一系列子目标引入一系列子目标 v把问题分解成若干子问题把问题分解成若干子问题 v解决子问题解决子问题n产生规划的基本方法产生规划的基本方法:差异减小法差异减小法 人工智能及其应用41多层规划 n多层规划解决问题的方法多层规划解决问题的方法:v给出一个总的粗略设想给出一

30、个总的粗略设想 v逐步细化设想逐步细化设想v产生详尽规划为止产生详尽规划为止 人工智能及其应用42多层规划 n例例3-12:假设假设有有A、B、C三块大小不同的积木和一个机三块大小不同的积木和一个机械手构成了下图所示的现实状态。试制定机械手将械手构成了下图所示的现实状态。试制定机械手将S状态变为状态变为D状态的行动规划。其中限制机械手一状态的行动规划。其中限制机械手一次只能搬动一块积木，且大块不能压在小块之上。次只能搬动一块积木，且大块不能压在小块之上。CABCBADS人工智能及其应用43多层规划引入几个通用规划引入几个通用规划：YX清光Y顶置X于地上YX(a)清光Y顶的规划清光X顶清光Y顶置X于Y顶(b)置X于Y上的规划人工智能及其应用44多层规划用过程网络表示的机械手行动控制多层规划如下图所示：用过程网络表示的机械手行动控制多层规划如下图所示：原始问题置A于B上置B于C上(a)置A于B上置B于C上(b)第一级细化(c)第二级细化矛盾清光A顶清光C顶清光B顶清光B顶人工智能及其应用45多层规划去除矛盾和冗余的多层规划如下图所示：去除矛盾和冗余的多层规划如下图所示：清光A顶清光B顶清光B顶清光C顶置A于B上置B于C上冗余(a)去掉矛盾清光A顶清光B顶清光C顶置A于B上置B于C上(b)去冗余结点人工智能及其应用46