《人工智能第三章_搜索策略-2czhx.pptx》由会员分享，可在线阅读，更多相关《人工智能第三章_搜索策略-2czhx.pptx（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2023/3/231启发式搜索启发式搜索o启发式知识启发式知识指导指导OPEN表排序表排序的的一般图搜索一般图搜索：n全局排序全局排序对对OPEN表中的表中的所有节点排序所有节点排序，使使最有希望最有希望的节点排在表首。的节点排在表首。oA算法，算法，A*算法（掌握！）算法（掌握！）n局部排序局部排序仅对仅对新新扩展出来的子节点排序扩展出来的子节点排序，使这些使这些新新节点中节点中最有希望最有希望者能优先取出考察者能优先取出考察和扩展；和扩展；o爬山法（了解，爬山法（了解，对对深度优先法深度优先法的改进的改进）；）；2023/3/232 简单的搜索策略：简单的搜索策略：g(n)0,f(n)=h
2、(n),g(n)0,f(n)=h(n),局部排序局部排序只排序新扩展出来的子节点，即局部排序只排序新扩展出来的子节点，即局部排序 简单易行，适用于不要求最优解答的问题求解任务。简单易行，适用于不要求最优解答的问题求解任务。1 1）爬山法）爬山法实现启发式搜索的最简单方法。实现启发式搜索的最简单方法。类似于人爬山类似于人爬山只要好爬，总是选取最陡处，以求快速登顶。只要好爬，总是选取最陡处，以求快速登顶。求求函函数数极极大大值值问问题题非非数数值值解解法法，依依赖赖于于启启发发式式知知识识，试试探探性性地地逐逐步步向向顶顶峰峰逼近逼近 适用于能适用于能逐步求精逐步求精的问题。的问题。爬山法特点：爬
3、山法特点：只能向上，不准后退，从而简化了搜索算法；体现在：只能向上，不准后退，从而简化了搜索算法；体现在：*从从当当前前状状态态节节点点扩扩展展出出的的子子节节点点（相相当当于于找找到到上上爬爬的的路路径径）中中，将将h(n)h(n)最最小小的的子子节节点点（对对应应于于到到顶顶峰峰最最近近的的上上爬爬路路径径）作作为为下下一一次次考考察察和和扩扩展展的的节节点点，其其余余子子节点全部丢弃。节点全部丢弃。不需设置不需设置OPENOPEN和和CLOSECLOSE表，因为没有必要保存任何待扩展节点；表，因为没有必要保存任何待扩展节点；爬爬山山法法对对于于单单一一极极值值问问题题（登登单单一一山山峰
4、峰）十十分分有有效效而而又又简简便便,对对于于具具有有多多极极值值的问题无能为力的问题无能为力会错登上次高峰而失败：不能到达最高峰。会错登上次高峰而失败：不能到达最高峰。回溯策略和爬山法回溯策略和爬山法 2023/3/233 2 2）回溯策略）回溯策略 可可以以有有效效地地克克服服爬爬山山法法面面临临的的困困难难保保存存了了每每次次扩扩展展出出的的子子节节点点，并并按按h(n)h(n)值值从从小到大排列。小到大排列。相相当当于于爬爬山山的的过过程程中中记记住住了了途途经经的的岔岔路路口口路路径径搜搜索索失失败败时时回回溯溯（后后退退），向向另一路径方向搜索另一路径方向搜索 回溯策略和爬山法回溯
5、策略和爬山法 2023/3/234 2 2）回溯策略）回溯策略 递归过程递归过程实现回溯策略的有效方式实现回溯策略的有效方式 算法就取名为算法就取名为BACKTRACK(n),BACKTRACK(n),参数参数n n为当前被扩展的节点，为当前被扩展的节点，初次调用时初次调用时n n即为初始状态节点即为初始状态节点s s；分二个部分：分二个部分：*判断当前节点判断当前节点n n的状态，的状态，*作作搜搜索索工工作作扩扩展展节节点点n n，递递归归调调用用该该算算法法，处处理理返返回结果。回结果。回溯策略和爬山法回溯策略和爬山法 2023/3/235令令PATHPATH、SNLSNL、n n、n
6、n 为局部变量：为局部变量：PATH-PATH-节点列表，指示解答路径；节点列表，指示解答路径；SNL-SNL-当前节点扩展出的子节点列表；当前节点扩展出的子节点列表；MOVE-FIRST(SNL)-MOVE-FIRST(SNL)-把把SNLSNL表表首首的的节节点点移移出出，作作为为下下一一次次要要加加以以扩扩展展的的节点；节点；n n、n n-分别指示当前考察和下一次考察的节点。分别指示当前考察和下一次考察的节点。该该递递归归过过程程的的算算法法就就取取名名为为BACKTRACK(n),BACKTRACK(n),参参数数n n为为当当前前被被扩扩展展的的节节点点，算算法法的的初初次调用式是
7、次调用式是BACKTRACK(s),sBACKTRACK(s),s即为初始状态节点。算法的步骤如下：即为初始状态节点。算法的步骤如下：（1 1）若若n n是目标状态节点，则算法的本次调用成功结束，返回空表；是目标状态节点，则算法的本次调用成功结束，返回空表；（2 2）若若n n是失败状态，则算法的本次调用失败结束，返回是失败状态，则算法的本次调用失败结束，返回FAILFAIL；（3 3）扩扩展展节节点点n n，将将生生成成的的子子节节点点置置于于列列表表SNLSNL，并并按按评评价价函函数数f(k)f(k)=h(k)h(k)的的值从小到大排序（值从小到大排序（k k指示子节点）；指示子节点）；
8、（4 4）若若SNLSNL为空，则算法的本次调用失败结束，返回为空，则算法的本次调用失败结束，返回FAILFAIL；（5 5）n=MOVE-FIRST(SNL)n=MOVE-FIRST(SNL)；（6 6）PATH=BACKTRACK(n)PATH=BACKTRACK(n)；（7 7）若若PATH=FAIL,PATH=FAIL,返回到语句（返回到语句（4 4）；）；（8 8）将将nn加到加到PATHPATH表首，算法的本次调用成功结束，返回表首，算法的本次调用成功结束，返回PATHPATH。2023/3/236 2 2）回溯策略）回溯策略 三种失败状态：三种失败状态：不合法状态（如传教士和野人
9、问题中所述的那样）不合法状态（如传教士和野人问题中所述的那样）旧旧状状态态重重现现（如如八八数数码码游游戏戏中中某某一一棋棋盘盘布布局局的的重重现现，会会导导致搜索算法死循环），致搜索算法死循环），状状态态节节点点深深度度超超过过预预定定限限度度（例例如如八八数数码码游游戏戏中中，指指示示解解答路径不超过答路径不超过6 6步）。步）。回溯条件回溯条件 失败状态，由算法第（失败状态，由算法第（2 2）句指示；）句指示；搜索进入搜索进入“死胡同死胡同”，由该算法的第，由该算法的第(4)(4)句定义。句定义。回溯策略和爬山法回溯策略和爬山法 2023/3/237 2 2）回溯策略）回溯策略 解解答答
10、路路径径的的生生成成从从相相应应于于目目标标状状态态节节点点的的空空表表开开始始，递递归归返返回回PATHPATH。影响回溯算法效率的关键因素影响回溯算法效率的关键因素回溯次数回溯次数。回溯回溯搜索到失败状态时的一种弥补行为，搜索到失败状态时的一种弥补行为，准准确确选选择择下下一一步步搜搜索索考考察察的的节节点点大大幅幅度度减减少少甚甚至至避避免免回回溯。溯。设计好的启发式函数设计好的启发式函数h(n)h(n)是至关重要的。是至关重要的。回溯策略和爬山法回溯策略和爬山法 2023/3/238课堂练习课堂练习:提高题提高题o在应用递归回溯算法解决四皇后的问题中，若按在应用递归回溯算法解决四皇后的
11、问题中，若按行行的序号从小到大试探性放置各的序号从小到大试探性放置各列列的皇后，请画出搜的皇后，请画出搜索图，并指出分别从算法第索图，并指出分别从算法第2步和第步和第4步回溯的次数。步回溯的次数。2023/3/239 定义定义L，为表示清晰起见，为表示清晰起见,L表中只记载皇后所在列表中只记载皇后所在列,皇皇后所在行可由在后所在行可由在L表中的先后位置指示表中的先后位置指示,例如例如L=(1 3)指示两个皇后位置分别为第指示两个皇后位置分别为第1行第行第1列和第列和第2行第行第3列。列。搜索图搜索图(树树)如右图所示如右图所示:共回溯共回溯22次次,其中算法第其中算法第2步的回溯步的回溯18次
12、次,算法第算法第4次的回溯次的回溯4次。次。2023/3/23103.4 3.4 问题归约和与或图启发式搜索问题归约和与或图启发式搜索o问题归约问题归约是人求解问题常用的策略：是人求解问题常用的策略：n把把复杂的问题复杂的问题变换为若干需要变换为若干需要同时同时处理的较为处理的较为简单的子问题简单的子问题后再加以分别求解后再加以分别求解n只有子问题全部解决时只有子问题全部解决时，问题才算解决问题才算解决；n问题的解答问题的解答由子问题的解答联合由子问题的解答联合构成。构成。o本节主要内容：本节主要内容：n问题归约的描述（理解）问题归约的描述（理解）n与或图搜索的基本过程（理解）与或图搜索的基本
13、过程（理解）n与或图的启发式搜索（与或图的启发式搜索（掌握掌握）2023/3/2311问题归约法问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题2023/3/2312o问题归约可以用三元组表示：（问题归约可以用三元组表示：（S S0 0，O O，P P），其中），其中nS S0 0是初始问题，即要求解的问题；是初始问题，即要求解的问题；nP P是本原问题集，其中的每一个问题是不用证是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或明的，自然成立的，如公理、已知事实等，或
14、已证明过的问题；已证明过的问题；nO O是操作算子集，它是一组变换规则，通过一是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。个操作算子把一个问题化成若干个子问题。2023/3/2313o问题归约表示方法就是由初始问题出发，运问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直用操作算子产生子问题的子问题，这样一直进行到进行到产生的问题均为本原问题产生的问题均为本原问题，则问题得，则问题得解。解。2023/3/2314o看如下符号积分问题：看如下符号积分问题：初始问题
15、初始问题f f(x x)d)dx x变换规则变换规则积分规则积分规则本原问题本原问题可直接求原函数和积分，如可直接求原函数和积分，如sin(sin(x x)d)dx x，coscos (x x)d)dx x等。等。所有问题归约的最终目的是产生本原问题。所有问题归约的最终目的是产生本原问题。2023/3/2315符号积分问题符号积分问题（sin3x+x4/(x2+1)）dx=sin3xdx+(x4/(x2+1)dx=-(1-cos2x)dcosx+(x2-1+1/(1+x2)dx=(-dcosx+cos2xdcosx)+(x2dx-dx+(1/(1+x2)dx）=-cosx+cos3x/3+x3
16、/3-x+arctgx2023/3/2316分子结构识别问题分子结构识别问题 如何区分分子式相同但分子结构不同的有机化合物成为如何区分分子式相同但分子结构不同的有机化合物成为重要而又困难的问题。著名的专家系统重要而又困难的问题。著名的专家系统 DENDRAL能用能用于有效地识别分子结构，该系统建立了一套重写规则去于有效地识别分子结构，该系统建立了一套重写规则去把分子式重写为原子数较少的分子式和原子间结合关系把分子式重写为原子数较少的分子式和原子间结合关系的混合结构的混合结构 2023/3/2317o问题归约的实质：问题归约的实质：从目标从目标(要解决的问题要解决的问题)出发逆向推理，建出发逆向
17、推理，建立子问题以及子问题的子问题，直至最立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问后把初始问题归约为一个平凡的本原问题集合。题集合。2023/3/2318n应用应用问题归约策略问题归约策略得到的得到的状态空间图状态空间图，也称为，也称为“与或图与或图”n逻辑逻辑“与与”关系关系用用圆弧圆弧将几条将几条节点间关联弧节点间关联弧连接在连接在一起一起o表示问题分解为子问题表示问题分解为子问题；o子问题的状态子问题的状态联合起来构成联合起来构成问题状态问题状态。o子问题全部解决才会导致问题的解决子问题全部解决才会导致问题的解决；n逻辑逻辑“或或”关系关系：o问题可以有问题可
18、以有多种分解方式多种分解方式；o问题（子问题）可能激活问题（子问题）可能激活多个状态变迁操作多个状态变迁操作；o只要一种只要一种分解方式分解方式或或状态变迁操作状态变迁操作能导致最终的解答成功即可；能导致最终的解答成功即可；o导致多个可能的解答。导致多个可能的解答。与或图与或图2023/3/2319o用用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、决，如下图所示。图中各节来解决，如下图所示。图中各节点表示要求解的问题或子问题。点表示要求解的问题或子问题。与或图与或图2023/3/2320梵塔问题梵塔问题n问题描述：问题描述：n初始状态下三个盘按初始状态下三个盘按A、B、C顺序堆放在顺序堆放在1号柱子上；号柱子上；n目标状态下三个盘以同样次序顺序堆放在目标状态下三个盘以同样次序顺序堆放在3号柱子上；号柱子上；n盘子的盘子的搬移规则搬移规则：o每次只能搬一个盘子；每次只能搬一个盘子；o较大盘不能压放在较小盘之上；较大盘不能压放在较小盘之上；CAB初始状态初始状态(1 1 1)目标目标状态状态(3 3 3)CAB132132与或图与或图202
20、3/3/2321梵塔问题梵塔问题状态空间图状态空间图(1,1,1)(3,3,3)(1,1,1)(2,2,1)(2,2,1)(2,2,3)(2,2,3)(3,3,3)(2,2,1)132CAB(2,2,3)123ABC目标目标状态状态(3 3 3)CAB1322023/3/2322梵塔问题梵塔问题状态空间图状态空间图(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)20
21、23/3/2323梵塔问题梵塔问题(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)123456789子问题间有子问题间有交互作用交互作用，问题分解问题分解注意注意正确的顺序正确的顺序2023/3/2324与或图搜索与或图搜索o与或图与或图视为对视为对一般图一般图(或图或图)的扩展；的扩展；n引入引入K-连接连接o父子节点父子节点间可以存在间可以存在“与与”关系关系n
22、结果结果解图解图。o解答路径往往不复存在，代之以广义的解路径解答路径往往不复存在，代之以广义的解路径解图解图。问题归约求解问题的过程问题归约求解问题的过程表示为与或图搜索表示为与或图搜索2023/3/2325与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n1、K-连接连接o从从父节点父节点到到K个个子节点子节点的连接，的连接，子节点子节点间间有有“与与”关系关系；o以以圆弧圆弧指示指示这些子节点这些子节点间间的的“与与”关系关系；o一个父节点可以一个父节点可以有多个有多个K-连接连接nK-连接间连接间”或或”关系关系o当当所有的所有的K都等于都等于1时，时，与或图与或图蜕化
23、为蜕化为一般图（或图）一般图（或图）。3个子节点个子节点2个子节点个子节点2023/3/2326与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n2、根、叶、根、叶、终节点终节点o根节点根节点无父节点的节点无父节点的节点n用于指示用于指示问题初始状态（和一般图一样）问题初始状态（和一般图一样）o叶节点叶节点无子节点的节点无子节点的节点o终节点终节点能用于能用于联合表示目标状态的节点联合表示目标状态的节点n终节点必定是叶节点终节点必定是叶节点，反之不然；，反之不然；n目标状态目标状态终结点的集合终结点的集合。2023/3/2327一些关于与或图的术语一些关于与或图的术语HMBC
24、DEFGAN父节点父节点与节与节点点弧线弧线或节或节点点子节子节点点终节点终节点2023/3/2328与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图o解图解图中，中，节点节点或或节点组间节点组间不存在不存在“或或”关系；关系；o所有叶节点都是终节点所有叶节点都是终节点2023/3/2329与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成n自自根节点根节点开始选开始选K-连连接接;n从该从该K-连接连接指向的指向的每每个子节点个子节点出发，再选出发，再选一一K-连接
25、连接;n如此反复进行，直到如此反复进行，直到所有所有K-连接连接都指向都指向终终节点节点为止为止.2023/3/23302023/3/2331与或图搜索与或图搜索o1)与或图搜索的基本概念与或图搜索的基本概念n3、解图的生成解图的生成o解图纯粹是一种解图纯粹是一种“与与”图图n解图解图中，中，节点节点或或节点组间节点组间不存在不存在“或或”关系；关系；n所有所有叶节点叶节点都是都是终节点终节点o与或图与或图中存在中存在“或或”关系，关系，搜索到多个解图搜索到多个解图；2023/3/2332与或图搜索与或图搜索o2)解图解图、解图代价、能解节点和不能解节点的定义、解图代价、能解节点和不能解节点的
26、定义n(1)解图解图与或图与或图（记为（记为G）任一节点（记为）任一节点（记为n）到）到终终节点集合节点集合的的解图解图（记为（记为G）是）是G的的子图子图。o(1)若若n是是终节点终节点，则，则G就就由单一节点由单一节点n构成构成；o(2)若若n有一有一K-连接连接指向子节点指向子节点n1，n2，nk,且每且每个子节点都有到终节点集合的个子节点都有到终节点集合的解图解图，则，则G由该由该k-连连接接和所有这些和所有这些相应于子节点的解图相应于子节点的解图构成构成;o(3)否则不存在否则不存在n到到终节点集合终节点集合的的解图解图。2023/3/2333与或图搜索与或图搜索o2)解图、解图、解
27、图代价解图代价、能解节点和不能解节点的定义、能解节点和不能解节点的定义n(2)解图代价解图代价 以以C(n)指示节点指示节点n到到终节点集合终节点集合解图解图的代价，并令的代价，并令K-连接的代价就为连接的代价就为K,则则 o(1)若若n是终节点，则是终节点，则C(n)=0；o(2)若若n有一有一K-连接连接指向子节点指向子节点n1，n2，nk,且这且这些子节点每个都有到终节点集合的解图些子节点每个都有到终节点集合的解图,则则C(n)=K+C(n1)+C(n2)+C(nk)352023/3/2334与或图搜索与或图搜索o2)解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节
28、点的定义的定义n(3)能解节点能解节点 o(1)终节点是能解节点终节点是能解节点；o(2)若节点若节点n有有一一K-连接连接指向子节点指向子节点n1，n2，nk,且这些且这些子节点都是能解节点子节点都是能解节点，则，则n是能解节点；是能解节点；能解节点能解节点能解节点能解节点能解节点能解节点能解节点能解节点2023/3/2335与或图搜索与或图搜索o2)解图、解图代价、解图、解图代价、能解节点能解节点和和不能解节点不能解节点的定义的定义n(4)不能解节点不能解节点o(1)非终节点的叶节点是不能解节点非终节点的叶节点是不能解节点；o(2)若节点若节点n的的每一个每一个K-连接连接都都至少至少指向
29、一个不能解指向一个不能解节点节点，则，则n是不能解节点。是不能解节点。能解节点能解节点不能解节点不能解节点能解节点能解节点不能解节点不能解节点不能解节点不能解节点2023/3/2336与或图的启发式搜索与或图的启发式搜索o与或图中搜索的是与或图中搜索的是解图解图，不是解答路径；，不是解答路径；n评价函数评价函数f(n)=h(n)nh(n)是对是对n到到终节点集合终节点集合解图最小解图代价解图最小解图代价的估计；的估计；o与或图中存在与或图中存在“或或”关系关系，会有会有多个候选的局部解图多个候选的局部解图；n选择选择局部解图中可能代价最小局部解图中可能代价最小的用于下一步搜索。的用于下一步搜索
30、。o1)（局部）解图代价（局部）解图代价f(n0)nn0初始状态节点初始状态节点n递归地计算出递归地计算出f(n0),比直接用比直接用h(n0)估算估算更为准确。更为准确。n父节点父节点n的的K-连接连接指向的子节点：指向的子节点：n1，n2，nknf(n)=K+h(n1)+h(n2)+h(nk)，代替，代替h(n)2023/3/2337与或图的启发式搜索与或图的启发式搜索o2)AO*算法算法o符号说明：符号说明：nG-搜索图；搜索图；nG-被选中的被选中的待扩展局部解图待扩展局部解图；nLGS-待扩展待扩展局部解图集局部解图集；nn0-根节点根节点，即初始状态节点；，即初始状态节点；nn-被
31、选中的被选中的待扩展节点待扩展节点；nfi(n0)-第第i个个待扩展局部解图待扩展局部解图的的可能代价可能代价。2023/3/2338与或图的启发式搜索与或图的启发式搜索o2)AO*算法算法o算法划分二个阶段：算法划分二个阶段：n1、初始化、初始化 o建立只包含建立只包含初始状态节点初始状态节点n0的搜索图的搜索图G:=n0；o待扩展局部解图集待扩展局部解图集LGS:=；n2、搜索循环、搜索循环o选择选择和和扩展扩展LGS中的中的局部解图局部解图；o精化精化新局部解图新局部解图代价的估计代价的估计；o传递传递节点的节点的能解性能解性。2023/3/2339与或图的启发式搜索与或图的启发式搜索o
32、2、搜索循环、搜索循环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;2023/3/2340与或图的启发式搜索与或图的启发式搜索o2、搜索循环、搜索循环n选择选择和和扩展扩展LGS中的中的局部解图局部解图；n精化精化新新
33、局部解图局部解图代价的估计代价的估计o用公式用公式f(f(n n)=K+h(n1)+h(n2)+)=K+h(n1)+h(n2)+h(nk)h(nk)取代原先的取代原先的f(n);f(n);o递归地递归地作用到作用到初始节点初始节点n n0 0；n传递传递新局部解图中新局部解图中节点的节点的能解性能解性o标记标记作为作为终节点终节点的子节点为的子节点为能解节点能解节点；o递归地递归地传递节点的传递节点的能解性能解性到到初始节点初始节点n n0 0。f(n)=h(n)2023/3/23412023/3/2342与或图的启发式搜索与或图的启发式搜索o2)AO*算法算法oAO*算法应用例算法应用例o搜
34、索过程中，启发式函数搜索过程中，启发式函数h(ni)的的 估算如下：估算如下：oh(n0)=3oh(n1)=2oh(n2)=1oh(n3)=1oh(n4)=4oh(n5)=2oh(n6)=2oh(n7)=1oh(n8)=1oh(n13)=30123546 7 891011 121314 15161718 19 202023/3/2343初始化初始化候选的待扩展局部解图集候选的待扩展局部解图集LGS:0302023/3/2344012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:32114202023/3/2345012354循环循环1候选的待扩展局部解图集候选的待扩展局部
35、解图集LGS:321142031201235432114202023/3/2346012354循环循环1候选的待扩展局部解图集候选的待扩展局部解图集LGS:10211420512f(n)=K+h(n1)+h(n2)+h(nk)取代原先的取代原先的f(n);f1(n0)=2+h(n1)+h(n2)=5f2(n0)=3+h(n3)+h(n4)+h(n5)=102023/3/2347012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1021142056 7 8211122023/3/2348012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:102114
36、2057 811012215623422023/3/2349012354循环循环2候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 8110123166234225252023/3/2350012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 81101231662342131430循环循环32023/3/2351012354候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 81101261965342131430循环循环33622023/3/2352012354循环循环4候选的待扩展局部解图集候选的待扩展局部解图
37、集LGS:1041142077 811012619653421314301402023/3/2353012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:1041142077 811012619653421314301401502023/3/2354012354循环循环5候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 812012619653421314301401504712023/3/2355012354循环循环6候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 81201261965342131430140150902
38、023/3/2356012354搜索成功！搜索成功！候选的待扩展局部解图集候选的待扩展局部解图集LGS:1051142087 81201261965342131430140150902023/3/2357与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o1、从局部解图、从局部解图G中选择加以扩展的节点中选择加以扩展的节点nn与或图搜索的是与或图搜索的是解图解图而而非解路径非解路径；n选择选择f(n)=h(n)的值最小的值最小的节点的节点n加以扩展并不加以扩展并不一定会加速搜索过程；一定会加速搜索过程；n应选择导致解图代价发生较大变化应选择导致解图代价发生较大变化
39、的节点的节点n优先优先加以扩展；加以扩展；o使搜索的注意力快速地聚焦到实际代价较小的候选使搜索的注意力快速地聚焦到实际代价较小的候选解图上；解图上；n简单情况下，可简单情况下，可随机选择随机选择加以扩展的节点。加以扩展的节点。2023/3/2358与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o2、算法算法AO*与与A*的比较的比较n解图解图解答路径解答路径，n估计估计代价最小的局部解图代价最小的局部解图加以优先扩展加以优先扩展OPEN表中表中f(n)最小的节点最小的节点；n只考虑只考虑评价函数评价函数f(n)=h(n)同时计算分量同时计算分量g(n)和和h(
40、n)，n应用应用LGS存放存放待扩展局部解图待扩展局部解图，并依据，并依据fi(n0)值值排序排序应用应用OPEN表和表和CLOSE表分别存放表分别存放待待扩展节点扩展节点和和已扩展节点已扩展节点，并依据，并依据f(n)值值排序排序OPEN表。表。2023/3/2359与或图的启发式搜索与或图的启发式搜索o4）算法应用的若干问题）算法应用的若干问题o3、解图代价的重复计算、解图代价的重复计算n某些某些子节点子节点可能会有可能会有多个父节点多个父节点；n这种这种子节点子节点到终节点集合的到终节点集合的解图代价解图代价在计算自在计算自根节点根节点n0出发的解图时被出发的解图时被重复累计重复累计。1
41、7 817 814 1512517 8142216241182023/3/2360博弈博弈 n博弈提供了一个可构造的任务领域，在这个领博弈提供了一个可构造的任务领域，在这个领域中，具有明确的域中，具有明确的胜利胜利和和失败失败；n博弈问题对人工智能研究提出了严峻的挑战。博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和例如，如何表示博弈问题的状态、博弈过程和博弈知识等。博弈知识等。o这里讲的博弈是这里讲的博弈是二人博弈二人博弈，二人零和二人零和、全信息全信息、非偶然博弈非偶然博弈，博弈双方的利益是，博弈双方的利益是完全对立完全对立的。的。2023/3/2361n所
42、谓所谓“二人零和二人零和”，是指在博弈中只有，是指在博弈中只有“敌、我敌、我”二方。二方。且双方的利益完全对立，且双方的利益完全对立，其赢得函数之和为零其赢得函数之和为零，即，即 1+2=0 式中，式中，1为我方赢得为我方赢得(利益利益)；2为敌方赢得为敌方赢得(利益利益)。即：博弈的双方有三种结局：即：博弈的双方有三种结局：(1)我胜：我胜：10；敌负：；敌负：2=-10。(2)我负：我负：1=-20。(3)平局：平局：1=0，2=0。博弈问题对人工智能研究提出了严峻的挑战。例如，如博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和博弈知识等。何表示博弈问题的状
43、态、博弈过程和博弈知识等。2023/3/2362n所谓所谓“全信息全信息”，是指博弈双方都了解当前的，是指博弈双方都了解当前的格局及过去的历史。格局及过去的历史。n所谓所谓“非偶然非偶然，是指博弈双方都可，是指博弈双方都可根据得失大根据得失大小进行分析小进行分析，选取，选取我方赢得最大，敌方赢得最我方赢得最大，敌方赢得最小的对策小的对策，而不是偶然的随机对策。，而不是偶然的随机对策。2023/3/2363（1 1）对垒的双方）对垒的双方MAXMAX和和MINMIN轮流采取行动，博轮流采取行动，博弈的结果只能有弈的结果只能有3 3种情况：种情况：MAXMAX胜、胜、MINMIN败；败；MAXMA
44、X败，败，MINMIN胜；和局。胜；和局。（2 2）在对垒过程中，任何一方都了解当前的）在对垒过程中，任何一方都了解当前的格局和过去的历史。格局和过去的历史。（3 3）任何一方在采取行动前都要根据当前的）任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选择对自己最实际情况，进行得失分析，选择对自己最为有利而对对方最不利的对策，在不存在为有利而对对方最不利的对策，在不存在“碰运气碰运气”的偶然因素，即双方都很理智的偶然因素，即双方都很理智地决定自己的行动。地决定自己的行动。这类博弈如一字棋、象棋、围棋等。博弈的特点博弈的特点博弈的特点博弈的特点 2023/3/2364o另外一种博弈是机
45、遇性博弈，是指不可预测另外一种博弈是机遇性博弈，是指不可预测性的博弈，如掷硬币游戏等。性的博弈，如掷硬币游戏等。2023/3/2365例：例：o假设有七枚钱币，任一选手只能将已分好的假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆一堆钱币分成两堆个数不等个数不等的钱币，两位选的钱币，两位选手轮流进行，直到每一堆都只有一个或两个手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个选手遇到不能再钱币，不能再分为止，哪个选手遇到不能再分的情况，则为输。分的情况，则为输。2023/3/2366o用数字序列加上一个说明表示一个状态，其中数字用数字序列加上一个说明表示一个状态，其中数字表示
46、不同堆中钱币的个数，说明表示下一步由谁来表示不同堆中钱币的个数，说明表示下一步由谁来分，分，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在它在它的基础上再作符合要求的划分。的基础上再作符合要求的划分。2023/3/2367o下图已将双方可能的方案完全
47、表示出来了，无下图已将双方可能的方案完全表示出来了，无论论MINMIN开始时怎么走法，开始时怎么走法，MAXMAX总可以获胜，取胜总可以获胜，取胜的策略用双线箭头表示。的策略用双线箭头表示。2023/3/2368o实际的情况没有这么简单，任何一种棋都不可实际的情况没有这么简单，任何一种棋都不可能将所有情况列尽，因此，只能模拟人能将所有情况列尽，因此，只能模拟人“向前向前看几步看几步”，然后做出决策，决定自己走哪一步，然后做出决策，决定自己走哪一步最有利。最有利。o只能给出几层走法，然后按照一定的估算方法，只能给出几层走法，然后按照一定的估算方法，决定走哪一步棋。决定走哪一步棋。o在双人完备信息
48、博弈过程中，双方都希望自己在双人完备信息博弈过程中，双方都希望自己能够获胜。因此当一方走步时，能够获胜。因此当一方走步时，都是选择对自都是选择对自己最有利，而对对方最不利的走法己最有利，而对对方最不利的走法。2023/3/2369o假设博弈双方为假设博弈双方为MAXMAX和和MINMIN。在博弈的每一步，可。在博弈的每一步，可供他们选择的方案都有很多种。供他们选择的方案都有很多种。o从从MAXMAX的观点看，可供自己选择的方案之间是的观点看，可供自己选择的方案之间是“或或”的关系，原因是主动权在自己手里，选择哪个的关系，原因是主动权在自己手里，选择哪个方案完全由自己决定，可供自己选择的方案之间
49、方案完全由自己决定，可供自己选择的方案之间是是“或或”的关系，而对那些可供的关系，而对那些可供MINMIN选择的方案之选择的方案之间是间是“与与”的关系，这是因为主动权在的关系，这是因为主动权在MINMIN手中，手中，任何一个方案都可能被任何一个方案都可能被MINMIN选中，选中，MAXMAX必须防止那必须防止那种对自己最不利的情况出现。种对自己最不利的情况出现。2023/3/2370o下图是把双人博弈过程用图的形式表示出来，下图是把双人博弈过程用图的形式表示出来，这样就可以得到一棵这样就可以得到一棵AND-ORAND-OR树，这种树，这种AND-ORAND-OR树称为博弈树。树称为博弈树。o
50、在博弈树中，那些下一步该在博弈树中，那些下一步该MAXMAX走的节点称走的节点称为为MAXMAX节点，而下一步该节点，而下一步该MINMIN走的节点称为走的节点称为MINMIN节点。节点。2023/3/2371o下图下图 所示是向前看两步，共四层的博弈树，用所示是向前看两步，共四层的博弈树，用表示表示MAXMAX，用用表示表示MINMIN，端节点上的数字表示它对应的估价函数的值。，端节点上的数字表示它对应的估价函数的值。在在MINMIN处用圆弧连接，用处用圆弧连接，用0 0表示其子节点取估值最小的格局。表示其子节点取估值最小的格局。图中节点处的数字，在端节点是估价函数的值，称它为静态值，在MI