人工智能基础之搜索技术.pptx

合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室1/79目录o第一章第一章绪论o第二章第二章知知识表示表示 o第三章搜索技第三章搜索技术o第四章推理技第四章推理技术o第五章机器学第五章机器学习 o第六章第六章专家系家系统 o第七章自第七章自动规划系划系统o第八章第八章 自然自然语言理解言理解o第九章第九章 智能控制智能控制o第十章第十章 人工智能程序人工智能程序设计合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室2/793.1 盲目搜索盲目搜索：即盲目搜索：即 无信息搜索无信息搜索 宽度度优先与深度先与深度优先先3.1.1 图搜索策略搜索策略 图搜索策略可看作一种在搜索策略可看作一种在图中中寻找路径的方法。初始找路径的方法。初始节点点和目和目标节点分点分别代表初始数据代表初始数据库和和满足足终止条件的数据止条件的数据库。求。求得把一个数据得把一个数据库变换为另一数据另一数据库的的规则序列序列问题就等价于求就等价于求得得图中的一条路径中的一条路径问题。研究。研究图搜索的一般策略，能搜索的一般策略，能够给出出图搜索搜索过程的一般步程的一般步骤。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室3/793.1 盲目搜索3.1.1 图搜索策略搜索策略 例例3.1 从王某家族的四代中找王从王某家族的四代中找王A的后代且其寿命的后代且其寿命为X的人的人 A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室4/793.1 盲目搜索3.1.1 图搜索策略搜索策略1.图搜索搜索(GRAPHSEARCH)的一般的一般过程程(1)建立一个只含有起始建立一个只含有起始节点点S的搜索的搜索图G，把，把S放到一个叫做放到一个叫做OPEN的未的未扩展展节点表中。点表中。(2)建立一个叫做建立一个叫做CLOSED的已的已扩展展节点表，其初始点表，其初始为空表。空表。(3)LOOP：若：若OPEN表是空表，表是空表，则失失败退出。退出。(4)选择OPEN表上的第一个表上的第一个节点，把它从点，把它从OPEN表移出并放表移出并放进CLOSED表中。称此表中。称此节点点为节点点n。(5)若若n为一目一目标节点，点，则有解并成功退出，此解是追踪有解并成功退出，此解是追踪图G中沿中沿着指着指针从从n到到S这条路径而得到的条路径而得到的(指指针将在第将在第7步中步中设置置)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室5/793.1 盲目搜索3.1.1 图搜索策略搜索策略1.图搜索搜索(GRAPHSEARCH)的一般的一般过程程(6)扩展展节点点n，同，同时生成不是生成不是n的祖先的那些后的祖先的那些后继节点的集合点的集合M。把。把M的的这些成些成员作作为n的后的后继节点添入点添入图G中。中。(7)对那些未曾在那些未曾在G中出中出现过的的(既未曾在既未曾在OPEN表上或表上或CLOSED表上出表上出现过的的)M成成员设置一个通向置一个通向n的指的指针。把。把M的的这些成些成员加加进OPEN表。表。对已已经在在OPEN或或CLOSED表上的每表上的每一个一个M成成员，确定是否需要更改通到，确定是否需要更改通到n的指的指针方向。方向。对已在已在CLOSED表上的每个表上的每个M成成员，确定是否需要更改，确定是否需要更改图G中通向它中通向它的每个后裔的每个后裔节点的指点的指针方向。方向。(8)按某一任意方式或按某个探按某一任意方式或按某个探试值，重排，重排OPEN表。表。(9)GO LOOP。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室6/793.1 盲目搜索节点节点父辈节点父辈节点3.1.1 图搜索策略搜索策略2.图搜索算法的几个重要名搜索算法的几个重要名词（1）OPEN表与表与CLOSE表表 OPEN表表 CLOSED表表编号编号节点节点父辈节点父辈节点合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室7/793.1 盲目搜索3.1.1 图搜索策略搜索策略3.搜索搜索图与搜索与搜索树搜索搜索过程框程框图开 始初始化：S放入OPEN表，CLOES表置空,n=1OPEN表中的第一个结点 n移至CLOSE表若n 的后继未曾在搜索图 G中出现，则将其放入OPEN表的末端，并提供返回结点 n的指针,置n=n+1根据后继结点在搜索图 G中的出现情况修改指针方向依某种准则重新排序 OPEN表失败成功NYNOPEN为空表NULL？n=目标结点D吗?Y合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室8/793.1 盲目搜索3.1.1 图搜索策略搜索策略4.图搜索方法分析：搜索方法分析：图搜索搜索过程的第程的第8步步对OPEN表上的表上的节点点进行排序，以便能行排序，以便能够从从中中选出一个出一个“最好最好”的的节点作点作为第第4步步扩展用。展用。这种排序可以种排序可以是任意的即盲目的是任意的即盲目的(属于盲目搜索属于盲目搜索)，也可以用以后要，也可以用以后要讨论的各的各种启种启发思想或其它准思想或其它准则为依据依据(属于启属于启发式搜索式搜索)。每当被。每当被选作作扩展的展的节点点为目目标节点点时，这一一过程就宣告成功程就宣告成功结束。束。这时，能能够重重现从起始从起始节点到目点到目标节点的点的这条成功路径，其条成功路径，其办法是从法是从目目标节点按指点按指针向向S返回追溯。当搜索返回追溯。当搜索树不再剩有未被不再剩有未被扩展的展的端端节点点时，过程就以失程就以失败告告终(某些某些节点最点最终可能没有后可能没有后继节点，所以点，所以OPEN表可能最后表可能最后变成空表成空表)。在失。在失败终止的情况下，止的情况下，从起始从起始节点出点出发，一定达不到目，一定达不到目标节点。点。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室9/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索 定定义3.1 如果搜索是以接近起始如果搜索是以接近起始节点的程度依次点的程度依次扩展展节点的，点的，那么那么这种搜索就叫做种搜索就叫做宽度度优先搜索（先搜索（breadth-first search)合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室10/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索宽度度优先搜索算法先搜索算法(1)把起始把起始节点放到点放到OPEN表中表中(如果如果该起始起始节点点为一目一目标节点，点，则求得一个解答求得一个解答)。(2)如果如果OPEN是个空表，是个空表，则没有解，失没有解，失败退出；否退出；否则继续。(3)把第一个把第一个节点点(节点点n)从从OPEN表移出，并把它放入表移出，并把它放入CLOSED的的扩展展节点表中。点表中。(4)扩展展节点点n。如果没有后。如果没有后继节点，点，则转向上述第向上述第(2)步。步。(5)把把n的所有后的所有后继节点放到点放到OPEN表的末端，并提供从表的末端，并提供从这些后些后继节点回到点回到n的指的指针。(6)如果如果n的任一个后的任一个后继节点是个目点是个目标节点，点，则找到一个解答，找到一个解答，成功退出；否成功退出；否则转向第向第(2)步。步。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室11/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索 例例3.2 八数八数码问题操操作作规定定:允允许空空格格四四周周上上、下下、左左、右右的的数数码块移移入入空空格格中，不中，不许斜方向移斜方向移动，不，不许返回先返回先辈结点。点。初始布局初始布局S和目和目标状状态D如下如下图所示：所示：合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室12/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索 例例3.2 八数八数码问题合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室13/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索深度深度优先算法步先算法步骤：(1)初始初始结点点S放到未放到未扩展展节点点OPEN中；中；(2)若若OPEN为空，空，则搜索失搜索失败，问题无解；无解；(3)弹出出OPEN表中最表中最顶端端结点放到点放到CLOSE表中，并表中，并给出出顺序序编号号n；(4)若若n为目目标结点点D，则搜索成功，搜索成功，问题有解；有解；(5)若若n无子无子结点，点，转(2)；(6)扩展展n结点，将其所有子点，将其所有子结点配上返回点配上返回n的指的指针，并按，并按次序次序压入入OPEN堆堆栈，转(2)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室14/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室15/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索有界深度有界深度优先搜索先搜索：引入搜索深度限制引入搜索深度限制值d，使深度使深度优先搜索先搜索过程具有完程具有完备性性 。设定搜索深度限制定搜索深度限制d=5，问题同深度同深度优先算法中的八数先算法中的八数码问题(2)(2)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室16/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室17/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索有界深度有界深度优先算法步先算法步骤：(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(n)=dd(n)=d，则转(2)(2)；(6)(6)若若n n无子无子结点，即不可点，即不可扩展，展，转(2)(2)；(7)(7)扩展展结点点n n，将其所有子，将其所有子结点配上返回点配上返回n n的指的指针，并，并压入入OPEN堆堆栈，转(2)(2)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室18/793.1 盲目搜索3.1.4 等代价搜索等代价搜索 宽度度优先搜索可被推广用来解决先搜索可被推广用来解决寻找从起始状找从起始状态至目至目标状状态的具有最小代价的路径的具有最小代价的路径问题，这种推广了的种推广了的宽度度优先搜索算法先搜索算法叫做等代价搜索算法叫做等代价搜索算法。等代价搜索中的几个等代价搜索中的几个记号号 起始起始节点点记为S；从从节点点i到它的后到它的后继节点点j的的连接弧接弧线代价代价记为c(i，j)；起始起始节点点S到任一到任一节点点i的路径代价的路径代价记为g(i)。如果所有的如果所有的连接弧接弧线具有相等的代价，那么等代价算法就具有相等的代价，那么等代价算法就简化化为宽度度优先搜索算法先搜索算法。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室19/793.2 启发式搜索盲目搜索的不足：效率低，耗盲目搜索的不足：效率低，耗费空空间与与时间。启启发式搜索：利用式搜索：利用问题域特性的信息（启域特性的信息（启发信息）信息）进行搜索。行搜索。3.2.1 启启发式搜索策略式搜索策略启启发式信息按用途分式信息按用途分为三种：三种：（1）用于确定要）用于确定要扩展的下一个展的下一个节点，避免盲目点，避免盲目扩展。展。（2）在）在扩展一个展一个节点的点的过程中，用于确定要生成哪一个或哪程中，用于确定要生成哪一个或哪几个后几个后继节点，避免盲目生成所有可能点，避免盲目生成所有可能节点。点。（3）用于确定某些）用于确定某些应该从搜索从搜索树中抛弃或修剪得中抛弃或修剪得节点。点。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室20/793.2 启发式搜索 有序搜索（有序搜索（ordered search）：利用第一种启）：利用第一种启发信息，信息，总是是选择“最有希望最有希望”的的节点作点作为下一个被下一个被扩展的展的节点。点。估价函数（估价函数（evaluation function)：估算：估算节点点“希望希望”的量度，的量度，这种量度叫做估价函数。种量度叫做估价函数。建立估价函数的一般方法：建立估价函数的一般方法：试图确定一个确定一个处在最佳路径上在最佳路径上的的节点的概率；提出任意点的概率；提出任意节点与目点与目标集之集之间的距离量度或差的距离量度或差别量度；或者在棋量度；或者在棋盘式的博弈和式的博弈和难题中根据棋局的某些特点来决中根据棋局的某些特点来决定棋局的得分数。定棋局的得分数。这些特点被些特点被认为与向目与向目标节点前点前进一步的希一步的希望程度有关。望程度有关。f(n)表示表示节点点n的估价函数的估价函数值 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室21/793.2 启发式搜索3.2.2 有序搜索有序搜索 用估价函数用估价函数f来排列来排列GRAPHSEARCH第第8步中步中OPEN表上表上的的节点。点。应用某个算法用某个算法(例如等代价算法例如等代价算法)选择OPEN表上具有表上具有最小最小f值的的节点作点作为下一个要下一个要扩展的展的节点。点。这种搜索方法叫做种搜索方法叫做有序搜索有序搜索或或最佳最佳优先搜索先搜索(best-first search)，而其算法就叫做，而其算法就叫做有序搜索算法有序搜索算法或或最佳最佳优先算法先算法。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室22/793.2 启发式搜索3.2.2 有序搜索有序搜索有序状有序状态空空间搜索算法：搜索算法：(1)把起始把起始节点点S放到放到OPEN表中，表中，计算算f(S)并把其并把其值与与节点点S联系起来。系起来。(2)如果如果OPEN是个空表，是个空表，则失失败退出，无解。退出，无解。(3)从从OPEN表中表中选择一个一个f值最小的最小的节点点i。结果有几个果有几个节点点合格，当其中有一个合格，当其中有一个为目目标节点点时，则选择此目此目标节点，否点，否则就就选择其中任一个其中任一个节点作点作为节点点i。(4)把把节点点i从从OPEN表中移出，并把它放入表中移出，并把它放入CLOSED的的扩展展节点表中。点表中。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室23/793.2 启发式搜索3.2.2 有序搜索有序搜索(5)如果如果i是个目是个目标节点，点，则成功退出，求得一个解。成功退出，求得一个解。(6)扩展展节点点i，生成其全部后，生成其全部后继节点。点。对于于i的每一个后的每一个后继节点点j：(a)计算算f(j)。(b)如果如果j既不在既不在OPEN表中，又不在表中，又不在CLOSED表中，表中，则用用估价函数估价函数f把它添入把它添入OPEN表。从表。从j加一指向其父加一指向其父辈节点点i的指的指针，以便一旦找到目以便一旦找到目标节点点时记住一个解答路径。住一个解答路径。(c)如果如果j已在已在OPEN表上或表上或CLOSED表上，表上，则比比较刚刚对j计算算过的的f值和前面和前面计算算过的的该节点在表中的点在表中的f值。如果新的。如果新的f值较小，小，则合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室24/793.2 启发式搜索3.2.2 有序搜索有序搜索(i)以此新以此新值取代旧取代旧值。(ii)从从j指向指向i，而不是指向它的父，而不是指向它的父辈节点。点。(iii)如果如果节点点j在在CLOSED表中，表中，则把它移回把它移回OPEN表。表。(7)转向向(2)，即，即GO TO(2)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室25/793.2 启发式搜索3.2.2 有序搜索有序搜索开始开始把把S放入放入OPEN表表OPEN为空表？为空表？失败失败选取选取OPEN表中表中f值最小值最小的节点的节点i，放入，放入CLOSED表表i=Sg？成功成功是是是是扩展扩展i得后继节点得后继节点j，计算，计算f(j)，提，提供返回供返回i的指针，利用的指针，利用f(j)对对OPEN表重新排序调整父子关系及指针表重新排序调整父子关系及指针合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室26/793.2 启发式搜索3.2.2 有序搜索有序搜索宽度度优先搜索、等代价搜索和深度先搜索、等代价搜索和深度优先搜索先搜索统统是有序是有序搜索技搜索技术的特例。的特例。对于于宽度度优先搜索，先搜索，选择f(i)作作为节点点i的深的深度。度。对于等代价搜索，于等代价搜索，f(i)是从起始是从起始节点至点至节点点i这段路径的代段路径的代价。价。有序搜索的有效性直接取决于有序搜索的有效性直接取决于f的的选择，如果，如果选择的的f不不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么没有适用的准确的希望量度，那么f的的选择将涉及两个方面的将涉及两个方面的内容：一方面是一个内容：一方面是一个时间和空和空间之之间的折衷方案；另一方面是的折衷方案；另一方面是保保证有一个最有一个最优的解或任意解。的解或任意解。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室27/793.2 启发式搜索3.2.2 有序搜索有序搜索例例3.4：八数：八数码难题,采用了采用了简单的估价函数的估价函数 f(n)=d(n)+W(n)其中：其中：d(n)是搜索是搜索树中中节点点n的深度；的深度；W(n)用来用来计算算对应于于节点点n的数据的数据库中中错放的棋子个数。因此，起始放的棋子个数。因此，起始节点棋局点棋局的的f值等于等于0+4=4。2 8 31 6 475合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室28/793.2 启发式搜索3.2.2 有序搜索有序搜索2 8 31 6 4752 8 31 6 47 52 8 3147 6 52 8 31 6 47 52 8 31 47 6 5231 8 47 6 52 8 31 47 6 58 32 1 47 6 52 8 37 1 46 52 31 8 47 6 52 3 31 8 47 6 51 2 38 47 6 51 2 3847 6 51 2 37 8 46 5合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室29/793.2 启发式搜索3.2.3 A*算法算法A*算法是一种有序搜索算法，其特点在于算法是一种有序搜索算法，其特点在于对估价函数的定估价函数的定义上。上。1.A*算法的估价函数算法的估价函数 k(ni，nj)：表示任意两个：表示任意两个节点点ni和和nj之之间最小代价路径的最小代价路径的实际代价代价(对于两于两节点点间没有通路的没有通路的节点，函数点，函数k没有定没有定义)。k(n,ti)：从：从节点点n到某个具体的目到某个具体的目标节点点ti，某一条最小代，某一条最小代价路径的代价。价路径的代价。h*(n)：表示整个目：表示整个目标节点集合点集合ti上所有上所有k(n,ti)中最小的中最小的一个，因此，一个，因此，h*(n)就是从就是从n到目到目标节点最小代价路径的代价，点最小代价路径的代价，而且从而且从n到目到目标节点能点能够获得得h*(n)的任一路径就是一条从的任一路径就是一条从n到到某个目某个目标节点的最佳路径点的最佳路径(对于任何不能到达目于任何不能到达目标节点的点的节点点n，函数，函数h*没有定没有定义)。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室30/793.2 启发式搜索3.2.3 A*算法算法定定义g*为g*(n)=k(S,n)从已知起始从已知起始节点点S到任意到任意节点点n的一条最佳路径代价。的一条最佳路径代价。定定义函数函数f*，f*(n)=g*(n)+h*(n)使得在任一使得在任一节点点n上其函数上其函数值f*(n)就是从就是从节点点S到到节点点n的一条的一条最佳路径的最佳路径的实际代价加上从代价加上从节点点n到某目到某目标节点的一条最佳路点的一条最佳路径的代价之和。径的代价之和。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室31/793.2 启发式搜索3.2.3 A*算法算法 希望估价函数希望估价函数f是是f*的一个估的一个估计，此估，此估计可由下式可由下式给出：出：f(n)=g(n)+h(n)其中：其中：g是是g*的估的估计；h是是h*的估的估计。对于于g(n)：一个明：一个明显的的选择就是搜索就是搜索树中从中从S到到n这段路径的段路径的代价，代价，这一代价可以由从一代价可以由从n到到S寻找指找指针时，把所遇到的各段弧，把所遇到的各段弧线的代价加起来的代价加起来给出出(这条路径就是到目前条路径就是到目前为止用搜索算法找到止用搜索算法找到的从的从S到到n的最小代价路径的最小代价路径)。这个定个定义包含了包含了g(n)g*(n)。h(n)：对 h*(n)的估的估计，依，依赖于有关于有关问题的的领域的启域的启发信息。信息。这种信息可能与八数种信息可能与八数码难题中的函数中的函数W(n)所用的那种信息相似。所用的那种信息相似。把把h叫做启叫做启发函数。函数。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室32/793.2 启发式搜索3.2.3 A*算法算法2.A算法和算法和A*算法的定算法的定义定定义3.3 在在GRAPHSEARCH过程中，如果第程中，如果第8步的重排步的重排OPEN表是依据表是依据f(x)=g(x)+h(x)进行的，行的，则称称该过程程为A算法。算法。定定义3.4 在在A算法中，如果算法中，如果对所有的所有的x存在存在h(x)h*(x),则称称h(x)为h*(x)的下界，它表示某种偏于保守的估的下界，它表示某种偏于保守的估计。定定义3.5 采用采用h*(x)的下界的下界h(x)为启启发函数的函数的A算法，称算法，称为A*算算法。当法。当h=0时，A*算法就算法就变为有序搜索算法。有序搜索算法。A A算法和算法和A*A*搜索算法的目标有所不同：搜索算法的目标有所不同：A A搜索算法虽然希搜索算法虽然希望能找到问题的最优解，但主要追求的是求解效率；而望能找到问题的最优解，但主要追求的是求解效率；而A*A*搜索搜索算法直接目标就在于要找到问题的最优解及其解的路径，即便算法直接目标就在于要找到问题的最优解及其解的路径，即便搜索效率有所降低也在所不惜。搜索效率有所降低也在所不惜。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室33/793.2 启发式搜索3.2.3 A*算法算法开始开始把把S放入放入OPEN表表,记记f=hOPEN为空表？为空表？失败失败选取选取OPEN表中未设置过的具有最小表中未设置过的具有最小f值值的节点的节点BESTNODE，放入，放入CLOSED表表BESTNODE=Sg？成功成功是是是是扩展扩展BESTNODE，产生后继节点，产生后继节点SUVVESSOR建立从建立从SUCCESSOR返回返回BESTNODE的指针的指针计算计算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR)SUCCESSOROPEN？否否是是合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室34/793.2 启发式搜索3.2.3 A*算法算法把把SECCESSOR放入放入OPEN表，表，加入加入BESTNODE的后裔表的后裔表g(SUCCESSOR)g(OLD)？否否重新确定重新确定OLD的父辈节点为的父辈节点为BESTNODE，并修正父辈节点的并修正父辈节点的g值和值和f值，记下值，记下g(OLD)SUCCESSORCLOSED？否否是是SECCESSOR=OLD，把它添到，把它添到BESTNODE的后继节点表中的后继节点表中是是否否计算计算f值值合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室35/793.3 博弈树搜索3.3.1 博弈概述博弈概述 何何何何谓谓博弈？博弈？博弈？博弈？博弈就是下棋、打牌、博弈就是下棋、打牌、竞技、技、战争等一争等一类竞争争性智能活性智能活动。“二人零和非偶然性全信息二人零和非偶然性全信息”博弈博弈 （1 1）二人零和：）二人零和：）二人零和：）二人零和：对垒的的MAX、MIN双方双方轮流采取行流采取行动，博，博弈的弈的结果只有三种情况：果只有三种情况：MAX方方胜，MIN方方胜，和局。，和局。（2 2）全信息：）全信息：）全信息：）全信息：在在对垒过程中，任何一方都了解当前格局及程中，任何一方都了解当前格局及过去的去的历史。史。（3 3）非偶然性：）非偶然性：）非偶然性：）非偶然性：任何一方在采取行任何一方在采取行动前都要根据当前的前都要根据当前的实际情况，情况，进行得失分析，行得失分析，选取取对自己最自己最为有利而有利而对对方最方最为不利不利的的对策，不存在策，不存在“碰运气碰运气”，“侥幸幸”及及“偶然失偶然失误”等随机等随机因素。因素。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室36/793.3 博弈树搜索3.3.1 博弈概述博弈概述 参加博弈的各方都希望己方取得参加博弈的各方都希望己方取得胜利。因此，当一方面利。因此，当一方面临多多个行个行动方案方案选择时，博弈的各方博弈的各方总是要挑是要挑选对自己最自己最为有利而有利而对对方最不利的那个行方最不利的那个行动方案。方案。假如假如MAXMAX方的目方的目方的目方的目标标：尽可能使自己达到最大（或最高）的分尽可能使自己达到最大（或最高）的分数分枝数分枝节点，点，可用可用“或或或或”关系来描述，称之关系来描述，称之为MAX方方节点；点；而当而当轮到到MIN方行方行动时，MINMIN方的目方的目方的目方的目标标：尽可能使尽可能使MIN方方获得最小（或最低）的分数分枝得最小（或最低）的分数分枝节点，点，这对MIN方来方来说，这些行些行动方案或分数分枝方案或分数分枝节点之点之间，可以用，可以用“与与与与”关系来描述，是由关系来描述，是由MINMIN方方方方自主自主进行控制的，故又称之行控制的，故又称之为MIN节点。点。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室37/793.3 博弈树搜索3.3.1 博弈概述博弈概述 把上述双方逐把上述双方逐层交替的博弈交替的博弈过程用与程用与/或或树（图）描述表达）描述表达出来，就得到了一棵具有出来，就得到了一棵具有“与与/或或”节点交替出点交替出现的博弈的博弈树。博弈博弈树有如下特点：有如下特点：（1）博弈的初始格局是初始）博弈的初始格局是初始节点。点。（2）在博弈）在博弈树中，由于中，由于双方双方双方双方轮轮流地流地流地流地扩扩展展展展节节点，点，点，点，“或或或或”节节点和点和点和点和“与与与与”节节点逐点逐点逐点逐层层交替出交替出交替出交替出现现。如果自己一方如果自己一方扩展的展的节点之点之间是是“或或”关系，关系，则对方方扩展的展的节点之点之间是是“与与”关系。关系。（3）把本方）把本方获胜的的终局定局定义为本原本原问题，相，相应最最优搜索路径搜索路径上的上的节点是可解点是可解节点，而所有使点，而所有使对方方获胜的的终局和属于局和属于对方最方最优搜索路径上的搜索路径上的节点点则是不可解是不可解节点。此外，所有其它的点。此外，所有其它的节点点则是具有是具有风险的中的中间节点。点。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室38/793.3 博弈树搜索3.3.2 极小极大分析法极小极大分析法 在二人博弈在二人博弈过程中，最直程中，最直观而可靠的常用分析方法就是极而可靠的常用分析方法就是极小极大化搜索法。其主要描述思想和算法：小极大化搜索法。其主要描述思想和算法：（1）设博弈的一方博弈的一方为MAX方，其目方，其目标是尽可能使自己得到是尽可能使自己得到最高分；另一方最高分；另一方为MIN方方,其目其目标是尽可能是尽可能给MAX方送出最低方送出最低分。所分。所谓极小极大化分析法是一种要极小极大化分析法是一种要轮流流为每一方每一方寻找一个最找一个最优行行动方案的方法。在方案的方法。在图中，方框形状中，方框形状“”表示是表示是MAX方方控制的或控制的或节点；点；圆形框形状形框形状“”表示表示MIN方控制与方控制与节点。点。（2）考）考虑每一方案每一方案实施后施后对方可能采取的所有行方可能采取的所有行动，并，并为其其计算可能的得分；算可能的得分；（3）为计算得分，需要根据算得分，需要根据问题的特性信息定的特性信息定义一个估价一个估价函数，用来估算当前博弈函数，用来估算当前博弈树所有端所有端节点的得分。此点的得分。此时估算出来估算出来的得分称的得分称为的静的静态估估值。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室39/793.3 博弈树搜索3.3.2极小极大分析法极小极大分析法 （4）当端）当端节点的估点的估值计算出来后，再推算父算出来后，再推算父辈节点的等分，点的等分，推算方法是：推算方法是：对“或或”节点，点，选择其子其子节点中最大的得分作点中最大的得分作为父父辈节点的得分（点的得分（选择对自己最有利的方案）；自己最有利的方案）；对“与与”节点，点，选其子其子节点中一个最小的得分作点中一个最小的得分作为作作为父父辈节点的得分（立足点的得分（立足于最坏的情况）。于最坏的情况）。这样计算出的父算出的父辈节点的等分称点的等分称为倒推倒推值。（5）如果一个行）如果一个行动方案能方案能获得得较大的倒推大的倒推值，则它就是当前它就是当前最好的行最好的行动方案。方案。存存储受限受限问题：先生成一定深度的博弈：先生成一定深度的博弈树，进行极小极大分行极小极大分析，找出当前的最好的行析，找出当前的最好的行动方案。然后再已方案。然后再已选定的分支上再定的分支上再扩展一定的深度，如此反复。展一定的深度，如此反复。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室40/793.3.2极小极大分析法极小极大分析法 4 -1 -1 8 1 2 -5 0 -4 -9 -14 -1 -1 8 1 2 -5 0 -4 -9 -1 5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6-4 10 9-1 12 5 5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6-4 10 9-1 12 5 MAX-MIN博弈树的倒推值计算博弈树的倒推值计算h h(S0)=S0)=？4 8 2 0 -1 4 8 2 0 -1 4 -14 -13.3 博弈树搜索合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室41/793.3 博弈树搜索3.3.3-剪枝技剪枝技术 基本思想：基本思想：边生成博弈生成博弈树边估算各估算各节点的倒推点的倒推值，并且根，并且根据据评估出的倒推估出的倒推值范范围，及，及时停止停止扩展那些已无必要再展那些已无必要再扩展的展的子子节点。点。具体剪枝方法：具体剪枝方法：（1）对于一个于一个“与与”节点点MIN，若能估，若能估计出其倒推出其倒推值上界上界，并且并且这个个值不大于不大于MIN的父的父辈节点（一定是点（一定是“或或”节点）的估点）的估计倒推倒推值的下界的下界，即，即，则就不必要再就不必要再扩展展该MIN节点的其点的其余子余子节点了。点了。这一一过程称程称为剪枝。剪枝。（2）对于一个于一个“或或”节点点MAX，若能估，若能估计出其倒推出其倒推值下界下界，并且并且这个个 值不小于不小于MAX的父的父辈节点（一定是点（一定是“与与”节点）的点）的估估计倒推倒推值的上界的上界，即，即，则就不必要再就不必要再扩展展该MAX节点点的其余子的其余子节点了。点了。这一一过程称程称为 剪枝。剪枝。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室42/793.3 博弈树搜索3.3.3-剪枝技剪枝技术 从算法中看到：从算法中看到：（1）MAX节点（包括起始点（包括起始节点）的点）的值永不减少。永不减少。（2）MIN节点（包括起始点（包括起始节点）的点）的值永不增加。永不增加。在搜索期在搜索期间，和和 值的的计算如下：算如下：（1）一个）一个MAX节点的点的值等于其后等于其后继节点当前最大的最点当前最大的最终倒推倒推值。（2）一个）一个MIN节点的点的 值等于其后等于其后继节点当前最小的最点当前最小的最终倒推倒推值。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室43/793.3 博弈树搜索3.3.3-剪枝技剪枝技术例例3.5 一字棋搜索一字棋搜索树和和值计算算 估价函数估价函数g(p)定定义如下：如下：（1）若当前棋局）若当前棋局对任何一方都不是任何一方都不是获胜的，的，则 g(p)=(所有空格都放上所有空格都放上MAX的棋子之后的棋子之后3个棋子所个棋子所组成的行成的行列及列及对角角线的的总数）数）（所有空格都放上（所有空格都放上MIN的棋子之后的棋子之后3个个棋子所棋子所组成的行列及成的行列及对角角线的的总数）数）（2）若）若p是是MAX获胜，则 g(p)=+（3）若）若p是是MIN获胜，则 g(p)=-上上图中，中，g(p)=6-4=2，其中，其中表示表示MAX方，方，表示表示MIN方方合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室44/793.3.3-剪枝技剪枝技术3.3 博弈树搜索初始节点初始节点=-1ABC-1=-16-5=15-5=06-5=15-5=04-5=-15-6=-1合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室45/793.3.3-剪枝技剪枝技术3.3 博弈树搜索 4 -1 -1 8 1 2 -5 0 -4 -9 -14 -1 -1 8 1 2 -5 0 -4 -9 -1 5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6-4 10 9-1 12 5 5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6-4 10 9-1 12 5 MAX-MIN博弈树的倒推值计算博弈树的倒推值计算h h(S0)=S0)=？4 8 2 0 -1 4 8 2 0 -1 4 -14 -1合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室46/793.3.3-剪枝技剪枝技术3.3 博弈树搜索h h(S0)=S0)=？4 44 411113 33 311118 88 810108 82 22 2-5-5-5-52 22 24 44 4 4 4x x 5 55 5 4 4 博弈树的博弈树的-剪枝实现过程剪枝实现过程 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室47/793.3 博弈树搜索3.3.3-剪枝技剪枝技术 要要进行行-剪枝，必剪枝，必须至少使某一部分的搜索至少使某一部分的搜索树生生长到最大到最大深度，因深度，因为和和值必必须以端以端节点的静点的静态估估值为依据。因此采用依据。因此采用-剪