人工智能之搜索培训讲义.pptx

《人工智能之搜索培训讲义.pptx》由会员分享，可在线阅读，更多相关《人工智能之搜索培训讲义.pptx（163页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能导论 第二章：搜索、问题求解与博弈人工智能之搜索培训讲义第1页第二章 搜索、问题求解与博弈n问题求解能力是人类智能基本组成部分，研究并实现问题求解是人工智能主要研究内容之一。n知识（问题）表示是问题求解基础，两种普遍采取问题表示方法：n状态空间表示n与或图表示n搜索（优化）：在问题表示基础上，在合理时间范围内，从问题全部可能解中找到一个最优解或可行解，是问题求解中关键技术。n启发式搜索-人工智能本质特征之一。n计算机博弈包括问题表示、搜索技术等AI关键问题，现有计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。人工智能之搜索培训讲义第2页主要内容n2.1 搜索概述n2.2

2、问题求解n2.2.1 状态空间n2.2.2 与或图n2.3 搜索技术n图搜索n2.4 机器博弈人工智能之搜索培训讲义第3页一些例子n搭积木n智力游戏：n有一个农夫带一条狼、一只羊和一筐菜要从河左岸乘船到右岸，但受以下条件限制：n船太小，农夫每次只能带一样东西过河n没有农夫看管，则狼要吃羊，羊要吃菜n请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。n类似问题：野人和传教士问题n下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）人工智能之搜索培训讲义第4页2.1 搜索概述n人工智能多个研究领域从求解现实问题过程来看，都可抽象为一个“问题求解”过程n问题求解过程实际上就是一个搜索过程n最

3、优性和计算法复杂性是搜索中一对矛盾，搜索必须考虑三个问题：n采取盲目搜索还是启发式搜索n盲目搜索：不考虑问题本身特征，经过遍历问题解集合来寻找可行解或最优解。n启发式搜索：利用与问题相关启发式信息来确定搜索方向，以加紧搜索过程。n进行局部搜索还是全集搜索n搜索可行解还是最优解人工智能之搜索培训讲义第5页2.1 搜索概述n评价一个搜索算法原因：n完备性：假如问题有解，一定能找到一个解n最优性：假如问题存在最优解，则一定能找到这个最优解n复杂性：时间和空间复杂性，在确保最优性和完备性前提下，算法复杂性越小越好。n当前搜索算法还不能同时满足以上三个要求。n为了进行搜索，首先必须用某种形式把问题表示出

4、来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程两种惯用方法。人工智能之搜索培训讲义第6页2.2 问题求解n状态空间表示法和与或图表示法不但是问题表示方法，也分别代表了两种问题求解思绪n状态空间将问题求解所包括每个可能步骤表示成一个状态，全部状态以及状态之间全部转换组成一个以图形式表示状态空间。问题求解过程是在状态空间中搜索搜索一条最优或可行从初始状态到目标状态路径过程。n与或图表示法基础是问题归约，经过一系列分解或变换，将复杂问题逐步转化为比较简单问题，直至能够直接求解本原问题。与或图求解过程是在与或图中搜索搜索一个将原始问题变换为简单问题在变换为本原问题、最优或可行归约步骤过程

5、。人工智能之搜索培训讲义第7页2.2.1 状态空间表示法n状态空间表示法是用“状态”和“算子”来表示问题一个方法n状态：用来描述问题求解过程中不一样时刻情况n算子：表示对状态操作，算子每次使用就使问题由一个状态变换为另一个状态n当到达目标状态时，由初始状态到目标状态所用算子序列就是问题一个解人工智能之搜索培训讲义第8页2.2.1 状态空间表示法n状态n状态是描述问题求解过程中任一时刻情况数据结构，普通用一组变量有序组合表示：SK(SK0,SK1,)n当给每一分量以确定值时，就得到一个详细状态n算子n引发状态中一些分量发生改变，从而使问题由一个状态变为另一个状态操作称为算子。产生式系统中，每一条

6、产生式规则就是一个算子n状态空间n由问题全部状态及一切可用算符所组成集合称为问题状态空间，普通用三元组表示:(S,F,C,I,G)nS:全部状态组成集合nF:用于状态转换算子集合nC:状态转换代价聚合nI:初始状态集合nG:目标状态集合人工智能之搜索培训讲义第9页例:二阶Hanoi Tower（梵塔）问题n设有三根柱子，在1号柱于上穿有A、B两个盘片，盘A小于盘B，盘A位于盘B上面。要求把这两个盘片全部移到另一根柱子上，而且要求每次只能移动一片，任何时刻都不能使盘B位于盘A上面。n设SK=(SK0,SK1)表示问题状态，SK0 表示盘片A所在柱号，SK1 表示盘片B所在柱号n全部可能状态:nS

7、0=(1,1),S1=(1,2),S2=(1,3),nS3=(2,1),S4=(2,2),S5=(2,3),nS6=(3,1),S7=(3,2),S8=(3,3).n问题初始状态集合S=S0,目标集合为G=S4,S8n算子分别用A(i,j),B(i,j)表示nA(i,j):盘片A从柱i移到柱j；B(i,j):盘片B从柱i移到柱jn全部可能算子：nA(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2),nB(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)人工智能之搜索培训讲义第10页例:二阶Hanoi Tower（梵塔）问题n9种状态，

8、12种算子组成状态空间转移图：人工智能之搜索培训讲义第11页2.2.1 状态空间表示法n总结：n用状态空间方法表示问题时，首先必须定义状态描述形式，经过使用这种描述形式可把问题一切状态都表示出来。其次，还安定义一组算符，经过使用算符可把问题由一个状态转变为另一个状态。n问题求解过程是一个不停把算符作用于状态过程。假如在使用某个算符后得到新状态是目标状态，就得到问题一个解：从初始状态到目标状态所用算符组成序列。n算符一次使用，就使问题由一个状态转变为另一个状态。可能有多个算特序列都可使问题从初始状态变到目标状态，这就得到了多个解。把使用算符最少解称为最优解。n对任何一个状态，可使用算符可能不止一

9、个，因而由一个状态所生成后继状态就可能有多个。当对这些后继状态使用算子生成更深入状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不一样搜索策略操作次序是不相同。人工智能之搜索培训讲义第12页2.2.1状态空间表示法n基于状态空间表示问题求解算法nStep1：确定问题状态计算机描述形式，将全部可能状态表示出来，并确定其中初始状态和目标状态。nStep2：确定促使状态发生转换操作，并在计算机中将其表示为对应算符。nStep3：以状态为顶点，状态之间所允许操作为有向边，取得图形式状态空间。nStep4：应用图搜索方法，在状态空间中搜索从初始状态到目标状态最优路径或可行路径。人工智能之搜索培训讲

10、义第13页例:三阶Hanoi Tower（梵塔）问题人工智能之搜索培训讲义第14页例:三阶Hanoi Tower（梵塔）问题人工智能之搜索培训讲义第15页例:三阶Hanoi Tower（梵塔）问题人工智能之搜索培训讲义第16页2.2.2 与或图表示法n也称为问题归约方法：把初始问题经过一系列交换最终变为一个子问题集合，而这些于问题解能够直接得到，从而解答了初始问题。n分解：把一个复杂问题分解为若干个较为简单子问题，每个子问题又可继续分解为若干个更为简单子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最终把各子问题解复合起来就得到了原问题解。n问题分解能够用

11、图表示出来，称为与树。比如，把问题P分解为三个子问题P1、P2和P3，能够表示为下列图：人工智能之搜索培训讲义第17页2.2.2 与或图表示法n等价变换：利用同构或同态等价变换，把它变换成若干个较轻易求解新问题。若新问题中有一个可求解，则就得到了原问题解。n问题等价变换过程也可用一个图表示出来，称为“或”树。n与或树结合称为与或图（树）。人工智能之搜索培训讲义第18页2.2.2 与或图表示法n本原问题：不能再分解或变换，而且直接可解子问题称为本原问题。n端节点与终止节点：在与或树中，没有子节点节点称为端节点；本原问题所对应节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。

12、n可解节点：在与或树今，满足以下条件之一节点：n1)它是一个终止节点。n2)它是一个“或”节点，且其子节点最少有一个是可解节点。n3)它是一个“与”节点，且其子节点全部是可解节点。n不可解节点：上面三个条件全不满足节点。n解树：由可解节点所组成，而且由这些可解节点可推出初始节点(它对应于原始问题)为可解节点子树称为解树。在解树中定包含初始节点。人工智能之搜索培训讲义第19页例:三阶Hanoi Tower（梵塔）问题n设有A、B、C三个盘片以及三根柱子，三个盘片按从小到大次序穿在1号柱上，要求把它们全部移到3号柱上，而且每次只能移动一个盘片，任何时刻都不能把大盘片压在小盘片上面，如图所表示。人工

13、智能之搜索培训讲义第20页例:三阶Hanoi Tower（梵塔）问题n分析：n1)为了把三个盘片全部移到3号柱上，必须先把盘片C移到3号柱上。n2)为了移盘片C，必须先把盘片A及B移到2号柱上。n3)当把盘片C移到3号盘上后，就可把A、B从2号柱移到3号柱上，以完成问题求解。n把原问题分解为三个子问题：n1)把盘片A及B移到2号柱双盘片问题。n2)把盘片C移到3号柱单盘片问题。n3)把盘片A及B移到3号柱双盘片问题。n其中，子问题1)与子问题3)又分别可分解为三个子问题人工智能之搜索培训讲义第21页例:三阶Hanoi Tower（梵塔）问题n定义问题状态表示：设三元组(i,j,k)表示状态，其

14、中i表示盘片C所在柱号,j表示盘片B所在柱号；k表示盘片A所在柱号。n初始问题可表示为：(1、11)(3，3，3)n与或树表示如图所表示。(把图中7个终止节点(本原问题)按从左至右排列，得到了初始问题解)人工智能之搜索培训讲义第22页2.2.2 与或图表示法n基于与或图表示问题求解算法nStep1：确定单个问题描述形式，可采取状态空间表示法。nStep2：从原始问题开始，逐步进行分解和变换，直到本原问题，然后将全部分解和变换过程表示为与或图。nStep3：从端顶点开始，逐步向上回溯，标注各顶点为可解或不可解顶点，直到标注原始顶点为可解顶点或不可解顶点为止nStep4：当原始顶点被确定为可解顶点

15、时，输出对应解图为问题解。人工智能之搜索培训讲义第23页2.3 搜索技术n 搜索技术是人工智能基本技术之一,在人工智能各应用领域中被广泛地使用。n早期人工智能程序与搜索技术联络就更为紧密，几乎全部早期人工智能程序都是以搜索为基础。比如，A.Newell(艾伦纽厄尔)和HASimon(西蒙)等人编写LT(Logic Theorist)程序,J.Slagle写符号积分程序SAINT,ANewell和HASimon写GPS(General Problem Solver)程序,HGelernter(格伦特尔)写Geometry theorem-proving machine程序,R.Fikes(菲克斯

16、)和N.Nilsson(尼尔逊)写STRIPS(Stanford Research Institute Problem Solver)程序以及A.Samuel(塞缪尔)写Chechers程序等,都使用了各种搜索技术。n现在,搜索技术渗透在各种人工智能系统中,能够说没有哪一个人工智能应用不用搜索方法,在教授系统、自然语言了解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。人工智能之搜索培训讲义第24页2.3 搜索技术n 搜索问题是AI关键理论问题之一n普通一个问题能够用好几个搜索技术处理,选择一个好搜索技术对处理问题效率很相关系,甚至关系到求解问题有没有解。n搜索方法好标准,

17、普通认为有两个：n(1)搜索空间小;n(2)解最正确。人工智能之搜索培训讲义第25页2.3 搜索技术n 搜索从问题性质上来看,可分为普通搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还能够分得更细。n当所给定问题用状态空间表示时,则求解过程可归结为对状态空间搜索。n 当问题有解时,使用不一样搜索策略,找到解搜索空间范围是有区分。普通来说,对大空间问题,搜索策略是要处理组合爆炸问题人工智能之搜索培训讲义第26页人工智能之搜索培训讲义第27页2.3 搜索策略n 通常搜索策略主要任务是确定怎样选取规则方式。有两种基本方式:n一个是不考虑给定问题所含有特定知识,系统依据事先确定好某种固

18、定排序,依次调用规则或随机调用规则,这实际上是盲目搜索方法,普通统称为无信息引导搜索策略。n另一个是考虑问题领域可应用知识,动态地确定规则排序,优先调用较适当规则使用,这就是通常称为启发式搜索策略或有信息引导搜索策略。人工智能之搜索培训讲义第28页AI领域搜索方法n(1)求任一解路搜索策略n回溯法(Backtracking)n爬山法(Hill Climbing)n宽度优先法(Breadth-first)n深度优先法(Depth-first)n限定范围搜索法(Beam Search)n最正确优先法(Best-first)n(2)求最正确解路搜索策略n大英博物馆法(British Museum)n

19、分枝界限法(Branch and Bound)n动态规划法(Dynamic Programming)n最正确图搜索法(A*)人工智能之搜索培训讲义第29页AI领域搜索方法n(3)求与或关系解图搜索法n普通与或图搜索法(AO*)n 极小极大法(Minimax)n剪枝法(Alpha-beta Pruning)n 启发式剪枝法(Heuristic Pruning)人工智能之搜索培训讲义第30页搜索策略分类人工智能之搜索培训讲义第31页盲目搜索方法n盲目搜索是不利用问题相关信息,而依据事先确定好某种固定搜索方法进行搜索。n经典盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜

20、索方法人工智能之搜索培训讲义第32页回溯策略n例：皇后问题n 在一个44国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获 人工智能之搜索培训讲义第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

21、)(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)

22、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数列n12，意大利家斐波那契在提出了一个关于兔子

23、繁殖问题：假如一对兔子每个月能生一对小兔（一雄一雌），而每对小兔在它出生後第三个月里，又能开始生一对小兔，假定在不发生死亡情況下，由一对出生小兔开始，50個月后会有多少对兔子？人工智能之搜索培训讲义第48页n當n1時，Fn+2=Fn+1+Fn，而 F0=F1=1。人工智能之搜索培训讲义第49页递归思想（续）当前状态目标状态g人工智能之搜索培训讲义第50页回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态路径（以规则表形式表示）或FAIL。人工智能之搜索培训讲义第51页回溯搜索算法递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETU

24、RN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);人工智能之搜索培训讲义第52页存在问题及处理方法n问题：n深度问题n死循环问题n处理方法：n对搜索深度加以限制n统计从初始状态到当前状态路径人工智能之

25、搜索培训讲义第53页回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前状态表（逆向）返回值：从当前状态到目标状态路径（以规则表形式表示）或FAIL。人工智能之搜索培训讲义第54页回溯搜索算法11,DATA:=FIRST(DATALIST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,

26、LOOP:IF NULL(RULES)RETURN FAIL;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,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);人工智能之搜索培训讲义第56页一些深入问题n失败原因分析、多步回溯QQ人工智能之搜索培训讲义第57页一些深入问题（续）n回溯搜索中知识利用基本思

27、想：尽可能选取划去对角线上位置数最少。QQQQ4334人工智能之搜索培训讲义第58页 图搜索策略n问题引出n回溯搜索：只保留从初始状态到当前状态一条路径。n图搜索：保留全部已经搜索过路径。人工智能之搜索培训讲义第59页一些基本概念n节点深度：根节点深度=0其它节点深度=父节点深度+10123人工智能之搜索培训讲义第60页一些基本概念（续1）n路径设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1含有一个后继节点ni，则该序列称为从n0到nk路径。n路径耗散值一条路径耗散值等于连接这条路径各节点间全部耗散值总和。用C(ni,nj)表示从ni到nj路径耗散值。人工智能之搜索培训讲义

28、第61页一些基本概念（续1）n扩展一个节点生成出该节点全部后继节点，并给出它们之间耗散值。这一过程称为“扩展一个节点”。人工智能之搜索培训讲义第62页图搜索普通过程n(1)建立一个只含有起始节点S搜索图G，把S放到一个叫做OPEN未扩展节点表中（简称OPEN表）。n(2)建立一个叫做CLOSED已扩展节点表（简称CLOSED表），其初始为空表。n(3)LOOP：若OPEN表是空表，则失溃退出。n(4)选择OPEN表上第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点编号。n(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S

29、这条路径而得到(指针将在第7步中设置)。人工智能之搜索培训讲义第63页n(6)扩展节点n，同时生成不是n祖先那些后继节点集合M。把M这些组员作为n后继节点添入图G中。n(7)对那些未曾在G中出现过(既未曾在OPEN表上或CLOSED表上出现过)M组员设置一个通向n指针。把M这些组员加进OPEN表。对已经在OPEN或CLOSED表上每一个M组员，确定是否需要更改通到n指针方向。对已在CLOSED表上每个M组员，确定是否需要更改图G中通向它每个后代节点指针方向。n(8)按某一任意方式或按某个探试值，重排OPEN表。n(9)GO LOOP。人工智能之搜索培训讲义第64页nOPEN表n节点n父节点nC

30、LOSED表n标号n节点n父节点OPEN表节点节点父节点编号父节点编号CLOSED表编号编号节点节点父节点编号父节点编号人工智能之搜索培训讲义第65页例子n例子：从某王姓家族四代中找王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：寿命51n若X=57，怎样寻找？人工智能之搜索培训讲义第66

31、页问题搜索树人工智能之搜索培训讲义第67页n深度优先搜索搜索过程无信息图搜索过程深度优先人工智能之搜索培训讲义第68页重排九宫深度优先n只是搜索树一部分，还未抵达目标节点，仍需继续往下搜索。人工智能之搜索培训讲义第69页有界深度优先搜索搜索过程n假如问题有解，且其路径长度dm，则搜索过程就得不到解。-深度界限选择很主要。人工智能之搜索培训讲义第70页有界深度优先搜索n设深度界度dm=4，有界深度优先搜索求解图以下，解路径为S020252628(Sg)人工智能之搜索培训讲义第71页深度优先搜索性质n普通不能确保找到最优解n当深度限制不合理时，可能找不到解，能够将算法改为可变深度限制n最坏情况时，

32、搜索空间等同于穷举n与回溯法差异：图搜索n是一个通用与问题无关方法人工智能之搜索培训讲义第72页无信息图搜索过程宽度优先n宽度优先搜索过程：n(1)把起始节点放到OPEN表中(假如该起始节点为一目标节点，则求得一个解答)。n(2)假如OPEN是个空表，则没有解，失溃退出；不然继续。n(3)把OPEN表中第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。n(4)考查节点n是否为目标节点，若是则求得问题解，退出，n(5)若节点n不可扩展，则转第(2)步。n(6)扩展节点n。将其全部后继节点放到OPEN表末末端端，并为每个后续节点都配置指向n指针。然后转向第(2)步。人工智能

33、之搜索培训讲义第73页宽度优先人工智能之搜索培训讲义第74页重排九宫宽度优先n解路径：S0381626人工智能之搜索培训讲义第75页宽度优先搜索性质n只要问题有解，一定能找到解，而且得到是路径最短解。n盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，所以搜索效率低。n方法与问题无关，含有通用性n属于图搜索方法人工智能之搜索培训讲义第76页非启发式搜索n按照事先要求路线进行搜索n广度优先搜索是按“层”进行搜索，先进入OPEN 表节点先被考查n深度优先搜索是沿着纵深方向进行搜索，后进入OPEN表节点先被考查n按已经付出代价决定下一步要搜索节点（为树中每条边赋予代价，广度及深度优先搜索

34、实质是每条边代价都为1）n代价树广度优先n代价树深度优先人工智能之搜索培训讲义第77页代价树宽度忧先搜索n边上标有代价(或费用)树称为代价树。n在代价树中，若用g(x)表示从初姑节点S0到节点x代价，用c(xl,x2)表示从父节点x1到子节点x2代价，则有：g(x2)=g(x1)+c(x1,x2)n 代价树宽度优先搜索基本思想是：OPEN表中节点在任一时刻都是按其代价从小到大排序，每次扩展时总是从OPEN表中选取代价最小节点进行扩展。其搜索过程以下：人工智能之搜索培训讲义第78页n五城市间交通路线图，A城市是出发地，E城市是目标地，两城市间交道费用(代价)如左图小数字所表示。求从A到E最小费用

35、交通路线。n交通代价树如右图，解为ACDE代价树宽度优先搜索举例人工智能之搜索培训讲义第79页代价树深度忧先搜索n代价树宽度优先搜索中，每次扩展时总是从OPEN表中选取代价最小节点进行扩展。而代价树深度优先搜索是从刚扩展出子节点中选一个代价最小节点送入CLOSE表中进行考查。n其搜索过程以下：解也为ACDE人工智能之搜索培训讲义第80页启发式图搜索n利用知识来引导搜索，到达降低搜索范围，降低问题复杂度目标。n启发性信息n用于指导搜索过程，且与详细问题求解相关控制性信息称为启发性信息n启发信息强度n强：降低搜索工作量，但可能造成找不到最 优解n弱：普通造成工作量加大，极限情况下变为 盲目搜索，但

36、可能能够找到最优解人工智能之搜索培训讲义第81页希望：n引入启发知识，在确保找到最正确解情况下，尽可能降低搜索范围，提升搜索效率。人工智能之搜索培训讲义第82页基本思想n定义一个评价函数f，对当前搜索状态进行评定，找出一个最有希望节点来扩展。人工智能之搜索培训讲义第83页1，启发式搜索算法A（A算法）n评价函数格式：f(n)=g(n)+h(n)f(n)：评价函数g(n):实际已经付出代价函数h(n)：启发函数人工智能之搜索培训讲义第84页符号意义ng*(n)：从s(初始状态S0)到n(当前状态Sn)最短路径耗散值nh*(n)：从n到g(目标状态Sg)最短路径耗散值nf*(n)=g*(n)+h*

37、(n)：从s经过n到g最短路径耗散值ng(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)=4 2831647512345768人工智能之搜索培训讲义第87页28316475283147652831647528316475231847652831476528314765283714

38、65832147652318476523184765123847651238476512378465s(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*算法）n在A算法中，假如满足条件：h(n)h*(n)则A算法称为A*算法。其中h*(n)是从顶点Sn到Sg最小代价。n因为h*(n)最小代价通常不知道，所以用h(n)（不在位将牌数）进行代价预计，所以可得h(n)=f1283164751

39、2345768将牌1：1将牌2：1将牌6：1将牌8：2人工智能之搜索培训讲义第90页A*算法性质定理1：对有限图，假如从初始节点s到目标节点t有路径存在，则算法A一定成功结束。人工智能之搜索培训讲义第91页nAO*算法是A*算法在与或图上扩展算法。nAO*算法中因为与节点存在，解对应不是一条路径，而是一个子图，所以对顶点评定实际上是对局部解图评价。n与节点代价计算：n最大代价n和代价n或节点代价计算：最小代价AO*算法人工智能之搜索培训讲义第92页AO*算法举例7=3+1(左树)+2+18=3+1+3+18=min(8+1,7+1)人工智能之搜索培训讲义第93页与或树宽度优先与深度优先搜索n宽

40、度优先：12345n深度优先：13B524人工智能之搜索培训讲义第94页问题n图搜索是针对什么知识表示方法问题求解方法？n什么是图搜索?其中，重排OPEN表意味着什么，重排标准是什么?n宽度优先搜索方法中OPEN表需要按什么方式进行操作nA先进后出 B先进先出n有界深度优先搜索方法能够确保在搜索树中找到一条通向目标节点最短路径吗？n试比较各种盲目搜索搜索方法效率，找出影响算法效率原因n试比较宽度优先搜索、有界深度优先搜索及有序搜索搜索效率，并以实例数据加以说明人工智能之搜索培训讲义第95页启发式搜索必要性n 现实困难迫使人们转而求援于启发式算法。这种算法本质是部分地放弃算法“普通化,通用化”概

41、念,把所要解问题详细领域知识加进算法中去,以提升算法效率。n如,广度优先法几乎能够用于解一切搜索问题：九宫图(八数码难题),hanoi塔(焚塔问题),旅行推销员,华容道,以至魔方等等。但实际使用时,效率可能低得惊人,甚至根本解不出来(比如魔方问题)。n假如我们为每类问题找出一些特殊规则,和广度优先法配合起来使用,那结果就可能完全不一样了。人工智能之搜索培训讲义第96页启发式搜索必要性n依据启发信息,在生成各种搜索树时能够考虑种种可能选择,如:n1.下一步展开哪个节点?n2.是部分展开还是完全展开?n3.使用哪个规则(或算子)?n4.怎样决定舍弃还是保留新生成节点?n5.怎样决定舍弃还是保留一棵

42、子树?n6.怎样决定停顿或继续搜索?n7.怎样定义启发函数(评价函数)?n8.怎样决定搜索方向?n 因为这些选择不一样,就得到了不一样启发式算法人工智能之搜索培训讲义第97页*解路径如粗线所标左、上、右、下*S、A、B、L、M等为状态空间图中各个节点名,其后小括号中数字表示该节点评价函数f(n)预计值,比如S(4)、L(5)等。*图中标识节点为被扩节点,标识节点为生成节点。九宫重排问题人工智能之搜索培训讲义第98页搜索效率比较人工智能之搜索培训讲义第99页启发式搜索策略n人工智能问题求解者在两种基本情况下利用启发式策略:n一个问题因为在问题陈说和数据获取方面固有含糊性可能使它没有一个确定解。医

43、疗诊疗即是一例。所给出一系列症状可能有多个原因,医生利用启发式搜索来选择最有可能论断并依此产生治疗计划。n一个问题可能有确定解,不过求解过程中计算机代价令人难以接收。在很多问题(如国际象棋)中,状态空间增加尤其快,可能状态数伴随搜索深度呈指数级增加、分解。在这种情况下,穷尽式搜索策略诸如深度优先或广度优先搜索,在一个给定较实际时空内很可能得不到最终解n和创造创造全部规则一样,启发式策略也是极易犯错人工智能之搜索培训讲义第100页图搜索策略n图搜索策略定义n图搜索策略可看作一个在图中寻找路径方法。初始节点和目标节点分别代表初始数据库和满足终止条件数据库。求得把一个数据库变换为另一数据库规则序列问

44、题就等价于求得图中一条路径问题。研究图搜索普通策略，能够给出图搜索过程普通步骤。n图搜索算法中几个主要名词术语n（1）OPEN表与CLOSE表n（2）搜索图与搜索树人工智能之搜索培训讲义第101页你可曾听说过“深蓝”？1997年5月11日，IBM开发“深蓝深蓝”击败了国际象棋冠军卡斯帕罗夫。1980年他取得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁卡斯帕罗夫成为历史上最年轻国 际象棋冠军积分是2849，这一分数是有史以来最高分。远远领先于第二位克拉姆尼克2770卡氏何许人也？卡氏何许人也？人工智能之搜索培训讲义第102页人工智能之搜索培训讲义第103页电脑棋手：永不停歇挑战

45、！n1988年“深思深思”击败了丹麦特级大师拉森。n1993年“深思深思”第二代击败了丹麦世界优异女棋手小波尔加。人工智能之搜索培训讲义第104页电脑棋手：永不停歇挑战！n“更弗里茨”击败了除了克拉姆尼克之外全部排名世界前十位棋手。n年10月“更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。n201至2月“更年少者”与卡斯帕罗夫在纽约较量，3比3战平。人工智能之搜索培训讲义第105页许多人在努力人工智能之搜索培训讲义第106页机器博弈n20世纪50年代，有些人构想利用机器智能来实现机器与人对弈。n1997年IBM“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。n加拿大阿尔伯塔

46、大学奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定、二人、零和、完备信息游戏世界冠军n西洋双陆棋这么存在非确定原因棋类也有了美国卡内基梅隆大学西洋双陆琪程序BKG这么世界冠军。n对围棋、中国象棋、桥牌、扑克等许各种其它种类游戏博弈研究也正在进行中。人工智能之搜索培训讲义第107页机器博弈基本思想n机器博弈关键思想就是对博弈树节点估值过程和对博弈树搜索过程结合 人工智能之搜索培训讲义第108页博弈树n在博弈任何一个中间阶段，站在博弈双方其中一方立场上，能够构想一个博弈树。这个博弈树根节点是当前时刻棋局，它儿子节点是假设再行棋一步以后各种棋局，孙子节点是从儿子节点棋局再行

47、棋一步各种棋局，以这类推，结构整棵博弈树，直到能够分出胜败棋局。人工智能之搜索培训讲义第109页机器博弈系统组成n知识表示n规则集，产生机制，构建博弈树n搜索技术n估值技术人工智能之搜索培训讲义第110页博弈搜索n博弈搜索基本思想已经提出半个多世纪，当前广泛研究是确定、二人、零和、完备信息博弈搜索。n没有随机原因博弈在两个人之间进行，在任何一个时刻，一方失去利益即为另一方得到利益，不会出现“双赢”局面，而且在任何时刻，博弈双方都明确知道每一个棋子是否存在和存在于哪里。n二人、零和、完备信息博弈搜索理论已经很系统。极大极小算法是全部搜索算法基础。n一类是作为主流深度优先alpha-beta搜索及

48、其系列增强算法n另一类是最正确优先系列算法。人工智能之搜索培训讲义第111页解谜：电脑是怎样下棋 人机博弈程序普通设计方法以中国棋为例人工智能之搜索培训讲义第112页（1）第一步该做什么？数据结构选取棋盘表示占用空间-少操作速度-快是否方便-方便在机器中表示棋局，让程序知道博弈状态。人工智能之搜索培训讲义第113页九列十行十四种不一样棋子三十二个棋子人工智能之搜索培训讲义第114页几个棋盘表示方式n二维数组直观 紧凑数据结构省空间，不直 观，速度?比特棋盘用于8*8棋盘（国际象 棋），64位主机人工智能之搜索培训讲义第115页（2）接下来怎么办？n产生正当走步规则，使博弈能公正进行，而且能够判

49、断对手是否乱走。依赖于详细棋类特征。n是一段将局面全部可能正确走法罗列出来程序。称之为走法产生。人工智能之搜索培训讲义第116页几个走法产生实现方式n普通做法 建立小型数据库 位运算人工智能之搜索培训讲义第117页位运算走法产生之例寻找象可走步人工智能之搜索培训讲义第118页位运算走法产生之要求n一个基于比特棋盘完善数据库n该数据库应位于内存中人工智能之搜索培训讲义第119页（3）终于到关键了从全部走法中找出最正确走法，也就是搜索人工智能之搜索培训讲义第120页博弈概述 n诸以下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很各种，我们讨论最简单二人零和、全信息、非偶然博弈，其特征以

50、下：(1)对垒MAX、MIN双方轮番采取行动，博弈结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。(2)在对垒过程中，任何一方都了解当前格局及过去历史。(3)任何一方在采取行动前都要依据当前实际情况，进行得失分析，选取对自已为最有利而对对方最为不利对策，不存在掷骰子之类碰运气原因。即双方都是很理智地决定自己行动。人工智能之搜索培训讲义第121页博弈概述n在博弈过程中，任何一方都希望自己取得胜利。所以，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利那个行动方案。此时，假如我们站在MAX方立场上，则可供MAX方选择若干行动方案之间是或关系，因