人工智能导论第二章搜索与问

人工智能导论第二章搜索与问第1页，共163页，2023年，2月20日，星期日第二章搜索、问题求解与博弈问题求解能力是人类智能的基本组成部分，研究并实现问题求解是人工智能的重要研究内容之一。知识（问题）的表示是问题求解的基础，两种普遍采用的问题表示方法：状态空间表示与或图表示搜索（优化）：在问题表示基础上，在合理的时间范围内，从问题所有可能的解中找到一个最优解或可行解，是问题求解中的核心技术。启发式搜索----人工智能的本质特征之一。计算机博弈涉及问题表示、搜索技术等AI核心问题，现有的计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。第2页，共163页，2023年，2月20日，星期日主要内容2.1搜索概述2.2问题求解2.2.1状态空间2.2.2与或图2.3搜索技术图搜索2.4机器博弈第3页，共163页，2023年，2月20日，星期日一些例子搭积木智力游戏：有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。类似问题：野人和传教士问题下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）第4页，共163页，2023年，2月20日，星期日2.1搜索概述人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程问题求解过程实际上就是一个搜索过程最优性和计算法复杂性是搜素中的一对矛盾，搜索必须考虑的三个问题：采用盲目搜索还是启发式搜索盲目搜索：不考虑问题本身的特性，通过遍历问题解的集合来寻找可行解或最优解。启发式搜索：利用与问题有关的启发式信息来确定搜索方向，以加快搜索过程。进行局部搜索还是全集搜索搜索可行解还是最优解第5页，共163页，2023年，2月20日，星期日2.1搜索概述评价一个搜索算法的因素：完备性：如果问题有解，一定能找到一个解最优性：如果问题存在最优解，则一定能找到这个最优解复杂性：时间和空间复杂性，在保证最优性和完备性的前提下，算法的复杂性越小越好。目前的搜索算法还不能同时满足以上三个要求。为了进行搜索，首先必须用某种形式把问题表示出来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程的两种常用方法。第6页，共163页，2023年，2月20日，星期日2.2问题求解状态空间表示法和与或图表示法不仅是问题表示的方法，也分别代表了两种问题求解的思路状态空间将问题求解所涉及的每个可能的步骤表示成一个状态，全部状态以及状态之间的所有转换构成一个以图的形式表示的状态空间。问题的求解过程是在状态空间中搜索一条最优的或可行的从初始状态到目标状态的路径的过程。与或图表示法的基础是问题归约，通过一系列分解或变换，将复杂问题逐步转化为比较简单的问题，直至可以直接求解的本原问题。与或图的求解过程是在与或图中搜索一个将原始问题变换为简单问题在变换为本原问题的、最优的或可行的归约步骤的过程。第7页，共163页，2023年，2月20日，星期日2.2.1状态空间表示法状态空间表示法是用“状态”和“算子”来表示问题的一种方法状态：用来描述问题求解过程中不同时刻的状况算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解第8页，共163页，2023年，2月20日，星期日2.2.1状态空间表示法状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK(SK0,SK1,…)当给每一分量以确定的值时，就得到一个具体的状态算子引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示:(S,F,C,I,G)S:所有状态构成的集合F:用于状态转换的算子的集合C:状态转换代价的聚合I:初始状态的集合G:目标状态的集合第9页，共163页，2023年，2月20日，星期日例:二阶HanoiTower（梵塔）问题设有三根柱子，在1号柱于上穿有A、B两个盘片，盘A小于盘B，盘A位于盘B的上面。要求把这两个盘片全部移到另一根柱子上，而且规定每次只能移动一片，任何时刻都不能使盘B位于盘A的上面。设SK=(SK0,SK1)表示问题的状态，SK0

表示盘片A所在的柱号，SK1

表示盘片B所在的柱号全部可能的状态:S0=(1,1),S1=(1,2),S2=(1,3),S3=(2,1),S4=(2,2),S5=(2,3),S6=(3,1),S7=(3,2),S8=(3,3).问题的初始状态集合S={S0},目标集合为G={S4,S8}算子分别用A(i,j),B(i,j)表示A(i,j):盘片A从柱i移到柱j；B(i,j):盘片B从柱i移到柱j全部可能的算子：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2),B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)第10页，共163页，2023年，2月20日，星期日例:二阶HanoiTower（梵塔）问题9种状态，12种算子构成的状态空间转移图：第11页，共163页，2023年，2月20日，星期日2.2.1状态空间表示法总结：用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还安定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到问题的一个解：从初始状态到目标状态所用算符构成的序列。算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算特序列都可使问题从初始状态变到目标状态，这就得到了多个解。把使用算符最少的解称为最优解。对任何一个状态，可使用的算符可能不止一个，因而由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。第12页，共163页，2023年，2月20日，星期日2.2.1状态空间表示法基于状态空间表示的问题求解算法Step1：确定问题状态的计算机描述形式，将所有可能的状态表示出来，并确定其中的初始状态和目标状态。Step2：确定促使状态发生转换的操作，并在计算机中将其表示为相应的算符。Step3：以状态为顶点，状态之间所允许的操作为有向边，获得‘图’形式的状态空间。Step4：应用图搜索方法，在状态空间中搜索从初始状态到目标状态的最优路径或可行路径。第13页，共163页，2023年，2月20日，星期日例:三阶HanoiTower（梵塔）问题第14页，共163页，2023年，2月20日，星期日例:三阶HanoiTower（梵塔）问题第15页，共163页，2023年，2月20日，星期日例:三阶HanoiTower（梵塔）问题第16页，共163页，2023年，2月20日，星期日2.2.2与或图表示法也称为问题归约方法：把初始问题通过一系列交换最终变为一个子问题集合，而这些于问题的解可以直接得到，从而解答了初始问题。分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。问题的分解可以用图表示出来，称为与树。例如，把问题P分解为三个子问题P1、P2和P3，可以表示为下图：第17页，共163页，2023年，2月20日，星期日2.2.2与或图表示法等价变换：利用同构或同态的等价变换，把它变换成若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程也可用一个图表示出来，称为“或”树。与或树的结合称为与或图（树）。第18页，共163页，2023年，2月20日，星期日2.2.2与或图表示法本原问题：不能再分解或变换，而且直接可解的子问题称为本原问题。端节点与终止节点：在与／或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。可解节点：在与／或树今，满足下列条件之一的节点：1)它是一个终止节点。2)它是一个“或”节点，且其子节点至少有一个是可解节点。3)它是一个“与”节点，且其子节点全部是可解节点。不可解节点：上面三个条件全不满足的节点。解树：由可解节点所构成的，并且由这些可解节点可推出初始节点(它对应于原始问题)为可解节点的子树称为解树。在解树中’定包含初始节点。第19页，共163页，2023年，2月20日，星期日例:三阶HanoiTower（梵塔）问题设有A、B、C三个盘片以及三根柱子，三个盘片按从小到大的顺序穿在1号柱上，要求把它们全部移到3号柱上，而且每次只能移动一个盘片，任何时刻都不能把大的盘片压在小的盘片上面，如图所示。第20页，共163页，2023年，2月20日，星期日例:三阶HanoiTower（梵塔）问题分析：1)为了把三个盘片全部移到3号柱上，必须先把盘片C移到3号柱上。2)为了移盘片C，必须先把盘片A及B移到2号柱上。3)当把盘片C移到3号盘上后，就可把A、B从2号柱移到3号柱上，以完成问题的求解。把原问题分解为三个子问题：1)把盘片A及B移到2号柱的双盘片问题。2)把盘片C移到3号柱的单盘片问题。3)把盘片A及B移到3号柱的双盘片问题。其中，子问题1)与子问题3)又分别可分解为三个子问题第21页，共163页，2023年，2月20日，星期日例:三阶HanoiTower（梵塔）问题定义问题状态表示：设三元组(i,j,k)表示状态，其中i表示盘片C所在的柱号,j表示盘片B所在的柱号；k表示盘片A所在的柱号。初始问题可表示为：(1、1．1)(3，3，3)与／或树表示如图所示。(把图中7个终止节点(本原问题)按从左至右排列，得到了初始问题的解)第22页，共163页，2023年，2月20日，星期日2.2.2与或图表示法基于与或图表示的问题求解算法Step1：确定单个问题描述形式，可采用状态空间表示法。Step2：从原始问题开始，逐步进行分解和变换，直到本原问题，然后将全部分解和变换过程表示为与或图。Step3：从端顶点开始，逐步向上回溯，标注各顶点为可解或不可解顶点，直到标注原始顶点为可解顶点或不可解顶点为止Step4：当原始顶点被确定为可解顶点时，输出相应解图为问题的解。第23页，共163页，2023年，2月20日，星期日2.3搜索技术搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。例如，A.Newell(艾伦·纽厄尔)和H·A·Simon(西蒙)等人编写的LT(LogicTheorist)程序,J.Slagle写的符号积分程序SAINT,A·Newell和H·A·Simon写的GPS(GeneralProblemSolver)程序,H·Gelernter(格伦特尔)写的Geometrytheorem-provingmachine程序,R.Fikes(菲克斯)和N.Nilsson(尼尔逊)写的STRIPS(StanfordResearchInstituteProblemSolver)程序以及A.Samuel(塞缪尔)写的Chechers程序等,都使用了各种搜索技术。现在,搜索技术渗透在各种人工智能系统中,可以说没有哪一种人工智能的应用不用搜索方法,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。第24页，共163页，2023年，2月20日，星期日2.3搜索技术搜索问题是AI核心理论问题之一一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。第25页，共163页，2023年，2月20日，星期日2.3搜索技术搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。当所给定的问题用状态空间表示时,则求解过程可归结为对状态空间的搜索。当问题有解时,使用不同的搜索策略,找到解的搜索空间范围是有区别的。一般来说,对大空间问题,搜索策略是要解决组合爆炸的问题第26页，共163页，2023年，2月20日，星期日第27页，共163页，2023年，2月20日，星期日2.3搜索策略通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式:一种是不考虑给定问题所具有的特定知识,系统根据事先确定好的某种固定排序,依次调用规则或随机调用规则,这实际上是盲目搜索的方法,一般统称为无信息引导的搜索策略。另一种是考虑问题领域可应用的知识,动态地确定规则的排序,优先调用较合适的规则使用,这就是通常称为启发式搜索策略或有信息引导的搜索策略。第28页，共163页，2023年，2月20日，星期日AI领域的搜索方法(1)求任一解路的搜索策略回溯法(Backtracking)爬山法(HillClimbing)宽度优先法(Breadth-first)深度优先法(Depth-first)限定范围搜索法(BeamSearch)最佳优先法(Best-first)(2)求最佳解路的搜索策略大英博物馆法(BritishMuseum)分枝界限法(BranchandBound)动态规划法(DynamicProgramming)最佳图搜索法(A*)第29页，共163页，2023年，2月20日，星期日AI领域的搜索方法(3)求与或关系解图的搜索法一般与或图搜索法(AO*)

极小极大法(Minimax)剪枝法(Alpha-betaPruning)

启发式剪枝法(HeuristicPruning)第30页，共163页，2023年，2月20日，星期日搜索策略分类第31页，共163页，2023年，2月20日，星期日盲目搜索方法盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索。典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法第32页，共163页，2023年，2月20日，星期日回溯策略例：皇后问题在一个4×4的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获第33页，共163页，2023年，2月20日，星期日()第34页，共163页，2023年，2月20日，星期日()Q((1,1))第35页，共163页，2023年，2月20日，星期日()QQ((1,1))((1,1)(2,3))第36页，共163页，2023年，2月20日，星期日()Q((1,1))((1,1)(2,3))第37页，共163页，2023年，2月20日，星期日()QQ((1,1))((1,1)(2,3))((1,1)(2,4))第38页，共163页，2023年，2月20日，星期日()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))第39页，共163页，2023年，2月20日，星期日()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第40页，共163页，2023年，2月20日，星期日()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第41页，共163页，2023年，2月20日，星期日()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第42页，共163页，2023年，2月20日，星期日()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))第43页，共163页，2023年，2月20日，星期日()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))第44页，共163页，2023年，2月20日，星期日()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))第45页，共163页，2023年，2月20日，星期日()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))第46页，共163页，2023年，2月20日，星期日递归的思想从前有座山……从前有座山……

从前有座山……第47页，共163页，2023年，2月20日，星期日Fibonacci数列1202年，意大利家斐波那契在提出了一个关于兔子繁殖的问题：

如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在它出生後的第三个月里，又能开始生一对小兔，假定在

不发生死亡的情況下，由一对出生的小兔开始，50個月后会有多少对兔子？第48页，共163页，2023年，2月20日，星期日當n＞1時，Fn+2=Fn+1+Fn，而F0=F1=1。第49页，共163页，2023年，2月20日，星期日递归的思想（续）当前状态目标状态g第50页，共163页，2023年，2月20日，星期日回溯搜索算法

BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。第51页，共163页，2023年，2月20日，星期日回溯搜索算法递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);第52页，共163页，2023年，2月20日，星期日存在问题及解决办法问题：深度问题死循环问题解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径第53页，共163页，2023年，2月20日，星期日回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。第54页，共163页，2023年，2月20日，星期日回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);第55页，共163页，2023年，2月20日，星期日回溯搜索算法1（续）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);第56页，共163页，2023年，2月20日，星期日一些深入的问题失败原因分析、多步回溯QQ第57页，共163页，2023年，2月20日，星期日一些深入问题（续）回溯搜索中知识的利用 基本思想： 尽可能选取划去对角线上位置数最少的。QQQQ4334第58页，共163页，2023年，2月20日，星期日图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

第59页，共163页，2023年，2月20日，星期日一些基本概念节点深度： 根节点深度=0

其它节点深度=父节点深度+10123第60页，共163页，2023年，2月20日，星期日一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。第61页，共163页，2023年，2月20日，星期日一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。第62页，共163页，2023年，2月20日，星期日图搜索的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。(2)建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。第63页，共163页，2023年，2月20日，星期日

(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)GOLOOP。第64页，共163页，2023年，2月20日，星期日OPEN表节点父节点CLOSED表标号节点父节点OPEN表节点父节点编号CLOSED表编号节点父节点编号第65页，共163页，2023年，2月20日，星期日例子例子：从某王姓家族的四代中找王A的后代且其寿命为X的人。

王A：寿命47，有儿子王B1、王B3、王B2王B1：寿命77，有儿子王C1、王C2王B3：寿命52，有儿子王D1王B2：寿命65，有儿子王E1、王E2王F1：寿命32王G1：寿命96王C2：寿命87，有儿子王F1王D1：寿命77，没有儿子王E1：寿命57，有儿子王G1王E2：寿命92，有儿子王H1王C1：寿命27，没有儿子王H1：寿命51若X=57，如何寻找？第66页，共163页，2023年，2月20日，星期日问题的搜索树第67页，共163页，2023年，2月20日，星期日深度优先搜索的搜索过程无信息图搜索过程—深度优先第68页，共163页，2023年，2月20日，星期日重排九宫深度优先只是搜索树的一部分，尚未到达目标节点，仍需继续往下搜索。第69页，共163页，2023年，2月20日，星期日有界深度优先搜索的搜索过程如果问题有解，且其路径长度<=dm，则上述搜索过程一定能求得解。但是，若解的路径长度>dm，则搜索过程就得不到解。----深度界限的选择很重要。第70页，共163页，2023年，2月20日，星期日有界深度优先搜索设深度界度dm=4，有界深度优先搜索求解图如下，解的路径为S020252628(Sg)第71页，共163页，2023年，2月20日，星期日深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法第72页，共163页，2023年，2月20日，星期日无信息图搜索过程—宽度优先宽度优先搜索过程：(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)考察节点n是否为目标节点，若是则求得问题的解，退出，(5)若节点n不可扩展，则转第(2)步。(6)扩展节点n。将其所有后继节点放到OPEN表的末端，并为每个后续节点都配置指向n的指针。然后转向第(2)步。第73页，共163页，2023年，2月20日，星期日宽度优先第74页，共163页，2023年，2月20日，星期日重排九宫宽度优先解的路径：S0381626第75页，共163页，2023年，2月20日，星期日宽度优先搜索的性质只要问题有解，一定能找到解，而且得到的是路径最短的解。盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，因此搜索效率低。方法与问题无关，具有通用性属于图搜索方法第76页，共163页，2023年，2月20日，星期日非启发式搜索按照事先规定的路线进行搜索广度优先搜索是按“层”进行搜索的，先进入OPEN表的节点先被考察深度优先搜索是沿着纵深方向进行搜索的，后进入OPEN表的节点先被考察按已经付出的代价决定下一步要搜索的节点（为树中的每条边赋予代价，广度及深度优先搜索实质是每条边的代价都为1）代价树的广度优先代价树的深度优先第77页，共163页，2023年，2月20日，星期日代价树的宽度忧先搜索边上标有代价(或费用)的树称为代价树。在代价树中，若用g(x)表示从初姑节点S0到节点x的代价，用c(xl,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)

代价树宽度优先搜索的基本思想是：OPEN表中的节点在任一时刻都是按其代价从小到大排序的，每次扩展时总是从OPEN表中选取代价最小的节点进行扩展。其搜索过程如下：第78页，共163页，2023年，2月20日，星期日五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交道费用(代价)如左图小数字所示。求从A到E的最小费用交通路线。交通代价树如右图，解为ACDE代价树的宽度优先搜索举例第79页，共163页，2023年，2月20日，星期日代价树的深度忧先搜索代价树的宽度优先搜索中，每次扩展时总是从OPEN表中选取代价最小的节点进行扩展。而代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入CLOSE表中进行考察。其搜索过程如下：解也为ACDE第80页，共163页，2023年，2月20日，星期日启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发性信息用于指导搜索过程，且与具体问题求解有关的控制性信息称为启发性信息启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解第81页，共163页，2023年，2月20日，星期日希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。第82页，共163页，2023年，2月20日，星期日基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。第83页，共163页，2023年，2月20日，星期日1，启发式搜索算法A（A算法）评价函数的格式：

f(n)=g(n)+h(n) f(n)：评价函数 g(n):实际已经付出的代价函数 h(n)：启发函数第84页，共163页，2023年，2月20日，星期日符号的意义g*(n)：从s(初始状态S0)到n(当前状态Sn)的最短路径的耗散值h*(n)：从n到g(目标状态Sg)的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值第85页，共163页，2023年，2月20日，星期日一个A算法的例子定义评价函数：

f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值,即顶点Sn在状态空间中的深度(从根顶点到Sn所经历的层次数)。

h(n)为当前节点“不在位”的将牌数 2831647512384765第86页，共163页，2023年，2月20日，星期日h计算举例

h(n)=42

831

647512345768第87页，共163页，2023年，2月20日，星期日2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456g=0,h=4f=0+4=4g=1,h=5f=1+5=6g=0g=1g=2g=3第88页，共163页，2023年，2月20日，星期日最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：

h(n)≤h*(n)

则A算法称为A*算法。其中h*(n)是从顶点Sn到Sg的最小代价。由于h*(n)最小代价通常不知道，因此用h(n)（不在位的将牌数）进行代价估计，因此可得h(n)<h*(n),所以上例是A*算法。第89页，共163页，2023年，2月20日，星期日A*条件举例8数码问题h(n)=“不在位”的将牌数=f1h(n)=将牌“不在位”的距离和=f2采用f2算法的效率会高于f1的算法，因为f2>=f12

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：2第90页，共163页，2023年，2月20日，星期日A*算法的性质定理1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。第91页，共163页，2023年，2月20日，星期日AO*算法是A*算法在与或图上的扩展算法。AO*算法中由于与节点的存在，解对应的不是一条路径，而是一个子图，因此对顶点的评估实际上是对局部解图的评价。与节点代价计算：最大代价和代价或节点的代价计算：最小代价AO*算法第92页，共163页，2023年，2月20日，星期日AO*算法举例7=3+1(左树)+2+18=3+1+3+18=min(8+1,7+1)第93页，共163页，2023年，2月20日，星期日与或树的宽度优先与深度优先搜索宽度优先：12345深度优先：13B524第94页，共163页，2023年，2月20日，星期日问题图搜索是针对什么知识表示方法的问题求解方法？什么是图搜索?其中，重排OPEN表意味着什么，重排的原则是什么?宽度优先搜索方法中OPEN表需要按什么方式进行操作 A．先进后出B．先进先出有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗？试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据加以说明第95页，共163页，2023年，2月20日，星期日启发式搜索的必要性现实的困难迫使人们转而求援于启发式算法。这种算法的本质是部分地放弃算法“一般化,通用化”的概念,把所要解的问题的具体领域的知识加进算法中去,以提高算法的效率。如,广度优先法几乎可以用于解一切搜索问题：九宫图(八数码难题),hanoi塔(焚塔问题),旅行推销员,华容道,以至魔方等等。但实际使用时,效率也许低得惊人,甚至根本解不出来(例如魔方问题)。如果我们为每类问题找出一些特殊规则,和广度优先法配合起来使用,那结果就可能完全不一样了。第96页，共163页，2023年，2月20日，星期日启发式搜索的必要性根据启发信息,在生成各种搜索树时可以考虑种种可能的选择,如:1.下一步展开哪个节点?2.是部分展开还是完全展开?3.使用哪个规则(或算子)?4.怎样决定舍弃还是保留新生成的节点?5.怎样决定舍弃还是保留一棵子树?6.怎样决定停止或继续搜索?7.如何定义启发函数(评价函数)?8.如何决定搜索方向?……

由于这些选择的不同,就得到了不同的启发式算法第97页，共163页，2023年，2月20日，星期日*解路径如粗线所标左、上、右、下**S、A、B、…、L、M等为状态空间图中各个节点名,其后的小括号中数字表示该节点的评价函数f(n)的估计值,例如S(4)、L(5)等。

***图中标记"▲"节点为被扩的节点,标记"■"的节点为生成的节点。

九宫重排问题第98页，共163页，2023年，2月20日，星期日搜索效率比较第99页，共163页，2023年，2月20日，星期日启发式搜索策略

人工智能问题求解者在两种基本情况下运用启发式策略:一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例。所给出的一系列症状可能有多个原因,医生运用启发式搜索来选择最有可能的论断并依此产生治疗计划。一个问题可能有确定解,但是求解过程中的计算机代价令人难以接受。在很多问题(如国际象棋)中,状态空间的增长特别快,可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下,穷尽式搜索策略诸如深度优先或广度优先搜索,在一个给定的较实际的时空内很可能得不到最终的解和发明创造的所有规则一样,启发式策略也是极易出错的第100页，共163页，2023年，2月20日，星期日图搜索策略图搜索策略的定义图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。图搜索算法中的几个重要名词术语（1）OPEN表与CLOSE表（2）搜索图与搜索树第101页，共163页，2023年，2月20日，星期日你可曾听说过“深蓝”？

1997年5月11日，IBM开发的“深蓝”击败了国际象棋冠军卡斯帕罗夫。1980年他获得世界少年组冠军

1982年他并列夺得苏联冠军

1985年22岁的卡斯帕罗夫成为历史上最年轻的国际象棋冠军积分是2849，这一分数是有史以来最高分。远远领先于第二位的克拉姆尼克的2770

卡氏何许人也？第102页，共163页，2023年，2月20日，星期日第103页，共163页，2023年，2月20日，星期日电脑棋手：永不停歇的挑战！1988年“深思”击败了丹麦特级大师拉森。1993年“深思”第二代击败了丹麦世界优秀女棋手小波尔加。第104页，共163页，2023年，2月20日，星期日电脑棋手：永不停歇的挑战！2001年“更弗里茨”击败了除了克拉姆尼克之外的所有排名世界前十位的棋手。2002年10月“更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。2003年1至2月“更年少者”与卡斯帕罗夫在纽约较量，3比3战平。第105页，共163页，2023年，2月20日，星期日许多人在努力

第106页，共163页，2023年，2月20日，星期日机器博弈20世纪50年代，有人设想利用机器智能来实现机器与人的对弈。1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定的、二人、零和、完备信息游戏世界冠军西洋双陆棋这样的存在非确定因素的棋类也有了美国卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠军。对围棋、中国象棋、桥牌、扑克等许多种其它种类游戏博弈的研究也正在进行中。第107页，共163页，2023年，2月20日，星期日机器博弈的基本思想机器博弈的核心思想就是对博弈树节点的估值过程和对博弈树搜索过程的结合第108页，共163页，2023年，2月20日，星期日博弈树在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。第109页，共163页，2023年，2月20日，星期日机器博弈系统的构成知识表示规则集，产生机制，构建博弈树搜索技术估值技术第110页，共163页，2023年，2月20日，星期日博弈搜索博弈搜索的基本思想已经提出半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。没有随机因素的博弈在两个人之间进行，在任何一个时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个棋子是否存在和存在于哪里。二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法另一类是最佳优先的系列算法。第111页，共163页，2023年，2月20日，星期日解谜：电脑是怎样下棋的

——人机博弈程序的一般设计方法以中国棋为例第112页，共163页，2023年，2月20日，星期日（1）第一步该做什么？数据结构的选取——棋盘表示占用空间-〉少操作速度-〉快是否方便-〉方便在机器中表示棋局，让程序知道博弈状态。第113页，共163页，2023年，2月20日，星期日九列十行十四种不同的棋子三十二个棋子第114页，共163页，2023年，2月20日，星期日几种棋盘表示的方式二维数组——直观紧凑的数据结构——省空间，不直观，速度?比特棋盘——用于8*8棋盘（国际象棋），64位主机第115页，共163页，2023年，2月20日，星期日（2）接下来怎么办？产生合法走步的规则，使博弈能公正的进行，并且能够判断对手是否乱走。依赖于具体棋类特征。是一段将局面所有可能的正确走法罗列出来的程序。称之为走法产生。第116页，共163页，2023年，2月20日，星期日几种走法产生的实现方式一般做法建立小型数据库位运算第117页，共163页，2023年，2月20日，星期日位运算走法产生之例寻找象的可走步第118页，共163页，2023年，2月20日，星期日位运算走法产生之要求一个基于比特棋盘的完善的数据库该数据库应位于内存中第119页，共163页，2023年，2月20日，星期日（3）终于到核心了从所有的走法中找出最佳的走法，也就是——搜索第120页，共163页，2023年，2月20日，星期日博弈概述诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的"二人零和、全信息、非偶然"博弈，其特征如下：

(1)对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。

(2)在对垒过程中，任何一方都了解当前的格局及过去的历史。

(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。

第121页，共163页，2023年，2月20日，星期日博弈概述在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是"或"关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是"与"关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。第122页，共163页，2023年，2月20日，星期日博弈概述这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵"与或树"。描述博弈过程的与或树称为博弈树，它有如下特点：

(1)博弈的初始格局是初始节点。

(2)在博弈树中，"或"节点和"与"节点是逐层交替出现的。自己一方扩展的节点之间是"或"关系，对方扩展的节点之间是"与"关系。双方轮流地扩展节点。

(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。

我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。

第123页，共163页，2023年，2月20日，星期日搜索算法极大极小值算法

负极大值搜索深度优先的alpha-beta搜索渴望搜索（AspirationSearch）极小窗口搜索（MinimalWindowSearch）遍历深化（IterativeDeepening）历史启发搜索（HistoryHeuristic）杀手启发搜索(KillerHeuristic)

MTD(f)算法（Memory–enhancedTestDriverwithfandn）第124页，共163页，2023年，2月20日，星期日极大极小法基本思想或算法：(1)设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。(4)当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。(5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。第125页，共163页，2023年，2月20日，星期日极大极小倒推值的计算A是与节点，从下往上可以倒推出S0的估计值第126页，共163页，2023年，2月20日，星期日一字棋游戏极小极大分析法设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。用叉号表示MAX，用圆圈代表MIN。第127页，共163页，2023年，2月20日，星期日一字棋游戏极小极大分析法为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下设棋局为P，估价函数为e(P)(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)(2)若P是MAX必胜的棋局，则e(P)＝+∞。(3)若P是B必胜的棋局，则e(P)＝-∞。

第128页，共163页，2023年，2月20日，星期日一字棋游戏极小极大分析法集中典型棋局得分值h(n)计算：(a)h(n)=4-2=2(b)是和局，h(n)=0(c)×方获胜，h(n)=+∞(d)○方获胜，h(n)=-∞第129页，共163页，2023年，2月20日，星期日一字棋游戏极小极大分析法第一回合扩展深度为2第130页，共163页，2023年，2月20日，星期日第131页，共163页，2023年，2月20日，星期日一字棋极大极小法的第一阶段第132页，共163页，2023年，2月20日，星期日一字棋极大极小法的第二阶段第133页，共163页，2023年，2月20日，星期日一字棋极大极小法的第三阶段第134页，共163页，2023年，2月20日，星期日Alpha-Beta剪枝技术极大极小搜索要求先生成与／或树，然后再计算各节点的估值，需要生成规定深度内的所有节点，因此搜索效率较低。基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。第135页，共163页，2023年，2月20日，星期日Alpha-Beta剪枝技术(1)对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值