人工智能之搜索16333703.pptx

人工智能导论 第二章：搜索、问题求解与博弈第二章 搜索、问题求解与博弈n问题求解能力是人类智能的基本组成部分，研究并实现问题求解是人工智能的重要研究内容之一。n知识（问题）的表示是问题求解的基础，两种普遍采用的问题表示方法：n状态空间表示n与或图表示n搜索（优化）：在问题表示基础上，在合理的时间范围内，从问题所有可能的解中找到一个最优解或可行解，是问题求解中的核心技术。n启发式搜索-人工智能的本质特征之一。n计算机博弈涉及问题表示、搜索技术等AI核心问题，现有的计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。主要内容n2.1 搜索概述n2.2 问题求解n2.2.1 状态空间n2.2.2 与或图n2.3 搜索技术n图搜索n2.4 机器博弈一些例子n搭积木n智力游戏：n有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：n船太小，农夫每次只能带一样东西过河n没有农夫看管，则狼要吃羊，羊要吃菜n请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。n类似问题：野人和传教士问题n下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）2.1 搜索概述n人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程n问题求解过程实际上就是一个搜索过程n最优性和计算法复杂性是搜索中的一对矛盾，搜索必须考虑的三个问题：n采用盲目搜索还是启发式搜索n盲目搜索：不考虑问题本身的特性，通过遍历问题解的集合来寻找可行解或最优解。n启发式搜索：利用与问题有关的启发式信息来确定搜索方向，以加快搜索过程。n进行局部搜索还是全集搜索n搜索可行解还是最优解2.1 搜索概述n评价一个搜索算法的因素：n完备性：如果问题有解，一定能找到一个解n最优性：如果问题存在最优解，则一定能找到这个最优解n复杂性：时间和空间复杂性，在保证最优性和完备性的前提下，算法的复杂性越小越好。n目前的搜索算法还不能同时满足以上三个要求。n为了进行搜索，首先必须用某种形式把问题表示出来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程的两种常用方法。2.2 问题求解n状态空间表示法和与或图表示法不仅是问题表示的方法，也分别代表了两种问题求解的思路n状态空间将问题求解所涉及的每个可能的步骤表示成一个状态，全部状态以及状态之间的所有转换构成一个以图的形式表示的状态空间。问题的求解过程是在状态空间中搜索搜索一条最优的或可行的从初始状态到目标状态的路径的过程。n与或图表示法的基础是问题归约，通过一系列分解或变换，将复杂问题逐步转化为比较简单的问题，直至可以直接求解的本原问题。与或图的求解过程是在与或图中搜索搜索一个将原始问题变换为简单问题在变换为本原问题的、最优的或可行的归约步骤的过程。2.2.1 状态空间表示法n状态空间表示法是用“状态”和“算子”来表示问题的一种方法n状态：用来描述问题求解过程中不同时刻的状况n算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态n当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解2.2.1 状态空间表示法n状态n状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK(SK0,SK1,)n当给每一分量以确定的值时，就得到一个具体的状态n算子n引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子n状态空间n由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示:(S,F,C,I,G)nS:所有状态构成的集合nF:用于状态转换的算子的集合nC:状态转换代价的聚合nI:初始状态的集合nG:目标状态的集合例:二阶Hanoi Tower（梵塔）问题n设有三根柱子，在1号柱于上穿有A、B两个盘片，盘A小于盘B，盘A位于盘B的上面。要求把这两个盘片全部移到另一根柱子上，而且规定每次只能移动一片，任何时刻都不能使盘B位于盘A的上面。n设SK=(SK0,SK1)表示问题的状态，SK0 表示盘片A所在的柱号，SK1 表示盘片B所在的柱号n全部可能的状态:nS0=(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)例:二阶Hanoi Tower（梵塔）问题n9种状态，12种算子构成的状态空间转移图：2.2.1 状态空间表示法n总结：n用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还安定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。n问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到问题的一个解：从初始状态到目标状态所用算符构成的序列。n算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算特序列都可使问题从初始状态变到目标状态，这就得到了多个解。把使用算符最少的解称为最优解。n对任何一个状态，可使用的算符可能不止一个，因而由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。2.2.1状态空间表示法n基于状态空间表示的问题求解算法nStep1：确定问题状态的计算机描述形式，将所有可能的状态表示出来，并确定其中的初始状态和目标状态。nStep2：确定促使状态发生转换的操作，并在计算机中将其表示为相应的算符。nStep3：以状态为顶点，状态之间所允许的操作为有向边，获得图形式的状态空间。nStep4：应用图搜索方法，在状态空间中搜索从初始状态到目标状态的最优路径或可行路径。例:三阶Hanoi Tower（梵塔）问题例:三阶Hanoi Tower（梵塔）问题例:三阶Hanoi Tower（梵塔）问题2.2.2 与或图表示法n也称为问题归约方法：把初始问题通过一系列交换最终变为一个子问题集合，而这些于问题的解可以直接得到，从而解答了初始问题。n分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。n问题的分解可以用图表示出来，称为与树。例如，把问题P分解为三个子问题P1、P2和P3，可以表示为下图：2.2.2 与或图表示法n等价变换：利用同构或同态的等价变换，把它变换成若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。n问题的等价变换过程也可用一个图表示出来，称为“或”树。n与或树的结合称为与或图（树）。2.2.2 与或图表示法n本原问题：不能再分解或变换，而且直接可解的子问题称为本原问题。n端节点与终止节点：在与或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。n可解节点：在与或树今，满足下列条件之一的节点：n1)它是一个终止节点。n2)它是一个“或”节点，且其子节点至少有一个是可解节点。n3)它是一个“与”节点，且其子节点全部是可解节点。n不可解节点：上面三个条件全不满足的节点。n解树：由可解节点所构成的，并且由这些可解节点可推出初始节点(它对应于原始问题)为可解节点的子树称为解树。在解树中定包含初始节点。例:三阶Hanoi Tower（梵塔）问题n设有A、B、C三个盘片以及三根柱子，三个盘片按从小到大的顺序穿在1号柱上，要求把它们全部移到3号柱上，而且每次只能移动一个盘片，任何时刻都不能把大的盘片压在小的盘片上面，如图所示。例:三阶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)又分别可分解为三个子问题例:三阶Hanoi Tower（梵塔）问题n定义问题状态表示：设三元组(i,j,k)表示状态，其中i表示盘片C所在的柱号,j表示盘片B所在的柱号；k表示盘片A所在的柱号。n初始问题可表示为：(1、11)(3，3，3)n与或树表示如图所示。(把图中7个终止节点(本原问题)按从左至右排列，得到了初始问题的解)2.2.2 与或图表示法n基于与或图表示的问题求解算法nStep1：确定单个问题描述形式，可采用状态空间表示法。nStep2：从原始问题开始，逐步进行分解和变换，直到本原问题，然后将全部分解和变换过程表示为与或图。nStep3：从端顶点开始，逐步向上回溯，标注各顶点为可解或不可解顶点，直到标注原始顶点为可解顶点或不可解顶点为止nStep4：当原始顶点被确定为可解顶点时，输出相应解图为问题的解。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(菲克斯)和N.Nilsson(尼尔逊)写的STRIPS(Stanford Research Institute Problem Solver)程序以及A.Samuel(塞缪尔)写的Chechers程序等,都使用了各种搜索技术。n现在,搜索技术渗透在各种人工智能系统中,可以说没有哪一种人工智能的应用不用搜索方法,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。2.3 搜索技术n 搜索问题是AI核心理论问题之一n一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。n搜索方法好的标准,一般认为有两个：n(1)搜索空间小;n(2)解最佳。2.3 搜索技术n 搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。n当所给定的问题用状态空间表示时,则求解过程可归结为对状态空间的搜索。n 当问题有解时,使用不同的搜索策略,找到解的搜索空间范围是有区别的。一般来说,对大空间问题,搜索策略是要解决组合爆炸的问题2.3 搜索策略n 通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式:n一种是不考虑给定问题所具有的特定知识,系统根据事先确定好的某种固定排序,依次调用规则或随机调用规则,这实际上是盲目搜索的方法,一般统称为无信息引导的搜索策略。n另一种是考虑问题领域可应用的知识,动态地确定规则的排序,优先调用较合适的规则使用,这就是通常称为启发式搜索策略或有信息引导的搜索策略。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分枝界限法(Branch and Bound)n动态规划法(Dynamic Programming)n最佳图搜索法(A*)AI领域的搜索方法n(3)求与或关系解图的搜索法n一般与或图搜索法(AO*)n 极小极大法(Minimax)n剪枝法(Alpha-beta Pruning)n 启发式剪枝法(Heuristic Pruning)搜索策略分类盲目搜索方法n盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索。n典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法回溯策略n例：皇后问题n 在一个44的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获 ()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)()(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)()(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)递归的思想从前有座山从前有座山从前有座山Fibonacci数列n1202年，意大利家斐波那契在提出了一个关于兔子繁殖的问题：如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在它出生後的第三个月里，又能开始生一对小兔，假定在不发生死亡的情況下，由一对出生的小兔开始，50個月后会有多少对兔子？n當n1時，Fn+2=Fn+1+Fn，而 F0=F1=1。递归的思想（续）当前状态目标状态g回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN 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);存在问题及解决办法n问题：n深度问题n死循环问题n解决办法：n对搜索深度加以限制n记录从初始状态到当前状态的路径回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法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,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);回溯搜索算法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);一些深入的问题n失败原因分析、多步回溯QQ一些深入问题（续）n回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ4334 图搜索策略n问题的引出n回溯搜索：只保留从初始状态到当前状态的一条路径。n图搜索：保留所有已经搜索过的路径。一些基本概念n节点深度：根节点深度=0其它节点深度=父节点深度+10123一些基本概念（续1）n路径设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。n路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。一些基本概念（续1）n扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。图搜索的一般过程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这条路径而得到的(指针将在第7步中设置)。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。nOPEN表n节点n父节点nCLOSED表n标号n节点n父节点OPEN表节点节点父节点编号父节点编号CLOSED表编号编号节点节点父节点编号父节点编号例子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，如何寻找？问题的搜索树n深度优先搜索的搜索过程无信息图搜索过程深度优先重排九宫深度优先n只是搜索树的一部分，尚未到达目标节点，仍需继续往下搜索。有界深度优先搜索的搜索过程n如果问题有解，且其路径长度dm，则搜索过程就得不到解。-深度界限的选择很重要。有界深度优先搜索n设深度界度dm=4，有界深度优先搜索求解图如下，解的路径为S020252628(Sg)深度优先搜索的性质n一般不能保证找到最优解n当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制n最坏情况时，搜索空间等同于穷举n与回溯法的差别：图搜索n是一个通用的与问题无关的方法无信息图搜索过程宽度优先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)步。宽度优先重排九宫宽度优先n解的路径：S0381626宽度优先搜索的性质n只要问题有解，一定能找到解，而且得到的是路径最短的解。n盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，因此搜索效率低。n方法与问题无关，具有通用性n属于图搜索方法非启发式搜索n按照事先规定的路线进行搜索n广度优先搜索是按“层”进行搜索的，先进入OPEN 表的节点先被考察n深度优先搜索是沿着纵深方向进行搜索的，后进入OPEN表的节点先被考察n按已经付出的代价决定下一步要搜索的节点（为树中的每条边赋予代价，广度及深度优先搜索实质是每条边的代价都为1）n代价树的广度优先n代价树的深度优先代价树的宽度忧先搜索n边上标有代价(或费用)的树称为代价树。n在代价树中，若用g(x)表示从初姑节点S0到节点x的代价，用c(xl,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)n 代价树宽度优先搜索的基本思想是：OPEN表中的节点在任一时刻都是按其代价从小到大排序的，每次扩展时总是从OPEN表中选取代价最小的节点进行扩展。其搜索过程如下：n五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交道费用(代价)如左图小数字所示。求从A到E的最小费用交通路线。n交通代价树如右图，解为ACDE代价树的宽度优先搜索举例代价树的深度忧先搜索n代价树的宽度优先搜索中，每次扩展时总是从OPEN表中选取代价最小的节点进行扩展。而代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入CLOSE表中进行考察。n其搜索过程如下：解也为ACDE启发式图搜索n利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。n启发性信息n用于指导搜索过程，且与具体问题求解有关的控制性信息称为启发性信息n启发信息的强度n强：降低搜索工作量，但可能导致找不到最 优解n弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解希望：n引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。基本思想n定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。1，启发式搜索算法A（A算法）n评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数g(n):实际已经付出的代价函数h(n)：启发函数符号的意义ng*(n)：从s(初始状态S0)到n(当前状态Sn)的最短路径的耗散值nh*(n)：从n到g(目标状态Sg)的最短路径的耗散值nf*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值ng(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值一个A算法的例子定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值,即顶点Sn在状态空间中的深度(从根顶点到Sn所经历的层次数)。h(n)为当前节点“不在位”的将牌数2831647512384765h计算举例h(n)=4 28316475123457682831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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最佳图搜索算法A*（A*算法）n在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。其中h*(n)是从顶点Sn到Sg的最小代价。n由于h*(n)最小代价通常不知道，因此用h(n)（不在位的将牌数）进行代价估计，因此可得h(n)=f12831647512345768将牌1：1将牌2：1将牌6：1将牌8：2A*算法的性质定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。nAO*算法是A*算法在与或图上的扩展算法。nAO*算法中由于与节点的存在，解对应的不是一条路径，而是一个子图，因此对顶点的评估实际上是对局部解图的评价。n与节点代价计算：n最大代价n和代价n或节点的代价计算：最小代价AO*算法AO*算法举例7=3+1(左树)+2+18=3+1+3+18=min(8+1,7+1)与或树的宽度优先与深度优先搜索n宽度优先：12345n深度优先：13B524问题n图搜索是针对什么知识表示方法的问题求解方法？n什么是图搜索?其中，重排OPEN表意味着什么，重排的原则是什么?n宽度优先搜索方法中OPEN表需要按什么方式进行操作nA先进后出 B先进先出n有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗？n试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因n试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据加以说明启发式搜索的必要性n 现实的困难迫使人们转而求援于启发式算法。这种算法的本质是部分地放弃算法“一般化,通用化”的概念,把所要解的问题的具体领域的知识加进算法中去,以提高算法的效率。n如,广度优先法几乎可以用于解一切搜索问题：九宫图(八数码难题),hanoi塔(焚塔问题),旅行推销员,华容道,以至魔方等等。但实际使用时,效率也许低得惊人,甚至根本解不出来(例如魔方问题)。n如果我们为每类问题找出一些特殊规则,和广度优先法配合起来使用,那结果就可能完全不一样了。启发式搜索的必要性n根据启发信息,在生成各种搜索树时可以考虑种种可能的选择,如:n1.下一步展开哪个节点?n2.是部分展开还是完全展开?n3.使用哪个规则(或算子)?n4.怎样决定舍弃还是保留新生成的节点?n5.怎样决定舍弃还是保留一棵子树?n6.怎样决定停止或继续搜索?n7.如何定义启发函数(评价函数)?n8.如何决定搜索方向?n 由于这些选择的不同,就得到了不同的启发式算法*解路径如粗线所标左、上、右、下*S、A、B、L、M等为状态空间图中各个节点名,其后的小括号中数字表示该节点的评价函数f(n)的估计值,例如S(4)、L(5)等。*图中标记节点为被扩的节点,标记的节点为生成的节点。九宫重排问题搜索效率比较启发式搜索策略n人工智能问题求解者在两种基本情况下运用启发式策略:n一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例。所给出的一系列症状可能有多个原因,医生运用启发式搜索来选择最有可能的论断并依此产生治疗计划。n一个问题可能有确定解,但是求解过程中的计算机代价令人难以接受。在很多问题(如国际象棋)中,状态空间的增长特别快,可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下,穷尽式搜索策略诸如深度优先或广度优先搜索,在一个给定的较实际的时空内很可能得不到最终的解n和发明创造的所有规则一样,启发式策略也是极易出错的图搜索策略n图搜索策略的定义n图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。n图搜索算法中的几个重要名词术语n（1）OPEN表与CLOSE表n（2）搜索图与搜索树你可曾听说过“深蓝”？1997年5月11日，IBM开发的“深蓝深蓝”击败了国际象棋冠军卡斯帕罗夫。1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军积分是2849，这一分数是有史以来最高分。远远领先于第二位的克拉姆尼克的2770卡氏何许人也？卡氏何许人也？电脑棋手：永不停歇的挑战！n1988年“深思深思”击败了丹麦特级大师拉森。n1993年“深思深思”第二代击败了丹麦世界优秀女棋手小波尔加。电脑棋手：永不停歇的挑战！n2001年“更弗里茨更弗里茨”击败了除了克拉姆尼克之外的所有排名世界前十位的棋手。n2002年10月“更弗里茨更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。n2003年1至2月“更年少者更年少者”与卡斯帕罗夫在纽约较量，3比3战平。许多人在努力机器博弈n20世纪50年代，有人设想利用机器智能来实现机器与人的对弈。n1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。n加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定的、二人、零和、完备信息游戏世界冠军n西洋双陆棋这样的存在非确定因素的棋类也有了美国卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠军。n对围棋、中国象棋、桥牌、扑克等许多种其它种类游戏博弈的研究也正在进行中。机器博弈的基本思想n机器博弈的核心思想就是对博弈树节点的估值过程和对博弈树搜索过程的结合 博弈树n在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。机器博弈系统的构成n知识表示n规则集，产生机制，构建博弈树n搜索技术n估值技术博弈搜索n博弈搜索的基本思想已经提出半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。n没有随机因素的博弈在两个人之间进行，在任何一个时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个棋子是否存在和存在于哪里。n二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。n一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法n另一类是最佳优先的系列算法。解谜：电脑是怎样下棋的 人机博弈程序的一般设计方法以中国棋为例（1）第一步该做什么？数据结构的选取棋盘表示占用空间-少操作速度-快是否方便-方便在机器中表示棋局，让程序知道博弈状态。九列十行十四种不同的棋子三十二个棋子几种棋盘表示的方式n二维数组直观 紧凑的数据结构省空间，不直 观，速度?比特棋盘用于8*8棋盘（国际象 棋），64位主机（2）接下来怎么办？n产生合法走步的规则，使博弈能公正的进行，并且能够判断对手是否乱走。依赖于具体棋类特征。n是一段将局面所有可能的正确走法罗列出来的程序。称之为走法产生。几种走法产生的实现方式n一般做法 建立小型数据库 位运算位运算走法产生之例寻找象的可走步位运算走法产生之要求n一个基于比特棋盘的完善的数据库n该数据库应位于内存中（3）终于到核心了从所有的走法中找出最佳的走法，也就是博弈概述 n诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的二人零和、全信息、非偶然博弈，其特征如下：(1)对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。(2)在对垒过程中，任何一方都了解当前的格局及过去的历史。(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动。博弈概述n在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是或关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。博弈概述n这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵与或树。描述博弈过程的与或树称为博弈树，它有如下特点：(1)博弈的初始格局是初始节点。(2)在博弈树中，或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系，对方扩展的节点之间是与关系。双方轮流地扩展节点。(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。搜索算法n极大极小值算法极大极小值算法 n负极大值搜索n深度优先的 alpha-beta搜索n渴望搜索（Aspiration Search）n极小窗口搜索（Minimal Window Search）n遍历深化（Iterative Deepening）n历史启发搜索（History Heuristic）n杀手启发搜索杀手启发搜索(Killer Heuristic)nMTD(f)算法（Memory enhanced Test Driver with f and n）极大极小法n基本思想或算法：n(1)设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。n(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。n(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。n(4)当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。n(5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。极大极小倒推值的计算nA是与节点，从下往上可以倒推出S0的估计值一字棋游戏极小极大分析法一字棋游戏极小极大分析法n设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。n用叉号表示MAX，用圆圈代表MIN。一字棋游戏极小极大分析法一字棋游戏极小极大分析法n为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下n设棋局为P，估价函数为e(P)n(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)n(2)若P是MAX必