人工智能之搜索培训讲义

人工智能导论

第二章：搜索、问题求解与博弈人工智能之搜索培训讲义第1页第二章搜索、问题求解与博弈问题求解能力是人类智能基本组成部分，研究并实现问题求解是人工智能主要研究内容之一。知识（问题）表示是问题求解基础，两种普遍采取问题表示方法：状态空间表示与或图表示搜索（优化）：在问题表示基础上，在合理时间范围内，从问题全部可能解中找到一个最优解或可行解，是问题求解中关键技术。启发式搜索----人工智能本质特征之一。计算机博弈包括问题表示、搜索技术等AI关键问题，现有计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。人工智能之搜索培训讲义第2页主要内容2.1搜索概述2.2问题求解2.2.1状态空间2.2.2与或图2.3搜索技术图搜索2.4机器博弈人工智能之搜索培训讲义第3页一些例子搭积木智力游戏：有一个农夫带一条狼、一只羊和一筐菜要从河左岸乘船到右岸，但受以下条件限制：船太小，农夫每次只能带一样东西过河没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。类似问题：野人和传教士问题下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）人工智能之搜索培训讲义第4页2.1搜索概述人工智能多个研究领域从求解现实问题过程来看，都可抽象为一个“问题求解”过程问题求解过程实际上就是一个搜索过程最优性和计算法复杂性是搜索中一对矛盾，搜索必须考虑三个问题：采取盲目搜索还是启发式搜索盲目搜索：不考虑问题本身特征，经过遍历问题解集合来寻找可行解或最优解。启发式搜索：利用与问题相关启发式信息来确定搜索方向，以加紧搜索过程。进行局部搜索还是全集搜索搜索可行解还是最优解人工智能之搜索培训讲义第5页2.1搜索概述评价一个搜索算法原因：完备性：假如问题有解，一定能找到一个解最优性：假如问题存在最优解，则一定能找到这个最优解复杂性：时间和空间复杂性，在确保最优性和完备性前提下，算法复杂性越小越好。当前搜索算法还不能同时满足以上三个要求。为了进行搜索，首先必须用某种形式把问题表示出来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程两种惯用方法。人工智能之搜索培训讲义第6页2.2问题求解状态空间表示法和与或图表示法不但是问题表示方法，也分别代表了两种问题求解思绪状态空间将问题求解所包括每个可能步骤表示成一个状态，全部状态以及状态之间全部转换组成一个以图形式表示状态空间。问题求解过程是在状态空间中搜索一条最优或可行从初始状态到目标状态路径过程。与或图表示法基础是问题归约，经过一系列分解或变换，将复杂问题逐步转化为比较简单问题，直至能够直接求解本原问题。与或图求解过程是在与或图中搜索一个将原始问题变换为简单问题在变换为本原问题、最优或可行归约步骤过程。人工智能之搜索培训讲义第7页2.2.1状态空间表示法状态空间表示法是用“状态”和“算子”来表示问题一个方法状态：用来描述问题求解过程中不一样时刻情况算子：表示对状态操作，算子每次使用就使问题由一个状态变换为另一个状态当到达目标状态时，由初始状态到目标状态所用算子序列就是问题一个解人工智能之搜索培训讲义第8页2.2.1状态空间表示法状态状态是描述问题求解过程中任一时刻情况数据结构，普通用一组变量有序组合表示：SK(SK0,SK1,…)当给每一分量以确定值时，就得到一个详细状态算子引发状态中一些分量发生改变，从而使问题由一个状态变为另一个状态操作称为算子。产生式系统中，每一条产生式规则就是一个算子状态空间由问题全部状态及一切可用算符所组成集合称为问题状态空间，普通用三元组表示:(S,F,C,I,G)S:全部状态组成集合F:用于状态转换算子集合C:状态转换代价聚合I:初始状态集合G:目标状态集合人工智能之搜索培训讲义第9页例:二阶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页例:二阶HanoiTower（梵塔）问题9种状态，12种算子组成状态空间转移图：人工智能之搜索培训讲义第11页2.2.1状态空间表示法总结：用状态空间方法表示问题时，首先必须定义状态描述形式，经过使用这种描述形式可把问题一切状态都表示出来。其次，还安定义一组算符，经过使用算符可把问题由一个状态转变为另一个状态。问题求解过程是一个不停把算符作用于状态过程。假如在使用某个算符后得到新状态是目标状态，就得到问题一个解：从初始状态到目标状态所用算符组成序列。算符一次使用，就使问题由一个状态转变为另一个状态。可能有多个算特序列都可使问题从初始状态变到目标状态，这就得到了多个解。把使用算符最少解称为最优解。对任何一个状态，可使用算符可能不止一个，因而由一个状态所生成后继状态就可能有多个。当对这些后继状态使用算子生成更深入状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不一样搜索策略操作次序是不相同。人工智能之搜索培训讲义第12页2.2.1状态空间表示法基于状态空间表示问题求解算法Step1：确定问题状态计算机描述形式，将全部可能状态表示出来，并确定其中初始状态和目标状态。Step2：确定促使状态发生转换操作，并在计算机中将其表示为对应算符。Step3：以状态为顶点，状态之间所允许操作为有向边，取得‘图’形式状态空间。Step4：应用图搜索方法，在状态空间中搜索从初始状态到目标状态最优路径或可行路径。人工智能之搜索培训讲义第13页例:三阶HanoiTower（梵塔）问题人工智能之搜索培训讲义第14页例:三阶HanoiTower（梵塔）问题人工智能之搜索培训讲义第15页例:三阶HanoiTower（梵塔）问题人工智能之搜索培训讲义第16页2.2.2与或图表示法也称为问题归约方法：把初始问题经过一系列交换最终变为一个子问题集合，而这些于问题解能够直接得到，从而解答了初始问题。分解：把一个复杂问题分解为若干个较为简单子问题，每个子问题又可继续分解为若干个更为简单子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最终把各子问题解复合起来就得到了原问题解。问题分解能够用图表示出来，称为与树。比如，把问题P分解为三个子问题P1、P2和P3，能够表示为下列图：人工智能之搜索培训讲义第17页2.2.2与或图表示法等价变换：利用同构或同态等价变换，把它变换成若干个较轻易求解新问题。若新问题中有一个可求解，则就得到了原问题解。问题等价变换过程也可用一个图表示出来，称为“或”树。与或树结合称为与或图（树）。人工智能之搜索培训讲义第18页2.2.2与或图表示法本原问题：不能再分解或变换，而且直接可解子问题称为本原问题。端节点与终止节点：在与／或树中，没有子节点节点称为端节点；本原问题所对应节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。可解节点：在与／或树今，满足以下条件之一节点：1)它是一个终止节点。2)它是一个“或”节点，且其子节点最少有一个是可解节点。3)它是一个“与”节点，且其子节点全部是可解节点。不可解节点：上面三个条件全不满足节点。解树：由可解节点所组成，而且由这些可解节点可推出初始节点(它对应于原始问题)为可解节点子树称为解树。在解树中’定包含初始节点。人工智能之搜索培训讲义第19页例:三阶HanoiTower（梵塔）问题设有A、B、C三个盘片以及三根柱子，三个盘片按从小到大次序穿在1号柱上，要求把它们全部移到3号柱上，而且每次只能移动一个盘片，任何时刻都不能把大盘片压在小盘片上面，如图所表示。人工智能之搜索培训讲义第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页例:三阶HanoiTower（梵塔）问题定义问题状态表示：设三元组(i,j,k)表示状态，其中i表示盘片C所在柱号,j表示盘片B所在柱号；k表示盘片A所在柱号。初始问题可表示为：(1、1．1)(3，3，3)与／或树表示如图所表示。(把图中7个终止节点(本原问题)按从左至右排列，得到了初始问题解)人工智能之搜索培训讲义第22页2.2.2与或图表示法基于与或图表示问题求解算法Step1：确定单个问题描述形式，可采取状态空间表示法。Step2：从原始问题开始，逐步进行分解和变换，直到本原问题，然后将全部分解和变换过程表示为与或图。Step3：从端顶点开始，逐步向上回溯，标注各顶点为可解或不可解顶点，直到标注原始顶点为可解顶点或不可解顶点为止Step4：当原始顶点被确定为可解顶点时，输出对应解图为问题解。人工智能之搜索培训讲义第23页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页2.3搜索技术

搜索问题是AI关键理论问题之一普通一个问题能够用好几个搜索技术处理,选择一个好搜索技术对处理问题效率很相关系,甚至关系到求解问题有没有解。搜索方法好标准,普通认为有两个：(1)搜索空间小;(2)解最正确。人工智能之搜索培训讲义第25页2.3搜索技术

搜索从问题性质上来看,可分为普通搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还能够分得更细。当所给定问题用状态空间表示时,则求解过程可归结为对状态空间搜索。当问题有解时,使用不一样搜索策略,找到解搜索空间范围是有区分。普通来说,对大空间问题,搜索策略是要处理组合爆炸问题人工智能之搜索培训讲义第26页人工智能之搜索培训讲义第27页2.3搜索策略

通常搜索策略主要任务是确定怎样选取规则方式。有两种基本方式:一个是不考虑给定问题所含有特定知识,系统依据事先确定好某种固定排序,依次调用规则或随机调用规则,这实际上是盲目搜索方法,普通统称为无信息引导搜索策略。另一个是考虑问题领域可应用知识,动态地确定规则排序,优先调用较适当规则使用,这就是通常称为启发式搜索策略或有信息引导搜索策略。人工智能之搜索培训讲义第28页AI领域搜索方法(1)求任一解路搜索策略回溯法(Backtracking)爬山法(HillClimbing)宽度优先法(Breadth-first)深度优先法(Depth-first)限定范围搜索法(BeamSearch)最正确优先法(Best-first)(2)求最正确解路搜索策略大英博物馆法(BritishMuseum)分枝界限法(BranchandBound)动态规划法(DynamicProgramming)最正确图搜索法(A*)人工智能之搜索培训讲义第29页AI领域搜索方法(3)求与或关系解图搜索法普通与或图搜索法(AO*)

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

启发式剪枝法(HeuristicPruning)人工智能之搜索培训讲义第30页搜索策略分类人工智能之搜索培训讲义第31页盲目搜索方法盲目搜索是不利用问题相关信息,而依据事先确定好某种固定搜索方法进行搜索。经典盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法人工智能之搜索培训讲义第32页回溯策略例：皇后问题在一个4×4国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获人工智能之搜索培训讲义第33页()人工智能之搜索培训讲义第34页()Q((1,1))人工智能之搜索培训讲义第35页()QQ((1,1))((1,1)(2,3))人工智能之搜索培训讲义第36页()Q((1,1))((1,1)(2,3))人工智能之搜索培训讲义第37页()QQ((1,1))((1,1)(2,3))((1,1)(2,4))人工智能之搜索培训讲义第38页()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))人工智能之搜索培训讲义第39页()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))人工智能之搜索培训讲义第40页()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))人工智能之搜索培训讲义第41页()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))人工智能之搜索培训讲义第42页()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))人工智能之搜索培训讲义第43页()((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页()((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页()((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页递归思想从前有座山……

从前有座山……

从前有座山……人工智能之搜索培训讲义第47页Fibonacci数列12，意大利家斐波那契在提出了一个关于兔子繁殖问题：

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

不发生死亡情況下，由一对出生小兔开始，50個月后会有多少对兔子？人工智能之搜索培训讲义第48页當n＞1時，Fn+2=Fn+1+Fn，而F0=F1=1。人工智能之搜索培训讲义第49页递归思想（续）当前状态目标状态g人工智能之搜索培训讲义第50页回溯搜索算法 BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态路径 （以规则表形式表示） 或FAIL。人工智能之搜索培训讲义第51页回溯搜索算法递归过程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页存在问题及处理方法问题：深度问题死循环问题处理方法：对搜索深度加以限制统计从初始状态到当前状态路径人工智能之搜索培训讲义第53页回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前状态表（逆向） 返回值：从当前状态到目标状态路径 （以规则表形式表示） 或FAIL。人工智能之搜索培训讲义第54页回溯搜索算法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页回溯搜索算法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页一些深入问题失败原因分析、多步回溯QQ人工智能之搜索培训讲义第57页一些深入问题（续）回溯搜索中知识利用 基本思想： 尽可能选取划去对角线上位置数最少。QQQQ4334人工智能之搜索培训讲义第58页

图搜索策略问题引出回溯搜索：只保留从初始状态到当前状态一条路径。图搜索：保留全部已经搜索过路径。

人工智能之搜索培训讲义第59页一些基本概念节点深度： 根节点深度=0

其它节点深度=父节点深度+10123人工智能之搜索培训讲义第60页一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1含有一个后继节点ni，则该序列称为从n0到nk路径。路径耗散值 一条路径耗散值等于连接这条路径各节点间全部耗散值总和。用C(ni,nj)表示从ni到nj路径耗散值。人工智能之搜索培训讲义第61页一些基本概念（续1）扩展一个节点 生成出该节点全部后继节点，并给出它们之间耗散值。这一过程称为“扩展一个节点”。人工智能之搜索培训讲义第62页图搜索普通过程(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页

(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页OPEN表节点父节点CLOSED表标号节点父节点OPEN表节点父节点编号CLOSED表编号节点父节点编号人工智能之搜索培训讲义第65页例子例子：从某王姓家族四代中找王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页问题搜索树人工智能之搜索培训讲义第67页深度优先搜索搜索过程无信息图搜索过程—深度优先人工智能之搜索培训讲义第68页重排九宫深度优先只是搜索树一部分，还未抵达目标节点，仍需继续往下搜索。人工智能之搜索培训讲义第69页有界深度优先搜索搜索过程假如问题有解，且其路径长度<=dm，则上述搜索过程一定能求得解。不过，若解路径长度>dm，则搜索过程就得不到解。----深度界限选择很主要。人工智能之搜索培训讲义第70页有界深度优先搜索设深度界度dm=4，有界深度优先搜索求解图以下，解路径为S020252628(Sg)人工智能之搜索培训讲义第71页深度优先搜索性质普通不能确保找到最优解当深度限制不合理时，可能找不到解，能够将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法差异：图搜索是一个通用与问题无关方法人工智能之搜索培训讲义第72页无信息图搜索过程—宽度优先宽度优先搜索过程：(1)把起始节点放到OPEN表中(假如该起始节点为一目标节点，则求得一个解答)。(2)假如OPEN是个空表，则没有解，失溃退出；不然继续。(3)把OPEN表中第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)考查节点n是否为目标节点，若是则求得问题解，退出，(5)若节点n不可扩展，则转第(2)步。(6)扩展节点n。将其全部后继节点放到OPEN表末端，并为每个后续节点都配置指向n指针。然后转向第(2)步。人工智能之搜索培训讲义第73页宽度优先人工智能之搜索培训讲义第74页重排九宫宽度优先解路径：S0381626人工智能之搜索培训讲义第75页宽度优先搜索性质只要问题有解，一定能找到解，而且得到是路径最短解。盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，所以搜索效率低。方法与问题无关，含有通用性属于图搜索方法人工智能之搜索培训讲义第76页非启发式搜索按照事先要求路线进行搜索广度优先搜索是按“层”进行搜索，先进入OPEN表节点先被考查深度优先搜索是沿着纵深方向进行搜索，后进入OPEN表节点先被考查按已经付出代价决定下一步要搜索节点（为树中每条边赋予代价，广度及深度优先搜索实质是每条边代价都为1）代价树广度优先代价树深度优先人工智能之搜索培训讲义第77页代价树宽度忧先搜索边上标有代价(或费用)树称为代价树。在代价树中，若用g(x)表示从初姑节点S0到节点x代价，用c(xl,x2)表示从父节点x1到子节点x2代价，则有：g(x2)=g(x1)+c(x1,x2)

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

f(n)=g(n)+h(n) f(n)：评价函数

g(n):实际已经付出代价函数

h(n)：启发函数人工智能之搜索培训讲义第84页符号意义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页一个A算法例子定义评价函数：

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

h(n)为当前节点“不在位”将牌数 2831647512384765人工智能之搜索培训讲义第86页h计算举例 h(n)=42

831

647512345768人工智能之搜索培训讲义第87页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页最正确图搜索算法A*（A*算法）在A算法中，假如满足条件：

h(n)≤h*(n)

则A算法称为A*算法。其中h*(n)是从顶点Sn到Sg最小代价。因为h*(n)最小代价通常不知道，所以用h(n)（不在位将牌数）进行代价预计，所以可得h(n)<h*(n),所以上例是A*算法。人工智能之搜索培训讲义第89页A*条件举例8数码问题h(n)=“不在位”将牌数=f1h(n)=将牌“不在位”距离和=f2采取f2算法效率会高于f1算法，因为f2>=f12

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：2人工智能之搜索培训讲义第90页A*算法性质定理1： 对有限图，假如从初始节点s到目标节点t有路径存在，则算法A一定成功结束。人工智能之搜索培训讲义第91页AO*算法是A*算法在与或图上扩展算法。AO*算法中因为与节点存在，解对应不是一条路径，而是一个子图，所以对顶点评定实际上是对局部解图评价。与节点代价计算：最大代价和代价或节点代价计算：最小代价AO*算法人工智能之搜索培训讲义第92页AO*算法举例7=3+1(左树)+2+18=3+1+3+18=min(8+1,7+1)人工智能之搜索培训讲义第93页与或树宽度优先与深度优先搜索宽度优先：12345深度优先：13B524人工智能之搜索培训讲义第94页问题图搜索是针对什么知识表示方法问题求解方法？什么是图搜索?其中，重排OPEN表意味着什么，重排标准是什么?宽度优先搜索方法中OPEN表需要按什么方式进行操作 A．先进后出B．先进先出有界深度优先搜索方法能够确保在搜索树中找到一条通向目标节点最短路径吗？试比较各种盲目搜索搜索方法效率，找出影响算法效率原因试比较宽度优先搜索、有界深度优先搜索及有序搜索搜索效率，并以实例数据加以说明人工智能之搜索培训讲义第95页启发式搜索必要性

现实困难迫使人们转而求援于启发式算法。这种算法本质是部分地放弃算法“普通化,通用化”概念,把所要解问题详细领域知识加进算法中去,以提升算法效率。如,广度优先法几乎能够用于解一切搜索问题：九宫图(八数码难题),hanoi塔(焚塔问题),旅行推销员,华容道,以至魔方等等。但实际使用时,效率可能低得惊人,甚至根本解不出来(比如魔方问题)。假如我们为每类问题找出一些特殊规则,和广度优先法配合起来使用,那结果就可能完全不一样了。人工智能之搜索培训讲义第96页启发式搜索必要性依据启发信息,在生成各种搜索树时能够考虑种种可能选择,如:1.下一步展开哪个节点?2.是部分展开还是完全展开?3.使用哪个规则(或算子)?4.怎样决定舍弃还是保留新生成节点?5.怎样决定舍弃还是保留一棵子树?6.怎样决定停顿或继续搜索?7.怎样定义启发函数(评价函数)?8.怎样决定搜索方向?……

因为这些选择不一样,就得到了不一样启发式算法人工智能之搜索培训讲义第97页*解路径如粗线所标左、上、右、下**S、A、B、…、L、M等为状态空间图中各个节点名,其后小括号中数字表示该节点评价函数f(n)预计值,比如S(4)、L(5)等。

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

九宫重排问题人工智能之搜索培训讲义第98页搜索效率比较人工智能之搜索培训讲义第99页启发式搜索策略

人工智能问题求解者在两种基本情况下利用启发式策略:一个问题因为在问题陈说和数据获取方面固有含糊性可能使它没有一个确定解。医疗诊疗即是一例。所给出一系列症状可能有多个原因,医生利用启发式搜索来选择最有可能论断并依此产生治疗计划。一个问题可能有确定解,不过求解过程中计算机代价令人难以接收。在很多问题(如国际象棋)中,状态空间增加尤其快,可能状态数伴随搜索深度呈指数级增加、分解。在这种情况下,穷尽式搜索策略诸如深度优先或广度优先搜索,在一个给定较实际时空内很可能得不到最终解和创造创造全部规则一样,启发式策略也是极易犯错人工智能之搜索培训讲义第100页图搜索策略图搜索策略定义图搜索策略可看作一个在图中寻找路径方法。初始节点和目标节点分别代表初始数据库和满足终止条件数据库。求得把一个数据库变换为另一数据库规则序列问题就等价于求得图中一条路径问题。研究图搜索普通策略，能够给出图搜索过程普通步骤。图搜索算法中几个主要名词术语（1）OPEN表与CLOSE表（2）搜索图与搜索树人工智能之搜索培训讲义第101页你可曾听说过“深蓝”？1997年5月11日，IBM开发“深蓝”击败了国际象棋冠军卡斯帕罗夫。1980年他取得世界少年组冠军

1982年他并列夺得苏联冠军

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

卡氏何许人也？人工智能之搜索培训讲义第102页人工智能之搜索培训讲义第103页电脑棋手：永不停歇挑战！1988年“深思”击败了丹麦特级大师拉森。1993年“深思”第二代击败了丹麦世界优异女棋手小波尔加。人工智能之搜索培训讲义第104页电脑棋手：永不停歇挑战！“更弗里茨”击败了除了克拉姆尼克之外全部排名世界前十位棋手。年10月“更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。201至2月“更年少者”与卡斯帕罗夫在纽约较量，3比3战平。人工智能之搜索培训讲义第105页许多人在努力

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

——人机博弈程序普通设计方法以中国棋为例人工智能之搜索培训讲义第112页（1）第一步该做什么？数据结构选取——棋盘表示占用空间-〉少操作速度-〉快是否方便-〉方便在机器中表示棋局，让程序知道博弈状态。人工智能之搜索培训讲义第113页九列十行十四种不一样棋子三十二个棋子人工智能之搜索培训讲义第114页几个棋盘表示方式二维数组——直观

紧凑数据结构——省空间，不直观，速度?

比特棋盘——用于8*8棋盘（国际象棋），64位主机人工智能之搜索培训讲义第115页（2）接下来怎么办？产生正当走步规则，使博弈能公正进行，而且能够判断对手是否乱走。依赖于详细棋类特征。是一段将局面全部可能正确走法罗列出来程序。称之为走法产生。人工智能之搜索培训讲义第116页几个走法产生实现方式普通做法

建立小型数据库

位运算人工智能之搜索培训讲义第117页位运算走法产生之例寻找象可走步人工智能之搜索培训讲义第118页位运算走法产生之要求一个基于比特棋盘完善数据库该数据库应位于内存中人工智能之搜索培训讲义第119页（3）终于到关键了从全部走法中找出最正确走法，也就是——搜索人工智能之搜索培训讲义第120页博弈概述诸以下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很各种，我们讨论最简单"二人零和、全信息、非偶然"博弈，其特征以下：

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

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

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

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

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

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

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

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

人工智能之搜索培训讲义第123页搜索算法极大极小值算法

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

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

人工智能之搜索培训讲义第128页一字棋游戏极小极大分析法集中经典棋局得分值h(n)计算：(a)h(n)=4-2=2(b)是和局，h(n)=0(c)×方获胜，h(n)=+∞(d)○方获胜，h(n)=-∞人工智能之搜索培训讲义第129页一字棋游戏极小极大分析法第一回合扩展深度为2人工智能之搜索培训讲义第130页人工智能之搜索培训讲义第131页一字棋极大极小法第一阶段人工智能之搜索培训讲义第132页一字棋极大极小法第二阶段人工智能之搜索培训讲义第133页一字棋极大极小法第三阶段人工智能之搜索培训讲义第134页Alpha-Beta剪枝技术极大极小搜索要求先生成与／或树，然后再计算各节点估值，需要生成要求深度内全部节点，所以搜索效率较低。基本思想或算法是，边生成博弈树边计算评定各节点倒推值，而且依据评定出倒推值范围，及时停顿扩展那些已无必要再扩展子节点，即相当于剪去了博弈树上一些分枝，从而节约了机器开销，提升了搜索效率。人工智能之搜索培训讲义第135页Alpha-Beta剪枝技术(1)对于一个与节点MIN，若能预计出其倒推值上确界β，而且这个β值小于MIN父节点(一定是或节点)预计倒推值下确界α，即α≥β，则就无须再扩