Ch5状态空间搜索策略new

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 状态空间搜索策略,Searching,1,5.1,搜索概述,在解空间中寻找解的过程与,策略,搜索问题的产生,（,1,）结构不良或非结构化的问题，无解析解,（,2,）理论上可解的问题，计算复杂度可能太高,基本搜索方式,（,1,）,盲目搜索,按预定策略进行搜索，不考虑问题本身的特性,（,2,）,启发式,(Heuristic),搜索,利用与问题有关的启发式信息，加快搜索过程,启发式搜索,启发式信息,与,评价函数,反映问题特性，可用于确定搜索方向的信息,评价函数的作用是根据启发式信息，计算对应于特定搜索方向的评价值，作为选择搜索方向的依据。,局部,(local),搜索,vs.,全局,(global),搜索,确定搜索方向时考虑局部信息还是全局信息？,任一解,vs.,最优解,搜索方法,图搜索方法,宽度优先法,(,breadth-first,),，深度优先法,(,depth-first,),，有界深度优先法，启发式最优图搜索法,(A*,，,AO*).,博弈搜索方法,极小极大法,(,MiniMax,),，,Alpha-Beta,剪枝法,(,pruning,),现代优化搜索方法,爬山法,(,hill climbing,),，模拟退火法,(,simulated annealing,),，遗传算法,(,genetic algorithms,).,搜索策略的评价,完备性,如果问题有解，能否保证找到？,最优性,(,optimization,),如果问题存在不同的解，能否找到最优解？,时间复杂性,-,找到一个解需要花费多少时间,空间复杂性,-,在搜索过程中需要占用多少内存,时空复杂性的量度,状态空间图的大小,分支因子,b,目标节点的深度,d,路径的最大长度,m,搜索深度限制,l,5.2,问题及其搜索过程的表示,状态空间,表示法,通过“,状态,”表示问题，通过“,操作符,”求解问题,状态的改变,表示了问题求解过程,状态空间,以“状态”和“操作符”为基础,状态,：,问题求解过程中任意时刻的状况,操作符,：,使问题从一个状态变为另一个状态的操作,问题的全部状态,(,包含初始状态和目标状态,),及一切可用操作符所构成的集合称为问题的状态空间。,初始,状态,中间,状态,1,中间,状态,2,目标,状态,状态空间例：,二阶梵塔问题,设有三根钢针，它们的编号分别是,1,号、,2,号和,3,号。在初始情况下，,l,号钢针上穿有,A,、,B,两个金片，,A,比,B,小，,A,位于,B,的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。,用,Sk=,Sk0,，,Sk1,表示问题的,状态,，其中，,Sk0,表示金片,A,所在的钢针号，,Sk1,表示金片,B,所在的钢针号。全部可能的问题状态共有以下,9,种：,SO=(1,，,l) S1=,（,1,，,2,）,S2=,（,1,，,3,）,S3=(2,，,1,）,S4=,（,2,，,2,）,S5=,（,2,，,3,）,S6=(3,，,1,）,S7=,（,3,，,2,）,S8=,（,3,，,3,）,1,2,3,B,A,B,A,B,A,1,2,3,S0=(1,1),S4=(2,2),S8=(3,3),二阶梵塔问题的初始与目标状态,操作符,：,A(i,j),表示把金片,A,从第,i,号钢针移到,j,号钢针上；,B(i,j),表示把金片,B,从第,i,号钢针移到,j,号钢针上。共有,12,种操作，分别是：,A(1,，,3) A(2,，,1) A(2,，,3) A(3,，,1) A(3,，,2),B(1,，,3) B(2,，,1) B(2,，,3) B(3,，,1) B(3,，,2),(1,1),(2,1),(2,3),(3,3),(1,3),(1,2),(2,2),(3,2),(3,1),A(1,3),B(1,2),A(3,2),根据状态和操作符，可构成,二阶梵塔问题的状态图,最短路径解,八数码游戏（八数码问题）描述为：在,33,组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有,1-8,八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。,5.3,一般图搜索算法,无论是状态空间，还是与或图的问题表示，问题求解过程都可看作是在“,图,”中进行搜索。,基本思想,不存储全部搜索图，而是逐步展开问题求解所需的搜索子图,具体方法,从初始状态开始，不断扩展当前节点，即生成子节点，直到目标状态出现在这些子节点中，或者没有可供扩展的节点为止。,数据结构,Open,表（,未扩展节点表,）,存放未进行过扩展的节点,Closed,表（,已扩展节点表,）,存放已经扩展过的节点,Open,表：,Closed,表,：,算法步骤,Step1,把初始节点,S0,放入,Open,表，建立仅包含,S0,的图,G,；,Step2,从,Open,表中取出待扩展节点，放入,Closed,表,；,（不同搜索策略的区别主要体现于此）,Step3,对节点进行扩展，将扩展得到的、未在,G,中出现过的子节点放入,Open,表；根据需要修改,G,中节点的指针；,Step4,重复,Step2-3,直到,状态空间,：待扩展节点为目标节点或,Open,表为空,盲目搜索策略,广度（宽度）优先搜索,先生成的节点先扩展,深度优先搜索,后生成的节点先扩展,有界深度优先搜索,在深度优先策略中增加深度限制，在广度优先与深度优先之间折衷,完备,最小路径解,效率,2 8 3,4,7 6 5,S,0,1 2 3,8 4,7 6 5,Sg,盲目搜索例（状态空间）,:,八数码难题,在,3*3,的方格棋盘上，分别放置了标有数字,1,、,2,、,3,、,4,、,5,、,6,、,7,、,8,的八张牌，初始状态,S,0,和目标状态,S,g,分别如图所示。可以使用的操作有：,空格左移，空格上移，空格右移，空格下移,寻找从初始状态到目标状态的解路径。,广度优先搜索算法如下：,(1),把初始结点放入,Open,表中；,(2),如果,Open,表为空，则问题无解，失败退出；,(3),把,Open,表的第一个结点取出，放入,Closed,表，并记该结点为,n,；,(4),扩展节点,n,，如果没有后继节点，则转向第,(2),步；,(5),把,n,的所有后继结点放入,Open,表的末尾，并提供从这些后继结点回到父结点,(,编号值为,n),的指针,;,(6),如果刚产生的这些后继结点中存在一个目标结点，则找到一个解。解可从目标结点开始直到初始结点的返回指针中得到，算法成功退出。否则转,(2),继续。,S,L,O,M,F,P,Q,N,F,F,F,起始结点,起始,把,S,0,放入,Open,表,Open,表,是否为空,失败,把第,1,个结点,n,，从,Open,表,移出并把它放入,Closed,表中,扩展,n,把它的后继结点放入,Open,表的末端,提供回到,n,的,指针,是否有,任何后继结点为目标,结点？,成,功,否,是,否,是,示意图,算法框图,2 8 3,4,7 6 5,S,0,1,2 8 3,1,4,7 6 5,2,2 3,8,4,7 6 5,3,2 8 3,4,7 6 5,4,2 8 3,6,4,7 5,5,8 3,2,1 4,7 6 5,2 8 3,7,1,4,6 5,2,3,8,4,7 6 5,2,3,8,4,7 6 5,2 8,4,3,7 6 5,2 8 3,4,5,7 6,2 8 3,6,4,7,5,2 8 3,6,4,7,5,6,7,8,9 10,11 12,13,8,3,2,1 4,7 6 5,2 8 3,7,1,4,6,5,1,2,3,8,4,7 6 5,2,3,4,8,7 6 5,2,8,4,3,7 6 5,2 8 3,4,5,7,6,2 8 3,6,4,1,7,5,2 8 3,6,7,5,4,14,15,21,8,3,2,1 4,7 6 5,8,1,3,2,4,7 6 5,22,23,2 8 3,7,4,6,1,5,2 8 3,7,1,4,6,5,24,25,1 2,3,8,4,7 6 5,1,2,3,7,8,4,6 5,26,27,Sg,解的路径是：,S,0,3 8 16 26(,Sg,),八数码难题的广度优先搜索,广度优先搜索是一种完备策略，即只要问题有解,它就一定可以找到解。并且广度优先搜索找到的解，还一定是路径最短的解。,深度优先搜索,深度优先搜索是一种,后生成的结点先扩展的策略,。其搜索过程是：从初始结点,S,0,开始，在其子结点中选择一个最新生成的结点进行考察，如果该子结点不是目标结点且可以扩展，则扩展该子结点，依此向下搜索，直到某个子结点既不是目标结点，又不能继续扩展时，才选择其兄弟结点进行考察。图示如下：,S0,1,2,3,7,6,8,4,5,9,起始结点,起始,把,S,0,放入,Open,表,S,0,是否为,目标结点,是否,Open,为空表,把,Open,表中的第一个结,点,n,移入,Closed,表,结点,n,的深度是否等于深度,界限,扩展结点,n,，把其后代放入,Open,表的前端,是否有,任何后继结点为目标,结点,成功,失败,成功,是,否,是,是,是,否,否,否,示意图,算法框图,深度优先搜索算法如下：,(1),把初始结点,S,0,放入,Open,表中；,(2),如果,Open,表空，则问题无解，失败退出；,(3),把,Open,表的第一个结点取出放入,Close,表，并记该结点为,n;,(4),考察结点,n,是否为目标结点，若是，则得到问题的解，成功退出；,(5),若结点,n,不可扩展，则转,(2),；,(6),扩展结点,n,，将其子结点放入,Open,表的首部，并为每一个子结点设置指向父结点的指针，然后转,(2),。,2 8 3,4,7 6 5,S0,1,2 8 3,1,4,7 6 5,3,1,8,4,7 6 5,2 8 3,1,4,7 6 5,2 8 3,1,6,4,7 5,2,2 8 3,1 6 4,7,5,2 8 3,1 6 4,7,5,3,2 8 3,1 6,7 5,4,4,2 8,1 6,3,7 5 4,2 8 3,6,7 5 4,5,8,1 6 3,7 5 4,6,八数码难题的深度优先搜索,从深度优先搜索的算法可以看出,搜索一旦进入某个分支，就将沿这个分支一直进行下去，如果目标恰好在这个分支上,则它可以很快找到解,.,但是,如果目标不在这个分支上，且分支是一个无穷分支，则搜索过程就不可能找到解。因此，深度优先搜索是一种不完备策略，即使问题有解，它也不一定能够找到解。,解路径为,:,So,：,l 11 12 13 14,：,Sg,Sg,八数码难题的有界深度优先搜索,2 8 3,4,7 6 5,S0,1,2 8 3,1,4,7 6 5,2,2 3,8,4,7 6 5,11,2 8 3,4,7 6 5,2 8 3,6,4,7 5,8 3,2,1 4,7 6 5,2 8 3,7,1,4,6 5,2,3,8,4,7 6 5,2,3,8,4,7 6 5,2 8,4,3,7 6 5,2 8 3,4,5,7 6,2 8 3,6,4,7,5,2 8 3,6,4,7,5,3,7,13,8,3,2,1 4,7 6 5,2 8 3,7,1,4,6,5,1,2,3,8,4,7 6 5,2,3,4,8,7 6 5,2,8,4,3,7 6 5,2 8 3,4,5,7,6,2 8 3,6,4,1,7,5,2 8 3,6,7,5,4,4,8,8,3,2,1 4,7 6 5,8,1,3,2,4,7 6 5,5,6,2 8 3,7,4,6,1,5,2 8 3,7,1,4,6,5,9,10,1 2,3,8,4,7 6 5,1,2,3,7,8,4,6 5,14,12,深度限制为,4,上面讨论的搜索方法都没有用到问题本身的特性信息，只是按事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是非常有益的。这种利用问题自身的特性来引导搜索过程，,提高搜索效率,的搜索策略称为,启发式搜索,或,有信息搜索,。,启发式搜索方法所依据的是问题自身的,启发性信息,，而启发性信息又是通过,估价函数,而作用于搜索过程的。,5.4,启发式搜索,启发式算法,利用问题的特殊性，选择待扩展的节点，以缩小搜索范围，提高搜索速度。,启发信息,可指导搜索过程，且与具体问题求解过程有关的控制性信息。一般有以下三种：,帮助确定扩展节点的信息；,帮助决定哪些后继节点应被生成的信息；,在扩展一个节点时决定哪些节点应被删除的信息,估价函数,f(n),：,用于估计,节点代价,的函数,定义,为从初始节点,S0,出发，经过节点,n,约束后，到达目标节点,Sg,的所有路径中最优路径的代价估计值。,一般形式,为,f(n)=g(n),h(n),g(n),是从初始节点,S0,到节点,n,的实际代价。可以从节点,n,反向跟踪到初始节点,S0,得到一条当前最小代价路径，把这条路径上所有有向边的代价相加，就得到,g(n),的值。 ；,h(n),是从节点,n,到目标节点,S0,的最优路径的估计代价。需要根据问题自身的特性来确定，体现了问题自身的启发性信息，因此也称为,启发函数,。,估价函数例：,f(n) = d(n) + W(n),2 8 3,4,7 6 5,S0,节点,n,在搜索树中的深度,n,中“不在位”的数码个数,f(S0) = ?,= 0 + 3 = 3,1 2 3,8 4,7 6 5,Sg,根据搜索过程中选择扩展节点的范围，分为全局择优搜索和局部择优搜索。,1.,全局择优,在,Open,表的所有节点中选择一个估价函数值最小的节点进行扩展,2.,局部择优,在刚生成的子节点中选择一个估价函数值最小的节点进行扩展。,局部最佳优先搜索算法,对,OPEN,表中所有节点的,f(n),进行比较，按从小到大的顺序重排,OPEN,表。,其算法效率类似于纵向搜索算法，但使用了与问题特性相关的估价函数来确定下一步待扩展的节点，因此是一种启发式搜索方法。,开始,把,S,放入,OPEN,表，计算估价函数,f (s),OPEN,表为空表？,把,OPEN,表中的第一个节点,n,放入,CLOSED,表,n,为目标节点吗？,扩展,n,，计算所有子节点的估价函数值，并提供它们返回节点,n,的指针。,失败,成功,局部最佳优先搜索算法框图,是,否,是,否,把子节点送入,OPEN,表，并对其中的所有节点按估价函数值由小到大重排。,举例：,八数码魔方（,8-puzzle problem,）,1,2,3,8,4,5,6,7,（目标状态）,1,2,3,8,4,5,6,7,（初始状态）,5,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,(3),(5),(5),1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,(4),(3),(3),1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,(2),(4),1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,(3),(4),1,2,3,8,4,5,6,7,(1),8,1,3,2,4,5,6,7,1,2,3,8,4,5,6,7,(0),(2),八数码魔方的局部最佳优先搜索树,1,2,3,8,4,6,(4),7,5,搜索得到的路径如黄线所示,本题采用了简单的估价函数,f(n)=W(n),其中：,W(n),用来计算对应于节点,n,的数据库中错放的棋子个数。因此，初始节点棋局,的,f(n),值等于,4,。,1,2,3,8,4,5,6,7,第,步有三种情况,我们选择其中,f(n),最小的,:,其它依次类推,.,最后用了,7,步得出了结果,.,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,(3),(5),(5),最佳优先算法有时无法得到最优解，因为它的估价函数,f,的选取时，忽略了从初始节点到目前节点的代价值。所以，可考虑对估价函数,f(n),进行某些修改或限制。,5.5,A*,算法,对估价函数加上一些限制，以保证得到最优解的启发式搜索算法,最优估价函数,f*(n),g*(n),h*(n),初始节点到节点,n,的最小代价,节点,n,到目标节点的最小代价,有关限制,1.,g(n),是对,g*(n),的估计，且,g(n),0,；,2.,h(n),是,h*(n),的下界，即对任意节点,n,均有,h(n)h*(n),A*,算法例,1,：八数码问题,解,1,：,h(n) = W(n),。尽管不能确切知道,h*(n),，但当采用单位代价时，通过对“不在位”数码个数的估计，可以得出至少要移动,W(n),步才能到达目标，显然有,W(n)h*(n),，满足,A*,算法的限制条件。,解,2,：,h(n) = P(n),，,P(n),定义为每一个数码与其目标位置之间距离（不考虑夹在其间的数码）的总和，同样可以断定至少要移动,P(n),步才能到达目标，因此有,P(n)h*(n),，即满足,A*,算法的限制条件。,2 8,3,1,4,7 6 5,h=4, f=4,S0,2,3,1,8,4,7 6 5,2 8,3,1 6,4,7 5,2 8,3,1,4,7 6 5,2 8,3,1 4,7 6 5,g=1,2,3,1,8,4,7 6 5,2,3,1,8,4,7 6 5,g=2,1,2,3,8,4,7 6 5,1,2,3,7,8,4,6 5,Sg,g=4,h=5, f=6,h=5, f=6,h=3, f=4,h=5, f=6,h=2, f=4,h=3, f=5,1,2,3,8,4,7 6 5,g=3,h=1, f=4,h=0, f=4,h=2, f=6,八数码难题的的,A*,搜索图 （,h(n) = P(n),）,A*,算法例,2,：,修道士和野人问题,设在河的左岸有三个修道士、三个野人和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：,1.,修道士和野人都会划船，但每次船上至多可载两个人；,2.,河的任一岸如果野人数目超过修道士数，修道士就会被野人吃掉。,请给出一个确保修道士和野人都能过河，且没有修道士被野人吃掉的过河规划,问题表示,：需要考虑两岸的修道士人数和野人人数，船的位置。用三元式表示状态：,S= (m, c, b),其中，,m,表示左岸修道士人数，,c,表示左岸野人人数，,b,表示左岸船的数目。,解,：确定估价函数。,f(n) = g(n),h(n) = d(n),m,c,2b,其中，,d(n),为节点深度。,h(n),h*(n),，满足,A*,算法的限制条件。,(3,2,0),(3,1,0),(2,2,0),(3,3,1),h=4,f=4,f(n)=d(n)+,m+c-2b,h,h=5,f=6,h=4,f=5,h=4,f=5,(3,2,1),h=3,f=5,(2,1,0),(3,0,0),h=3,f=6,h=3,f=6,(2,2,1),(3,1,1),h=2,f=6,h=2,f=6,h=2,f=7,h=2,f=7,传教士和野人问题的,A*,搜索图,(0,0,0),(0,3,1),h=1,f=7,(0,1,0),h=1,f=8,(0,2,1),h=0,f=8,(0,2,0),(1,1,0),关于,A*,算法的一些讨论,A*,算法是到目前为止最快的一种计算最短路径的算法，但它是一种较优算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛。,A*,算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如,Dijkstra,算法）。它通过一个估价函数（,Heuristic Function,）,f(h),来估计图中的当前点,p,到终点的距离,(,带权值,),，并由此决定它的搜索方向，当这条路径失败时，它会尝试其它路径。,我们可以发现，,A*,算法成功与否的关键在于估价函数的正确选择，从理论上说，一个完全正确的估价函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函数是得不到的，因而,A*,算法不能保证它每次都得到正确解答。一个不理想的估价函数可能会使它工作得很慢，甚至会给出错误的解答。,为了提高解答的正确性，我们可以适当地降低估价函数的值，从而使之进行更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案，使之更具弹性。,A*,算法的数据结构,众所周知，对图的表示可以采用数组或链表，而且这些表示法也各有优缺点，数组可以方便地实现对其中某个元素的存取，但插入和删除操作却很困难，而链表则利于插入和删除，但对某个特定元素的定位却需借助于搜索。而,A*,算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作，因而数组或链表都显得太通用了，用来实现,A*,算法会使速度有所降低。要实现这些，可以通过二分树、跳转表等数据结构来实现，实践中如采用简单而高效的带优先权的堆栈，经实验表明，一个,1000,个结点的图，插入而且移动一个排序的链表平均需,500,次比较和,2,次移动；未排序的链表平均需,1000,次比较和,2,次移动；而堆仅需,10,次比较和,10,次移动。需要指出的是，当结点数,n,大于,10,，,000,时，堆栈不再是正确的选择，但这足已满足我们一般的要求。,估价函数（,Heuristic Function,）,估价函数的正确选取将直接关系到,A*,算法的成功与否，而函数的确定却与实际情形有着密切的关系。这里以网格地图的估价函数为例，其它情形需要作不同的分析，但至少估价函数应为连续函数。,a.Manhattan Distance,，,这是一种标准的估价函数，,h(A) = 10 * (abs(A.x-goal.x) + abs(A.y-goal.y),b.Diagonal Distance,，,如果在地图上允许作斜线方向的运动，则,Mahattan Distance,修正为,Diagonal Distance,：,h(A) = max(abs(A.x-goal.x), abs(A.y-goal.y),估价函数的判优,一般情形下，我们只需对估价函数的值进行比较而取其大者即可，但在几个结点的估价函数值相同的情形下，我们需要采取一定的策略来决定这几者谁更优，从而避免对多个点的搜索。从而如下代码可实现之：,double dx1 = currentX - goalX;,double dy1 = currentY - goalY;,double dx2 = startX - goalX;,double dy2 = startY - goalY;,cross = dx1*dy2 - dx2*dy1;,if( cross0 ) cross = -cross;,. add cross*0.001 to the heuristic .,这段代码计算始点、当前点和终点的矢量积，从而可以判断这三点是否共线（或近似共线），这样不同点间即使有微小的差别也会被放大，从而更利于判断。,改进的,A*,算法,a.Beam Search,。,在,A*,算法中需要保留所有的结点，这将使得时间和空间的消耗都很大，而,Beam Search,方法对结点数作出限期，当结点数过多时，它会将一些不,(,大,),可能为最优的点排除，从而降低时间和空间的要求，但需要说明的是，由于在排除结点后需对结点排序，当排序的工作量大于排除点后所节省的工作量，则该方法无意义。,b.Iterative deepening,。,这是一种在人工智能中常使用的方法，它首先产生一近似值，然后对它进行修正而逐步接近最优解。这其实是一种博奕算法的变形。,c.Dynamic weighting,。,这种算法是基于这样的考虑，即在搜索初期以速度优先，在搜索后期以准确度优先,(,这可通过对搜索初、后期赋予不同的权值来实现,),。即：,f(p) = g(p) + w(p) * h(p),d.Bidirectional search,。,这种算法从起点和终点同时应用,A*,算法，直到有结点相遇。其缺点在于复杂度太大，一般仅用于复杂的图形。,e.Hierarchical A*,。,这种算法思想是将搜索过程化，对每个简单过程求解从而得全局较优解。正如当我们到另一城市时，可分解为从家里“搜索”一条路径至车站，再从车站“搜索”一条路径到另一城市，当我们从家里出发时，需要考虑的是怎样尽快地到达车站，而不是怎样尽快地到另一城市。,f.Dynamic A*(D*),。,这种算法主要用于人工智能和机器人技术。由于,A*,算法一开始要求获得全部信息，而这在实际中有时是不可能的，而,D*,算法就是在假定信息不完整的前提下应用,A*,算法，但它会随着得到信息的增多而不断改进结果，这就决定了它对空间的要求相当高，因为它需要保留以前的所有获得信息及运算情形。,开放实验：不同搜索策略的算法实现与性能分析,以,8,数码问题求解为例,摘要,词汇表,第一章、,8,数码问题概述,第二章、,x,算法的一般描述,第三章、用,x,算法分析八数码问题,（第四章、评价函数的启发能力）,第五章、,x,算法在,y,开发环境下的实现（不限编程语言）,（,1.,类（可参见附录）,2.,数据结构,3.,程序流程图与相关说明,第六章、性能比较与分析（如广度优先、深度优先）,第七章、进一步讨论（改进与研究）,附录,参考文献,要求,编程语言环境不作要求（,Matlab,、,C/C+,、,Java,等均可）；,独立完成，至少包括一种非启发性、一种启发性算法；,提交最终报告与代码。,