人工智能之搜索

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能导论 第二章：搜索、问题求解与博弈,第二章 搜索、问题求解与博弈,问题求解能力是人类智能的基本组成部分，研究并实现问题求解是人工智能的重要研究内容之一。,知识（问题）的表示是问题求解的基础，两种普遍采用的问题表示方法：,状态空间表示,与或图表示,搜索（优化）：在问题表示基础上，在合理的时间范围内，从问题所有可能的解中找到一个最优解或可行解，是问题求解中的核心技术。,启发式搜索,-,人工智能的本质特征之一。,计算机博弈涉及问题表示、搜索技术等,AI,核心问题，现有的计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。,主要内容,2.1,搜索概述,2.2,问题求解,2.2.1,状态空间,2.2.2,与或图,2.3,搜索技术,图搜索,2.4,机器博弈,一些例子,搭积木,智力游戏：,有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：,船太小，农夫每次只能带一样东西过河,没有农夫看管，则狼要吃羊，羊要吃菜,请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。,类似问题：野人和传教士问题,下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）,2.1,搜索概述,人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个,“,问题求解,”,过程,问题求解过程实际上就是一个搜索过程,最优性和计算法复杂性是搜索中的一对矛盾，搜索必须考虑的三个问题：,采用盲目搜索还是启发式搜索,盲目搜索：不考虑问题本身的特性，通过遍历问题解的集合来寻找可行解或最优解。,启发式搜索：利用与问题有关的启发式信息来确定搜索方向，以加快搜索过程。,进行局部搜索还是全集搜索,搜索可行解还是最优解,2.1,搜索概述,评价一个搜索算法的因素：,完备性：如果问题有解，一定能找到一个解,最优性：如果问题存在最优解，则一定能找到这个最优解,复杂性：时间和空间复杂性，在保证最优性和完备性的前提下，算法的复杂性越小越好。,目前的搜索算法还不能同时满足以上三个要求。,为了进行搜索，首先必须用某种形式把问题表示出来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程的两种常用方法。,2.2,问题求解,状态空间表示法和与或图表示法不仅是问题表示的方法，也分别代表了两种问题求解的思路,状态空间将问题求解所涉及的每个可能的步骤表示成一个状态，全部状态以及状态之间的所有转换构成一个以图的形式表示的状态空间。问题的求解过程是在状态空间中,搜索,一条最优的或可行的从初始状态到目标状态的路径的过程。,与或图表示法的基础是问题归约，通过一系列分解或变换，将复杂问题逐步转化为比较简单的问题，直至可以直接求解的本原问题。与或图的求解过程是在与或图中,搜索,一个将原始问题变换为简单问题在变换为本原问题的、最优的或可行的归约步骤的过程。,2.2.1,状态空间表示法,状态空间表示法是用,“,状态,”,和,“,算子,”,来表示问题的一种方法,状态：用来描述问题求解过程中不同时刻的状况,算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态,当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解,2.2.1,状态空间表示法,状态,状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：,S,K,(S,K0,S,K1,),当给每一分量以确定的值时，就得到一个具体的状态,算子,引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子,状态空间,由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示,: (S,F,C,I,G),S:,所有状态构成的集合,F:,用于状态转换的算子的集合,C:,状态转换代价的聚合,I:,初始状态的集合,G:,目标状态的集合,例,:,二阶,Hanoi Tower,（梵塔）问题,设有三根柱子，在,1,号柱于上穿有,A,、,B,两个盘片，盘,A,小于盘,B,，盘,A,位于盘,B,的上面。要求把这两个盘片全部移到另一根柱子上，而且规定每次只能移动一片，任何时刻都不能使盘,B,位于盘,A,的上面。,设,S,K,=(S,K0,S,K1,),表示问题的状态，,S,K0,表示盘片,A,所在的柱号，,S,K1,表示盘片,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),例,:,二,阶,阶,HanoiTower,（,梵,梵,塔,塔,）,）,问,问,题,题,9,种,状,状,态,态,，,，,12,种,算,算,子,子,构,构,成,成,的,的,状,状,态,态,空,空,间,间,转,转,移,移,图,图,：,：,状,态,态,空,空,间,间,表,表,示,示,法,法,总,结,结,：,：,用,状,状,态,态,空,空,间,间,方,方,法,法,表,表,示,示,问,问,题,题,时,时,，,，,首,首,先,先,必,必,须,须,定,定,义,义,状,状,态,态,的,的,描,描,述,述,形,形,式,式,，,，,通,通,过,过,使,使,用,用,这,这,种,种,描,描,述,述,形,形,式,式,可,可,把,把,问,问,题,题,的,的,一,一,切,切,状,状,态,态,都,都,表,表,示,示,出,出,来,来,。,。,其,其,次,次,，,，,还,还,安,安,定,定,义,义,一,一,组,组,算,算,符,符,，,，,通,通,过,过,使,使,用,用,算,算,符,符,可,可,把,把,问,问,题,题,由,由,一,一,种,种,状,状,态,态,转,转,变,变,为,为,另,另,一,一,种,种,状,状,态,态,。,。,问,题,题,的,的,求,求,解,解,过,过,程,程,是,是,一,一,个,个,不,不,断,断,把,把,算,算,符,符,作,作,用,用,于,于,状,状,态,态,的,的,过,过,程,程,。,。,如,如,果,果,在,在,使,使,用,用,某,某,个,个,算,算,符,符,后,后,得,得,到,到,的,的,新,新,状,状,态,态,是,是,目,目,标,标,状,状,态,态,，,，,就,就,得,得,到,到,问,问,题,题,的,的,一,一,个,个,解,解,：,：,从,从,初,初,始,始,状,状,态,态,到,到,目,目,标,标,状,状,态,态,所,所,用,用,算,算,符,符,构,构,成,成,的,的,序,序,列,列,。,。,算,符,符,的,的,一,一,次,次,使,使,用,用,，,，,就,就,使,使,问,问,题,题,由,由,一,一,种,种,状,状,态,态,转,转,变,变,为,为,另,另,一,一,种,种,状,状,态,态,。,。,可,可,能,能,有,有,多,多,个,个,算,算,特,特,序,序,列,列,都,都,可,可,使,使,问,问,题,题,从,从,初,初,始,始,状,状,态,态,变,变,到,到,目,目,标,标,状,状,态,态,，,，,这,这,就,就,得,得,到,到,了,了,多,多,个,个,解,解,。,。,把,把,使,使,用,用,算,算,符,符,最,最,少,少,的,的,解,解,称,称,为,为,最,最,优,优,解,解,。,。,对,任,任,何,何,一,一,个,个,状,状,态,态,，,，,可,可,使,使,用,用,的,的,算,算,符,符,可,可,能,能,不,不,止,止,一,一,个,个,，,，,因,因,而,而,由,由,一,一,个,个,状,状,态,态,所,所,生,生,成,成,的,的,后,后,继,继,状,状,态,态,就,就,可,可,能,能,有,有,多,多,个,个,。,。,当,当,对,对,这,这,些,些,后,后,继,继,状,状,态,态,使,使,用,用,算,算,子,子,生,生,成,成,更,更,进,进,一,一,步,步,状,状,态,态,时,时,，,，,首,首,先,先,应,应,对,对,哪,哪,一,一,状,状,态,态,进,进,行,行,操,操,作,作,呢,呢,？,？,这,这,取,取,决,决,于,于,搜,搜,索,索,策,策,略,略,，,，,不,不,同,同,搜,搜,索,索,策,策,略,略,的,的,操,操,作,作,顺,顺,序,序,是,是,不,不,相,相,同,同,的,的,。,。,状,态,态,空,空,间,间,表,表,示,示,法,法,基,于,于,状,状,态,态,空,空,间,间,表,表,示,示,的,的,问,问,题,题,求,求,解,解,算,算,法,法,Step1,：,确,确,定,定,问,问,题,题,状,状,态,态,的,的,计,计,算,算,机,机,描,描,述,述,形,形,式,式,，,，,将,将,所,所,有,有,可,可,能,能,的,的,状,状,态,态,表,表,示,示,出,出,来,来,，,，,并,并,确,确,定,定,其,其,中,中,的,的,初,初,始,始,状,状,态,态,和,和,目,目,标,标,状,状,态,态,。,。,Step2,：,确,确,定,定,促,促,使,使,状,状,态,态,发,发,生,生,转,转,换,换,的,的,操,操,作,作,，,，,并,并,在,在,计,计,算,算,机,机,中,中,将,将,其,其,表,表,示,示,为,为,相,相,应,应,的,的,算,算,符,符,。,。,Step3,：,以,以,状,状,态,态,为,为,顶,顶,点,点,，,，,状,状,态,态,之,之,间,间,所,所,允,允,许,许,的,的,操,操,作,作,为,为,有,有,向,向,边,边,，,，,获,获,得,得,图,形,式,式,的,的,状,状,态,态,空,空,间,间,。,。,Step4,：,应,应,用,用,图,图,搜,搜,索,索,方,方,法,法,，,，,在,在,状,状,态,态,空,空,间,间,中,中,搜,搜,索,索,从,从,初,初,始,始,状,状,态,态,到,到,目,目,标,标,状,状,态,态,的,的,最,最,优,优,路,路,径,径,或,或,可,可,行,行,路,路,径,径,。,。,例,:,三,阶,阶,HanoiTower,（,梵,梵,塔,塔,）,）,问,问,题,题,例,:,三,阶,阶,HanoiTower,（,梵,梵,塔,塔,）,）,问,问,题,题,例,:,三,阶,阶,HanoiTower,（,梵,梵,塔,塔,）,）,问,问,题,题,与,或,或,图,图,表,表,示,示,法,法,也,称,称,为,为,问,问,题,题,归,归,约,约,方,方,法,法,：,：,把,把,初,初,始,始,问,问,题,题,通,通,过,过,一,一,系,系,列,列,交,交,换,换,最,最,终,终,变,变,为,为,一,一,个,个,子,子,问,问,题,题,集,集,合,合,，,，,而,而,这,这,些,些,于,于,问,问,题,题,的,的,解,解,可,可,以,以,直,直,接,接,得,得,到,到,，,，,从,从,而,而,解,解,答,答,了,了,初,初,始,始,问,问,题,题,。,。,分,解,解,：,：,把,把,一,一,个,个,复,复,杂,杂,问,问,题,题,分,分,解,解,为,为,若,若,干,干,个,个,较,较,为,为,简,简,单,单,的,的,子,子,问,问,题,题,，,，,每,每,个,个,子,子,问,问,题,题,又,又,可,可,继,继,续,续,分,分,解,解,为,为,若,若,干,干,个,个,更,更,为,为,简,简,单,单,的,的,子,子,问,问,题,题,。,。,重,重,复,复,此,此,过,过,程,程,，,，,直,直,到,到,不,不,需,需,要,要,再,再,分,分,解,解,或,或,者,者,不,不,能,能,再,再,分,分,解,解,为,为,止,止,。,。,然,然,后,后,对,对,每,每,个,个,子,子,问,问,题,题,分,分,别,别,进,进,行,行,求,求,解,解,，,，,最,最,后,后,把,把,各,各,子,子,问,问,题,题,的,的,解,解,复,复,合,合,起,起,来,来,就,就,得,得,到,到,了,了,原,原,问,问,题,题,的,的,解,解,。,。,问,题,题,的,的,分,分,解,解,可,可,以,以,用,用,图,图,表,表,示,示,出,出,来,来,，,，,称,称,为,为,与,与,树,树,。,。,例,例,如,如,，,，,把,把,问,问,题,题,P,分,解,解,为,为,三,三,个,个,子,子,问,问,题,题,P1,、,P2,和,P3,，,可,可,以,以,表,表,示,示,为,为,下,下,图,图,：,：,与,或,或,图,图,表,表,示,示,法,法,等,价,价,变,变,换,换,：,：,利,利,用,用,同,同,构,构,或,或,同,同,态,态,的,的,等,等,价,价,变,变,换,换,，,，,把,把,它,它,变,变,换,换,成,成,若,若,干,干,个,个,较,较,容,容,易,易,求,求,解,解,的,的,新,新,问,问,题,题,。,。,若,若,新,新,问,问,题,题,中,中,有,有,一,一,个,个,可,可,求,求,解,解,，,，,则,则,就,就,得,得,到,到,了,了,原,原,问,问,题,题,的,的,解,解,。,。,问,题,题,的,的,等,等,价,价,变,变,换,换,过,过,程,程,也,也,可,可,用,用,一,一,个,个,图,图,表,表,示,示,出,出,来,来,，,，,称,称,为,为,“,或,”,树,。,。,与,或,或,树,树,的,的,结,结,合,合,称,称,为,为,与,与,或,或,图,图,（,（,树,树,）,）,。,。,与,或,或,图,图,表,表,示,示,法,法,本,原,原,问,问,题,题,：,：,不,不,能,能,再,再,分,分,解,解,或,或,变,变,换,换,，,，,而,而,且,且,直,直,接,接,可,可,解,解,的,的,子,子,问,问,题,题,称,称,为,为,本,本,原,原,问,问,题,题,。,。,端,节,节,点,点,与,与,终,终,止,止,节,节,点,点,：,：,在,在,与,与,或,或,树,树,中,中,，,，,没,没,有,有,子,子,节,节,点,点,的,的,节,节,点,点,称,称,为,为,端,端,节,节,点,点,；,；,本,本,原,原,问,问,题,题,所,所,对,对,应,应,的,的,节,节,点,点,称,称,为,为,终,终,止,止,节,节,点,点,。,。,显,显,然,然,，,，,终,终,止,止,节,节,点,点,一,一,定,定,是,是,端,端,节,节,点,点,，,，,但,但,端,端,节,节,点,点,不,不,一,一,定,定,是,是,终,终,止,止,节,节,点,点,。,。,可,解,解,节,节,点,点,：,：,在,在,与,与,或,或,树,树,今,今,，,，,满,满,足,足,下,下,列,列,条,条,件,件,之,之,一,一,的,的,节,节,点,点,：,：,1),它,是,是,一,一,个,个,终,终,止,止,节,节,点,点,。,。,2),它,是,是,一,一,个,个,“,或,”,节,点,点,，,，,且,且,其,其,子,子,节,节,点,点,至,至,少,少,有,有,一,一,个,个,是,是,可,可,解,解,节,节,点,点,。,。,3),它是一,个,个,“,与,”,节点，,且,且其子,节,节点全,部,部是可,解,解节点,。,。,不可解,节,节点：,上,上面三,个,个条件,全,全不满,足,足的节,点,点。,解树：,由,由可解,节,节点所,构,构成的,，,，并且,由,由这些,可,可解节,点,点可推,出,出初始,节,节点,(,它对应,于,于原始,问,问题,),为可解,节,节点的,子,子树称,为,为解树,。,。在解,树,树中,定包含,初,初始节,点,点。,例,:,三阶,HanoiTower,（梵塔,）,）问题,设有,A,、,B,、,C,三个盘,片,片以及,三,三根柱,子,子，三,个,个盘片,按,按从小,到,到大的,顺,顺序穿,在,在,1,号柱上,，,，要求,把,把它们,全,全部移,到,到,3,号柱上,，,，而且,每,每次只,能,能移动,一,一个盘,片,片，任,何,何时刻,都,都不能,把,把大的,盘,盘片压,在,在小的,盘,盘片上,面,面，如,图,图所示,。,。,例,:,三阶,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),又分别,可,可分解,为,为三个,子,子问题,例,:,三阶,HanoiTower,（梵塔,）,）问题,定义问,题,题状态,表,表示：,设,设三元,组,组,(i,j,k),表示状,态,态，其,中,中,i,表示盘,片,片,C,所在的,柱,柱号,j,表示盘,片,片,B,所在的,柱,柱号；,k,表示盘,片,片,A,所在的,柱,柱号。,初始问,题,题可表,示,示为：,(1,、,1,1)(3,，,3,，,3),与或,树,树表示,如,如图所,示,示。,(,把图中,7,个终止,节,节点,(,本原问,题,题,),按从左,至,至右排,列,列，得,到,到了初,始,始问题,的,的解,),与或图,表,表示法,基于与,或,或图表,示,示的问,题,题求解,算,算法,Step1,： 确,定,定单个,问,问题描,述,述形式,，,，可采,用,用状态,空,空间表,示,示法。,Step2,：从原,始,始问题,开,开始，,逐,逐步进,行,行分解,和,和变换,，,，直到,本,本原问,题,题，然,后,后将全,部,部分解,和,和变换,过,过程表,示,示为与,或,或图。,Step3,：从端,顶,顶点开,始,始，逐,步,步向上,回,回溯，,标,标注各,顶,顶点为,可,可解或,不,不可解,顶,顶点，,直,直到标,注,注原始,顶,顶点为,可,可解顶,点,点或不,可,可解顶,点,点为止,Step4,：当原,始,始顶点,被,被确定,为,为可解,顶,顶点时,，,，输出,相,相应解,图,图为问,题,题的解,。,。,2.3,搜索技,术,术,搜索技,术,术是人,工,工智能,的,的基本,技,技术之,一,一,在人工,智,智能各,应,应用领,域,域中被,广,广泛地,使,使用。,早期的,人,人工智,能,能程序,与,与搜索,技,技术联,系,系就更,为,为紧密,，,，几乎,所,所有的,早,早期的,人,人工智,能,能程序,都,都是以,搜,搜索为,基,基础的,。,。例如,，,，,A.Newell(,艾伦,纽厄尔,),和,H,A,Simon(,西蒙,),等人编,写,写的,LT(LogicTheorist),程序, J.Slagle,写的符,号,号积分,程,程序,SAINT,A,Newell,和,H,A,Simon,写的,GPS(GeneralProblem Solver),程序, H,Gelernter(,格伦特,尔,尔,),写的,Geometrytheorem-provingmachine,程序, R.Fikes(,菲克斯,),和,N.Nilsson(,尼尔逊,),写的,STRIPS(StanfordResearchInstitute ProblemSolver),程序以,及,及,A.Samuel(,塞缪尔,),写的,Chechers,程序等,都使用,了,了各种,搜,搜索技,术,术。,现在,搜索技,术,术渗透,在,在各种,人,人工智,能,能系统,中,中,可以说,没,没有哪,一,一种人,工,工智能,的,的应用,不,不用搜,索,索方法,在专家,系,系统、,自,自然语,言,言理解,、,、自动,程,程序设,计,计、模,式,式识别,、,、机器,人,人学、,信,信息检,索,索和博,弈,弈都广,泛,泛使用,搜,搜技术,。,。,2.3,搜索技,术,术,搜索问,题,题是,AI,核心理,论,论问题,之,之一,一般一,个,个问题,可,可以用,好,好几种,搜,搜索技,术,术解决,选择一,种,种好的,搜,搜索技,术,术对解,决,决问题,的,的效率,很,很有关,系,系,甚至关,系,系到求,解,解问题,有,有没有,解,解。,搜索方,法,法好的,标,标准,一般认,为,为有两,个,个：,(1),搜索空,间,间小,;,(2),解最佳,。,。,2.3,搜索技,术,术,搜索从,问,问题性,质,质上来,看,看,可分为,一,一般搜,索,索和博,奕,奕搜索,从处理,方,方法上,来,来看,可分为,盲,盲目搜,索,索和启,发,发式搜,索,索。还,可,可以分,得,得更细,。,。,当所给,定,定的问,题,题用状,态,态空间,表,表示时,则求解,过,过程可,归,归结为,对,对状态,空,空间的,搜,搜索。,当问题,有,有解时,使用不,同,同的搜,索,索策略,找到解,的,的搜索,空,空间范,围,围是有,区,区别的,。,。一般,来,来说,对大空,间,间问题,搜索策,略,略是要,解,解决组,合,合爆炸,的,的问题,2.3,搜索策,略,略,通常搜,索,索策略,的,的主要,任,任务是,确,确定如,何,何选取,规,规则的,方,方式。,有,有两种,基,基本方,式,式,:,一种,是,是不,考,考虑,给,给定,问,问题,所,所具,有,有的,特,特定,知,知识,系统,根,根据,事,事先,确,确定,好,好的,某,某种,固,固定,排,排序,依次,调,调用,规,规则,或,或随,机,机调,用,用规,则,则,这实,际,际上,是,是盲,目,目搜,索,索的,方,方法,一般,统,统称,为,为无,信,信息,引,引导,的,的搜,索,索策,略,略。,另一,种,种是,考,考虑,问,问题,领,领域,可,可应,用,用的,知,知识,动态,地,地确,定,定规,则,则的,排,排序,优先,调,调用,较,较合,适,适的,规,规则,使,使用,这就,是,是通,常,常称,为,为启,发,发式,搜,搜索,策,策略,或,或有,信,信息,引,引导,的,的搜,索,索策,略,略。,AI,领域,的,的搜,索,索方,法,法,(1),求任,一,一解,路,路的,搜,搜索,策,策略,回溯,法,法,(Backtracking),爬山,法,法,(HillClimbing),宽度,优,优先,法,法,(Breadth-first),深度,优,优先,法,法,(Depth-first),限定,范,范围,搜,搜索,法,法,(BeamSearch),最佳,优,优先,法,法,(Best-first),(2),求最,佳,佳解,路,路的,搜,搜索,策,策略,大英,博,博物,馆,馆法,(BritishMuseum),分枝,界,界限,法,法,(BranchandBound),动态,规,规划,法,法,(DynamicProgramming),最佳,图,图搜,索,索法,(A*),AI,领域,的,的搜,索,索方,法,法,(3),求与,或,或关,系,系解,图,图的,搜,搜索,法,法,一般,与,与或,图,图搜,索,索法,(AO*),极小,极,极大,法,法,(Minimax),剪枝,法,法,(Alpha-betaPruning),启发,式,式剪,枝,枝法,(HeuristicPruning),搜索,策,策略,分,分类,盲目,搜,搜索,方,方法,盲目,搜,搜索,是,是不,利,利用,问,问题,的,的有,关,关信,息,息,而根,据,据事,先,先确,定,定好,的,的某,种,种固,定,定的,搜,搜索,方,方法,进,进行,搜,搜索,。,。,典型,的,的盲,目,目搜,索,索方,法,法是,深,深度,优,优先,搜,搜索,和,和宽,度,度优,先,先搜,索,索,(,亦称,广,广度,优,优先,搜,搜索,),这是,两,两处,基,基本,搜,搜索,方,方法,回溯,策,策略,例：,皇,皇后,问,问题,在一,个,个,44,的国,际,际象,棋,棋棋,盘,盘上,一次,一,一个,地,地摆,布,布四,枚,枚皇,后,后棋,子,子,摆好,后,后要,满,满足,每,每行,、,、每,列,列和,对,对象,线,线上,只,只允,许,许出,现,现一,枚,枚棋,子,子,即棋,子,子间,不,不许,相,相互,俘,俘获,(),(),Q,(1,1),(),Q,Q,(1,1),(1,1)(2,3),(),Q,(1,1),(1,1)(2,3),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),(),Q,Q,(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,数列,1202,年，,意,意大,利,利家,斐,斐波,那,那契,在,在提,出,出了,一,一个,关,关于,兔,兔子,繁,繁殖,的,的问,题,题：,如,如果,一,一对,兔,兔子,每,每月,能,能生,一,一对,小,小兔,（,（一,雄,雄一,雌,雌）,，,，而,每,每对,小,小兔,在,在它,出,出生,後,後的,第,第三,个,个月,里,里，,又,又能,开,开始,生,生一,对,对小,兔,兔，,假,假定,在,在,不,不发,生,生死,亡,亡的,情,情況,下,下，,由,由一,对,对出,生,生的,小,小兔,开,开始,，,，,50,個月,后,后会,有,有多,少,少对,兔,兔子,？,？,當,n,1,時，,Fn+2=Fn+1+Fn,，而,F0=F1=1,。,递归,的,的思,想,想（,续,续）,当前,状,状态,目标,状,状态,g,回溯,搜,搜索,算,算法,BACKTRACK,（,DATA,）,DATA,：当,前,前状,态,态。,返回,值,值：,从,从当,前,前状,态,态到,目,目标,状,状态,的,的路,径,径,（以,规,规则,表,表的,形,形式,表,表示,）,）,或,FAIL,。,回溯,搜,搜索,算,算法,递归,过,过程,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);,存在,问,问题,及,及解,决,决办,法,法,问题,：,：,深度,问,问题,死循,环,环问,题,题,解决,办,办法,：,：,对搜,索,索深,度,度加,以,以限,制,制,记录,从,从初,始,始状,态,态到,当,当前,状,状态,的,的路,径,径,回溯,搜,搜索,算,算法,1,BACKTRACK1,（,DATALIST,）,DATALIST,：从,初,初始,到,到当,前,前的,状,状态,表,表（,逆,逆向,）,）,返回,值,值：,从,从当,前,前状,态,态到,目,目标,状,状态,的,的路,径,径,（以,规,规则,表,表的,形,形式,表,表示,）,）,或,FAIL,。,回溯,搜,搜索,算,算法,1,1,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);,回溯,搜,搜索,算,算法,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);,一些,深,深入,的,的问,题,题,失败,原,原因,分,分析,、,、多,步,步回,溯,溯,Q,Q,一些,深,深入,问,问题,（,（续,）,）,回溯,搜,搜索,中,中知,识,识的,利,利用,基本,思,思想,：,：,尽可,能,能选,取,取划,去,去对,角,角线,上,上位,置,置数,最,最少,的,的。,Q,Q,Q,Q,4 3 3 4,图搜,索,索策,略,略,问题,的,的引,出,出,回溯,搜,搜索,：,：只,保,保留,从,从初,始,始状,态,态到,当,当前,状,状态,的,的一,条,条路,径,径。,图搜,索,索：,保,保留,所,所有,已,已经,搜,搜索,过,过的,路,路径,。,。,一些,基,基本,概,概念,节点,深,深度,：,：,根节,点,点深,度,度,=0,其它,节,节点,深,深度,=,父节,点,点深,度,度,+1,0,1,2,3,一些,基,基本,概,概念,（,（续,1,）,路径,设一,节,节点,序,序列,为,为,(n,0,n,1,n,k,),，对,于,于,i=1,k,，若,节,节点,n,i-1,具有,一,一个,后,后继,节,节点,n,i,，则,该,该序,列,列称,为,为从,n,0,到,n,k,的路,径,径。,路径,的,的耗,散,散值,一条,路,路径,的,的耗,散,散值,等,等于,连,连接,这,这条,路,路径,各,各节,点,点间,所,所有,耗,耗散,值,值的,总,总和,。,。用,C(n,i,n,j,),表示,从,从,n,i,到,n,j,的路,径,径的,耗,耗散,值,值。,一些,基,基本,概,概念,（,（续,1,）,扩展,一,一个,节,节点,生成,出,出该,节,节点,的,的所,有,有后,继,继节,点,点，,并,并给,出,出它,们,们之,间,间的,耗,耗散,值,值。,这,这一,过,过程,称,称为,“,“扩,展,展一,个,个节,点,点”,。,。,图搜,索,索的,一,一般,过,过程,(1),建立,一,一个,只,只含,有,有起,始,始节,点,点,S,的搜,索,索图,G,，把,S,放到,一,一个,叫,叫做,OPEN,的未,扩,扩展,节,节点,表,表中,（,（简,称,称,OPEN,表）,。,。,(2),建立,一,一个,叫,叫做,CLOSED,的已,扩,扩展,节,节点,表,表（,简,简称,CLOSED,表）,，,，其,初,初始,为,为空,表,表。,(3)LOOP,：若,OPEN,表是,空,空表,，,，则,失,失败,退,退出,。,。,(4),选择,OPEN,表上,的,的第,一,一个,节,节点,，,，把,它,它从,OPEN,表移,出,出并,放,放进,CLOSED,表中,。,。称,此,此节,点,点为,节,节点,n,，它,是,是,CLOSED,表中,节,节点,的,的编,号,号。,(5),若,n,为一,目,目标,节,节点,，,，则,有,有解,并,并成,功,功退,出,出，,此,此解,是,是追,踪,踪图,G,中沿,着,着指,针,针从,n,到,S,这条,路,路径,而,而得,到,到的,(,指针,将,将在,第,第,7,步中,设,设置,),。,(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,。,OPEN,表,节点,父节点,CLOSED,表,标号,节点,父节点,OPEN,表,节点,父节点编号,CLOSED,表,编号,节点,父节点编号,例子,例子：从,某,某王姓家,族,族的四代,中,中找王,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,，如何寻,找,找？,问题的搜,索,索树,深度优先,搜,搜索的搜,索,索过程,无信息图,搜,搜索过程,深度优先,重排九宫,深,深度优先,只是搜索,树,树的一部,分,分，尚未,到,到达目标,节,节点，仍,需,需继续往,下,下搜索。,有界深度,优,优先搜索,的,的搜索过,程,程,如果问题,有,有解，且,其,其路径长,度,度,dm,，则搜索,过,过程就得,不,不到解。,-,深度界限,的,的选择很,重,重要。,有界深度,优,优先搜索,设深度界,度,度,dm=4,，有界深,度,度优先搜,索,索求解图,如,如下，解,的,的路径为,S0,20252628(Sg),深度优先,搜,搜索的性,质,质,一般不能,保,保证找到,最,最优解,当深度限,制,制不合理,时,时，可能,找,找不到解,，,，可以将,算,算法改为,可,可变深度,限,限制,最坏情况,时,时，搜索,空,空间等同,于,于穷举,与回溯法,的,的差别：,图,图搜索,是一个通,用,用的与问,题,题无关的,方,方法,无信息图,搜,搜索过程,宽度优先,宽度优先,搜,搜索过程,：,：,(1),把起始节,点,点放到,OPEN,表中,(,如果该起,始,始节点为,一,一目标节,点,点，则求,得,得一个解,答,答,),。,(2),如果,OPEN,是个空表,，,，则没有,解,解，失败,退,退出；否,则,则继续。,(3),把,OPEN,表中第一,个,个节点,(,节点,n),从,OPEN,表移出，,并,并把它放,入,入,CLOSED,扩展节点,表,表中。,(4),考察节点,n,是否为目,标,标节点，,若,若是则求,得,得问题的,解,解，退出,，,，,(5),若节点,n,不可扩展,，,，则转第,(2),步。,(6),扩展节点,n,。将其所,有,有后继节,点,点放到,OPEN,表的,末端,，并为每,个,个后续节,点,点都配置,指,指向,n,的指针。,然,然后转向,第,第,(2),步。,宽度优先,重排九宫,宽,宽度优先,解的路径,：,：,S0,38,1626,宽度优先,搜,搜索的性,质,质,只要问题,有,有解，一,定,定能找到,解,解，而且,得,得到的是,路,路径最短,的,的解。,盲目性较,大,大，当目,标,标节点距,离,离初始节,点,点较远时,将,将会产生,许,许多无用,节,节点，因,此,此搜索效,率,率低。,方法与问,题,题无关，,具,具有通用,性,性,属于图搜,索,索方法,非启发式,搜,搜索,按照事先,规,规定的路,线,线进行搜,索,索,广度优先,搜,搜索是按,“,层,”,进行搜索,的,的，先进,入,入,OPEN,表的节点,先,先被考察,深度优先,搜,搜索是沿,着,着纵深方,向,向进行搜,索,索的，后,进,进入,OPEN,表的节点,先,先被考察,按已经付,出,出的代价,决,决定下一,步,步要搜索,的,的节点（,为,为树中的,每,每条边赋,予,予代价，,广,广度及深,度,度优先搜,索,索实质是,每,每条边的,代,代价都为,1,）,代价树的,广,广度优先,代价树的,深,深度优先,代价树的,宽,宽度忧先,搜,搜索,边上标有,代,代价,(,或费用,),的树称为,代,代价树。,在代价树,中,中，若用,g(x),表示从初,姑,姑节点,S0,到节点,x,的代价，,用,用,c(xl,x2),表示从父,节,节点,x1,到子节点,x2,的代价，,则,则有：,g(x2)=g(x1)+c(x1,x2),代价树宽,度,度优先搜,索,索的基本,思,思想是：,OPEN,表中的节,点,点在任一,时,时刻都是,按,按其代价,从,从小到大,排,排序的，,每,每次扩展,时,时总是从,OPEN,表中选取,代,代价最小,的,的节点进,行,行扩展。,其,其搜索过,程,程如下：,五城市间,的,的交通路,线,线图，,A,城市是出,发,发地，,E,城市是目,的,的地，两,城,城市间的,交,交道费用,(,代价,),如左图小,数,数字所示,。,。求从,A,到,E,的最小费,用,用交通路,线,线。,交通代价,树,树如右图,，,，解为,A,CD,E,代价树的,宽,宽度优先,搜,搜索举例,代价树的,深,深度忧先,搜,搜索,代价树的,宽,宽度优先,搜,搜索中，,每,每次扩展,时,时总是从,OPEN,表中选取,代,代价最小,的,的节点进,行,行扩展。,而,而代价树,的,的深度优,先,先搜索是,从,从刚扩展,出,出的子节,点,点中选一,个,个代价最,小,小的节点,送,送入,CLOSE,表中进行,考,考察。,其搜索过,程,程如下：,解,解也为,A,CD,E,启发式图,搜,搜索,利用知识,来,来引导搜,索,索，达到,减,减少搜索,范,范围，降,低,低问题复,杂,杂度的目,的,的。,启发性信,息,息,用于指导,搜,搜索过程,，,，且与具,体,体问题求,解,解有关的,控,控制性信,息,息称为启,发,发性信息,启发信息,的,的强度,强：降低,搜,搜索工作,量,量，但可,能,能导致找,不,不到最,优,优解,弱：一般,导,导致工作,量,量加大，,极,极限情况,下,下变为,盲,盲目,搜,搜索，但,可,可能可以,找,找到最优,解,解,希望：,引入启发,知,知识，在,保,保证找到,最,最佳解的,情,情况下，,尽,尽可能减,少,少搜索范,围,围，提高,搜,搜索效率,。,。,基本思想,定义一个,评,评价函数,f,，对当前,的,的搜索状,态,态进行评,估,估，找出,一,一个最有,希,希望的节,点,点来扩展,。,。,1,，启发式,搜,搜索算法,A,（,A,算法）,评价函数,的,的格式：,f(n)= g(n)+ h(n),f(n),：评价函,数,数,g(n):,实际已经,付,付出的代,价,价函数,h(n),：启发函,数,数,符号的意,义,义,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),的估计值,一个,A,算法的例,子,子,定义评价,函,函数：,f(n)= g(n)+ h(n),g(n),为从初始,节,节点到当,前,前节点的,耗,耗散值,即顶点,Sn,在状态空,间,间中的深,度,度,(,从根顶点,到,到,Sn,所经历的,层,层次数,),。,h(n),为当前节,点,点“不在,位,位”的将,牌,牌数,283,164,75,123,84,765,h,计算举例,h(n)=4,283,164,75,123,4,5,76,8,283,164,75,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,7 8 4,6 5,s(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),目标,1,2,3,4,5,6,g=0,h=4,f=0+4=4,g=1,h=5,f=1+5=6,g=0,g=1,g=2,g=3,最佳图搜,索,索算法,A*,（,A*,算法）,在,A,算法中，,如,如果满足,条,条件：,h(n),h*(n),则,A,算法称为,A*,算法。其,中,中,h*(n),是从顶点,Sn,到,Sg,的最小代,价,价。,由于,h*(n),最小代价,通,通常不知,道,道，因此,用,用,h(n),（不在位,的,的将牌数,）,）进行代,价,价估计，,因,因此可得,h(n)=f1,2,8,3,1,6,4,7 5,1 2 3,4,5,7 6,8,将牌,1,：,1,将牌,2,：,1,将牌,6,：,1,将牌,8,：,2,A*,算法的性,质,质,定理,1,：,对有限图,，,，如果从,初,初始节点,s,到目标节,点,点,t,有路径存,在,在，则算,法,法,A,一定成功,结,结束。,AO*,算法是,A*,算法在与,或,或图上的,扩,扩展算法,。,。,AO*,算法中由,于,于与节点,的,的存在，,解,解对应的,不,不是一条,路,路径，而,是,是一个子,图,图，因此,对,对顶点的,评,评估实际,上,上是对局,部,部解图的,评,评价。,与节点代,价,价计算：,最大代价,和代价,或节点的,代,代价计算,：,：最小代,价,价,AO*,算法,AO*,算法举例,7=3+1(,左树,)+2+1,8=3+1+3+1,8=min(8+1,7+1),与或树的,宽,宽度优先,与,与深度优,先,先搜索,宽度优先,：,：,1,23,45,深度优先,：,：,13B524,问题,图搜索是,针,针对什么,知,知识表示,方,方法的问,题,题求解方,法,法？,什么是图,搜,搜索,?,其中，重,排,排,OPEN,表意味着,什,什么，重,排,排的原则,是,是什么,?,宽,度,度,优,优,先,先,搜,搜,索,索,方,方,法,法,中,中,OPEN,表,需,需,要,要,按,按,什,什,么,么,方,方,式,式,进,进,行,行,操,操,作,作,A,先,先,进,进,后,后,出,出,B,先,先,进,进,先,先,出,出,有,界,界,深,深,度,度,优,优,先,先,搜,搜,索,索,方,方,法,法,能,能,够,够,保,保,证,证,在,在,搜,搜,索,索,树,树,中,中,找,找,到,到,一,一,条,条,通,通,向,向,目,目,标,标,节,节,点,点,的,的,最,最,短,短,途,途,径,径,吗,吗,？,？,试,比,比,较,较,各,各,种,种,盲,盲,目,目,搜,搜,索,索,搜,搜,索,索,方,方,法,法,的,的,效,效,率,率,，,，,找,找,出,出,影,影,响,响,算,算,法,法,效,效,率,率,的,的,原,原,因,因,试,比,比,较,较,宽,宽,度,度,优,优,先,先,搜,搜,索,索,、,、,有,有,界,界,深,深,度,度,优,优,先,先,搜,搜,索,索,及,及,有,有,序,序,搜,搜,索,索,的,的,搜,搜,索,索,效,效,率,率,，,，,并,并,以,以,实,实,例,例,数,数,据,据,加,加,以,以,说,说,明,明,启,发,发,式,式,搜,搜,索,索,的,的,必,必,要,要,性,性,现,实,实,的,的,困,困,难,难,迫,迫,使,使,人,人,们,们,转,转,而,而,求,求,援,援,于,于,启,启,发,发,式,式,算,算,法,法,。,。,这,这,种,种,算,算,法,法,的,的,本,本,质,质,是,是,部,部,分,分,地,地,放,放,