1、主 讲：谢 榕 武汉大学国际软件学院第三章第三章 搜索原理搜索原理内容提要：图搜索策略盲目搜索启发式搜索u问题求解问题求解(problem solving)是人工智能中研究得较早且比较成熟的一个领域。u它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。问题求解与搜索策略问题求解与搜索策略 现实世界中如何求解问题？u现实世界中的大多数问题都是非结构化问题，一般不存在特定的求解方法来解这样的问题，而只能利用已有的利用已有的知识知识一步一步地摸索前进。问题求解与搜索策略问题求解与搜索策略u所要解决的问题是如何寻找可利用的知识，即如何确定如何确定推理路线推理路线，才能使得在付出尽量
2、少的代价的前提下把问题圆满解决。u如果存在多条路线可实现对问题的求解，选出一条求解求解代价最小的路线代价最小的路线，以提高求解程序的运行效率。问题求解与搜索策略问题求解与搜索策略u按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，称为搜索搜索。u搜索包含两层含义：p要找到从初始事实到问题最终答案的一条推理路线推理路线。p所找到的这条路线是时间和空间复杂度时间和空间复杂度最小最小的求解路线。 存在何问题？问题求解与搜索策略问题求解与搜索策略u首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生
3、目标状态为止。图：十五数码难题部分状态图算符：棋子3右移或空格左移中间棋局初始棋局解题过程解题过程问题求解与搜索策略问题求解与搜索策略u若要把表示问题的整个状态空间整个状态空间都存入计算机，往往需要占据很大的存储空间，尤其是对比较复杂的问题，这几乎是不可能实现的，也无这种必要。u对于一个具体的问题，其解往往只与状态空间的一部分相关，只要计算机生成并存储与问题有关存储与问题有关的解状态空间的解状态空间部分，即可将问题解决。u“如何来生成并存储与问题有关的部分状态空间如何来生成并存储与问题有关的部分状态空间？”是人工智能所研究的搜索技术问题。是人工智能所研究的搜索技术问题。问题求解与搜索策略问题求
4、解与搜索策略盲目搜索启发性搜索图搜索策略宽度优先搜索深度优先搜索等代价搜索有序搜索A*算法有限深度优先搜索3.1 3.1 图搜索策略图搜索策略u例如：从某王姓家族的四代中找王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图: 用图表示方法的家族表u例如X=57，用通用的图搜索策
5、略求解此问题。u为了求解问题，需要把有关的知识存储在计算机的知识库中，有以下两种存储方式。p显式存储显式存储。把与问题有关的全部状态空间图，即相应的全部有关知识(叙述性知识、过程性知识和控制性知识)，都直接存入知识库，这种存储方式称为显式存储或显式图。p隐式存储隐式存储。只存储与问题求解有关的部分知识(即部分状态空间)，这种存储方式称为隐式存储。在求解过程中，由初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求的目标状态，只需在知识库中存储局部状态空间图，这种图称为隐式图。 u为了节约计算机的存储容量，提高搜索推理效率，通常采用隐式存储方式，进行隐式图搜索
6、推理。关于图关于图u一个图图由结点的集合组成。结点之间由弧连接。如果弧是有方向的，则这种图称为有向图有向图。在图搜索策略中，结点描述状态，弧代表操作。u如果一条弧由结点ni指向nj，则nj称为ni的后继结点后继结点，ni称为nj的父结点父结点。u在一个图中，如果每个结点最多只有一个父节点，则这种图称为树树。树中没有父辈的结点称为根结点根结点，没有后继结点的结点成为叶结点叶结点。u树中的结点可以定义深度深度。根结点的深度定义为0，其它结点的深度定义为它的父结点的深度加1。图搜索的基本思想图搜索的基本思想u图搜索就是一种在图中寻找路径的方法在图中寻找路径的方法。u寻找过程从图中的初始节点开始，至目
7、标节点为止。其中，初始节点和目标节点分别代表产生式系统的初始数据库和满足终止条件的数据库。u方法方法：先把问题的初始状态作为当前状态，选择适用的算符对其进行操作，生成一组子状态，检查目标状态是否在其中出现。 若出现，则搜索成功，找到了问题的解。 若不出现，则按某种搜索策略从己生成的按某种搜索策略从己生成的状态中再选一个状态作为当前状态状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。图搜索算法中的重要术语图搜索算法中的重要术语uOPENOPEN表表 存放刚生成的节点，作为以后待考察的对象。 OPEN表是一个“有进有出”的动态数据结构。节点进入O
8、PEN表的排列顺序(即出表的顺序)是由搜索策略决定。uCLOSEDCLOSED表表 存放将要扩展或者已经扩展的节点，记录求解中的信息。 CLOSED表是一个“有进无出”的动态数据结构，当前节点进入CLOSED表的最后。图搜索算法中的重要术语图搜索算法中的重要术语u搜索图与搜索树搜索图与搜索树p搜索过程生成一个明确的图G(称为搜索图)和一个G的子集T(称为搜索树)，树T上的每个节点也在图G中。pG中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。图搜索的一般过程图搜索的一般过程(1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPE
9、N的未扩展节点表中（简称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中出现过的(即未曾
10、在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8) 按某一任意方式或按某个探试值，重排OPEN表。(9) GO LOOP。Figure: 图搜索过程框图图搜索方法的几点分析图搜索方法的几点分析u图搜索过程中可以对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为扩展用。u这种排序可以是任意的即盲目的(属于盲目搜索)，也可以是具有各种启发思想或其它准则为
11、依据(属于启发式搜索)。u图搜索策略图搜索策略p无信息搜索策略p启发式搜索策略。3.2 3.2 盲目搜索盲目搜索u无须重新安排OPEN表的搜索叫做无信息搜无信息搜索索或盲目搜索盲目搜索。u盲目搜索包括：p宽度优先搜索p深度优先搜索p等代价搜索u盲目搜索只适用于求解比较简单的问题。3.2.1 3.2.1 宽度优先搜索宽度优先搜索u宽度优先搜索(breadth-first search)u宽度优先搜索的基本思想从初始节点S开始，向下逐层搜索，在n层节点未搜索完之前，不进入n十1层搜索。同层节点的搜索次序可以任意。即先按生成规则生成第一层节点，在该层全部节点中沿宽(广)度进行横向扫描，检查目标节点S
12、g是否在这些子节点中。若没有，则再将所有第一层节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含有Sg，如此依次按照先生成、先检查、先扩展的原则进行下去，直至发现Sg为止。宽度优先搜索算法宽度优先搜索算法(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6) 如果n的
13、任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。Figure: 宽度优先搜索算法框图u列出下列图中树的节点访问序列以满足宽度优先搜索策略：12345671089111213宽度优先搜索：1，2，3，4，5，6，7，8，9，10，11，12，13例：八数码难题例：八数码难题u把宽度优先搜索应用于八数码难题时所生成的搜索树。2831476512384765起始棋局目标棋局u搜索树上的所有节点都标记它们所对应的状态描述，节点扩展的顺序按顺时针方向移动空格。图中最后一个节点是目标节点。Figure: 八数码难题的宽度优先搜索树u对于如图所示的图，给出宽度优先搜索的OPEN表和
14、CLOSED表的变化情况。ABCDEF GH IJKLMNOPQRSTU宽度优先搜索的宽度优先搜索的OPENOPEN表和表和CLOSEDCLOSED表表OPEN=A;CLOSED=OPEN=A;CLOSED=OPEN=B,C,D;CLOSED=AOPEN=B,C,D;CLOSED=AOPEN=C,D,E,F;CLOSED=B,AOPEN=C,D,E,F;CLOSED=B,AOPEN=D,E,F,G,H;CLOSED=C,B,AOPEN=D,E,F,G,H;CLOSED=C,B,AOPEN=E,F,G,H,I,J;CLOSED=D,C,B,AOPEN=E,F,G,H,I,J;CLOSED=D,C
15、,B,AOPEN=F,G,H,I,J,K,L;CLOSED=E,D,C,B,AOPEN=F,G,H,I,J,K,L;CLOSED=E,D,C,B,AOPEN=G,H,I,J,K,L,M;CLOSED=F,E,D,C,B,AOPEN=G,H,I,J,K,L,M;CLOSED=F,E,D,C,B,AOPEN=H,I,J,K,L,M,N;CLOSED=G,F,E,D,C,B,AOPEN=H,I,J,K,L,M,N;CLOSED=G,F,E,D,C,B,A 以此类推直到找到目标或OPEN=宽度优先搜索方法分析宽度优先搜索方法分析u宽度优先搜索是图搜索一般过程的特殊情况，是将OPEN表作为“先进先出”的
16、队列进行操作。u能够保证在搜索树中找到一条通向目标节点的最短途径。u这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，该法失败退出；对于无限图来说，则永远不会终止)。3.2.2 3.2.2 深度优先搜索深度优先搜索u深度优先搜索(depth-first search)。u深度优先搜索基本思想Figure：深度优先搜索示意图从初始节点S开始，按生成规则生成下一级各子节点，检查是否出现目标节点Sg。若未出现，则按“最晚生成的子节点优先扩展”的原则，再用生成规则生成再下一级的子节点，再检查是否出现Sg。如此下去，沿着最晚生成的子节点分枝，逐级“纵向”深入搜索。深度优先搜索出现的问题
17、深度优先搜索出现的问题u在深度优先搜索法中，若目标节点Sg恰好处在最晚生成的子节点分枝树中，则可以较快地求得问题的解，效率比宽度优先搜索法高。u但是，若误陷入无穷分枝，进入“死循环死循环”，则搜索过程无法收敛，不能找到目标节点。图：无深度界限有限深度有先搜索有限深度优先搜索有限深度优先搜索u为了改进深度优先搜索法，以免搜索过程嵌入无穷分枝的死循环，可以引入搜索深度界限搜索深度界限（设为dm ）。当沿“最晚”分枝纵向搜索，达到深度dm时，尚未出现目标节点Sg，则返回，对“次晚”分枝搜索，如此按有限深度（d=dm）搜索下去，直到找到目标节点Sg为止。图：有深度界限有限深度优先搜索算法有限深度优先搜
18、索算法(1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。(2) 如果OPEN为一空表，则失败退出。(3) 把第一个节点(节点n)从OPEN表移到CLOSED表。(4) 如果节点n的深度等于最大深度，则转向(2)。(5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前端。如果没有后裔，则转向(2)。(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。33Figure: 有界深度优先搜索算法框图u列出下列图中树的节点访问序列以满足深度优先搜索策略：12345671089111213深度优先搜索：1，2，5，6，10，11，
19、3，7，12，13，4，8，9例：八数码难题例：八数码难题u按深度优先搜索生成八数码难题搜索树，设深度界限为5。2831476512384765起始棋局目标棋局Figure: 八数码难题的深度优先搜索树u对于如图所示的图，给出深度优先搜索的OPEN表和CLOSED表的变化情况。ABCDEF GH IJKLMNOPQRSTU深度优先搜索的深度优先搜索的OPENOPEN表和表和CLOSEDCLOSED表表OPEN=A;CLOSED=OPEN=A;CLOSED=OPEN=B,C,D;CLOSED=AOPEN=B,C,D;CLOSED=AOPEN=E,F,C,D;CLOSED=B,AOPEN=E,F,
20、C,D;CLOSED=B,AOPEN=K,L,F,C,D;CLOSED=E,B,AOPEN=K,L,F,C,D;CLOSED=E,B,AOPEN=S,L,F,C,D;CLOSED=K,E,B,AOPEN=S,L,F,C,D;CLOSED=K,E,B,AOPEN=L,F,C,D;CLOSED=S,K,E,B,AOPEN=L,F,C,D;CLOSED=S,K,E,B,AOPEN=T,F,C,D;CLOSED=L,S,K,E,B,AOPEN=T,F,C,D;CLOSED=L,S,K,E,B,AOPEN=F,C,D;CLOSED=T,L,S,K,E,B,AOPEN=F,C,D;CLOSED=T,L,S
21、,K,E,B,A以此类推直到找到目标或OPEN=3.2.3 3.2.3 等代价搜索等代价搜索u有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。等代价搜索 = 宽度优先搜索 + 最小代价u搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径具有最小代价的解答路径，与许多这样的广义准则相符合。u宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算等代价搜索算法法。等代价搜索中的记号等代价搜索中的记号u起始节点起始节点记为S S。u从节点i到它的后继节点j的连接弧线代价记为c(i,j)c(
22、i,j)。u从起始节点S到任一节点i的路径代价记为g(i)g(i)。在搜索树上，我们假设g(i)也是从起始节点S到节点i的最少代价路径上的代价，因为它是唯一的路径。等代价搜索算法等代价搜索算法(1) 把起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g(S)=0。(2) 如果OPEN是个空表，则没有解而失败退出。(3) 从OPEN表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i(要是有目标节点的话)；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。(4) 如果节点i为目标节点，
23、则求得一个解。(5) 扩展节点i。如果没有后继节点，则转向第(2)步。(6) 对于节点i的每个后继节点j，计算g(j)=g(i)+c(i，j)，并把所有后继节点j放进OPEN表。提供回到节点i的指针。(7) 转向第(2)步。Figure:等代价搜索算法框图u图中所示是5个城市之间的交通路线图，A城市是出发地，E城市是目的地，两城市之间的交通费用（代价）如图中的数字，求从A到E的最小费用交通路线。ACDBE445723图：旅行交通图ACDBE445723图：旅行交通图u首先将旅行交通图转换为代价树。AC1B1D1E2B2E4D2E1C2E33424572475图：交通图的代价树u转换方法为：从出
24、发城市A开始，将其作为根节点，把与它直接相连的相邻城市作为它的后继节点。对其它节点做同样的扩展。u对代价树做宽度优先搜索，可得到最优解为：AB1E1u从A城市到E城市的最小费用路线为ABE3.3 3.3 启发式搜索启发式搜索u盲目搜索的不足：效率低，耗费过多计算空间与时间。u宽度优先搜索、深度优先搜索，或等代价搜索算法主要的差别是OPEN表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有选择最有希望的节点加以扩展希望的节点加以扩展，则搜索效率将会大为提高。u启发信息启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。例如，人
25、们要阅读一本书人们要阅读一本书, 则书本的摘要和目录就反映了相关的启发信息则书本的摘要和目录就反映了相关的启发信息；u把利用启发信息的搜索方法叫做启发性搜索方法启发性搜索方法。3.3.1 3.3.1 启发式搜索策略启发式搜索策略u启发信息按其用途可分为下列3种：p用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。p在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。p用于决定某些应从搜索树中抛弃或修剪的节点。u我们只讨论上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择选择“最有希望最有希
26、望”的节点作为下一个被扩展的节点的节点作为下一个被扩展的节点。这种搜索叫做有序搜索有序搜索(ordered search)。3.3.2 3.3.2 估价函数估价函数u用来估算节点希望程度的量度，叫做估价函数估价函数(evaluation function)。u一个节点的节点的“希望希望”(promise)有几种定义方法： 估算目标节点到此节点的距离估算目标节点到此节点的距离； 解答路径包括被估价过的节点被估价过的节点，并计算全条路径并计算全条路径的长度的长度。u用符号f来标记估价函数，f(n)表示节点n的估价函数值，即f是从起始节点约束地通过节点n而到达目标节点的最小代价路径上的一个估算代价。
27、3.3.3 3.3.3 有序搜索有序搜索u我们用估价函数估价函数f f来排列GRAPHSEARCH(图搜索)中OPEN表上的节点。OPEN表上的节点按照它们f函数值的递增顺序排列。u某个具有低的估价值的节点较有可能处在最佳路径上。u应用某个算法(例如等代价算法)选择OPEN表上具具有最小有最小f f值的节点作为下一个要扩展的节点值的节点作为下一个要扩展的节点。选择最有希望的节点作为下一个要扩展的节点，这种搜索方法叫做有序搜索有序搜索(ordered search)或最最佳优先搜索佳优先搜索(best-first search) 。有序状态空间搜索算法有序状态空间搜索算法(1) 把起始节点s放到
28、OPEN表中，计算f(s)并把其值与节点s联系起来。(2) 如果OPEN是个空表，则失败退出，无解。(3) 从OPEN表中选择一个f值最小的节点i。如果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。(4) 把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。(5) 如果i是个目标节点，则成功退出，求得一个解。(6) 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：a.计算f(j)。 b.如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点
29、时记住一个解答路径。c.如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则:i.以此新值取代旧值。ii.从j指向i，而不是指向它的父辈节点。iii.如果节点j在CLOSED表中，则把它移回OPEN表。(7) 转向(2)，即GO TO(2)。有序状态空间搜索算法有序状态空间搜索算法Figure:有序搜索算法框图有序搜索技术小结有序搜索技术小结u宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。u对于宽度优先搜索，我们选择f(i)作为节点i的深度。对于等代价搜索，f(i)是从起始节点至节点i这段路径的代价。u有序
30、搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。u如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。 例：八数码难题例：八数码难题u用八数码难题的例子来说明过程GRAPHSEARCH是如何应用估如何应用估价函数排列节点的价函数排列节点的。u采用简单的估价函数f(n)f(n)= =d(n)d(n)+ +W(n)W(n)其中：d(n)是搜索树中节点n的深度W(n)用来计算对应于节点n的数据库中错放的棋子个数。2 8 31 47 6 51 2 3 8 47 6 5
31、目标棋局起始棋局u起始节点棋局f值等于：0+3=3u采用简单的估价函数f(n)f(n)= =d(n)d(n)+ +W(n)W(n)其中：d(n)是搜索树中节点n的深度W(n)用来计算对应于节点n的数据库中错放的棋子个数。Figure: 八数码难题的有序搜索树2 8 31 47 6 51 2 3 8 47 6 5目标棋局起始棋局u正确地选择估价函数选择估价函数对确定搜索结果具有决定性的作用。 使用不能识别某些节点真实希望的估价函数会形成非最小代价路径； 而使用一个过多过多地估计了全部节点希望的估价函数又会扩展过多的节点。3.3.4 A3.3.4 A* *算法算法uA*算法的估价函数p让我们描述一
32、个特别的估价函数，这个估价函估价函数数f f使得在任意节点上其函数值f(n)能估算出从从节点节点s s到节点到节点n n的最小代价路径的代价与从节的最小代价路径的代价与从节点点n n到到目标节点目标节点t t的最小代价路径的代价之总和的最小代价路径的代价之总和。即f(n)是约束通过节点n的一条最小代价路径的代价的一个估计。p因此，OPEN表上具有最小f值的那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。几个有用的记号几个有用的记号u令k k( (n ni i, ,n nj j) )表示任意两个节点ni和nj之间最小代价路径的实际代价。于是，从节点n到某个具体的
33、目标节点ti，某一条最小代价路径的代价可由k(n，ti)给出。u对所有从s开始可达到n的路径来说，令函函数数g*定义为g*(n)=k(s，n)。几个有用的记号几个有用的记号u令h h* *( (n n) )表示整个目标节点集合ti上所有k(n，ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径。u定义函数函数f f* *，使得在任一节点n上其函数值f*(n)就是从节点s到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即 f*(n)=g*(n)+ h*(n)。
34、几个有用的记号几个有用的记号u我们希望估价函数估价函数f f是是f f* *的一个估计的一个估计，此估计可由下式给出：f(n)=g(n)+h(n)其中：g是g*的估计；h是h*的估计。u对于g(n)来说，一个明显的选择就是搜索树中从s到n这段路径的代价，这一代价可以由从n到s寻找指针时，把所遇到的各段弧线的代价加起来给出。 这个定义包含了g(n)g*(n)。u对于h(n)来说，它依赖于有关问题的领域的启发信息。我们把h h叫做启发函数叫做启发函数。A A算法和算法和A A* *算法的定义算法的定义u定义定义1 1:在GRAPHSEARCH过程中，如果依据f(x)=g(x)+h(x)重排OPEN
35、表，该过程为A A算法算法。u定义定义2 2:在A算法中，如果对所有的x，h(x)h*(x)成立,则称h(x)为h*(x)的下界下界，它表示某种偏于保守的估计。u定义定义3 3:采用h*(x)的下界h(x)为启发函数的A算法，称为A A* *算法算法。当h=0时，A*算法就变为有序搜索算法。注：A* 之所以加一个 * 号，是因为它的启发式函数是有限制的，这个限制确保它能找到绝对最优解，去掉这个限制，就是 A 算法了。A A* *算法算法(1) 把s放入OPEN表，记f=h，令CLOSED为空表。(2) 重复下列过程，直至找到目标节点止。若OPEN为空表，则宣告失败。(3) 选取OPEN表中未设
36、置过的具有最小f值的节点为最佳节点BESTNODE，并把它放入CLOSED表。(4) 若BESTNODE为一目标节点，则成功求得一解。(5) 若BESTNODE不是目标节点，则扩展之，产生后继节点SUCCSSOR。(6) 对每个SUCCSSOR进行下列过程：(a) 建立从SUCCSSOR返回BESTNODE的指针。(b) 计算g(SUC)=g(BES)+g(BES,SUC)。(c) 如果SUCCSSOROPEN，则称此节点为OLD，并把它添至BESTNODE的后继节点表中。(d) 比较新旧路径代价。如果g(SUC)g(OLD)，则重新确定OLD的父辈节点为BESTNODE，记下较小代价g(OL
37、D)，并修正f(OLD)值。(e) 若OLD节点的代价较低或一样，则停止扩展节点。(f) 若SUCCSSOR不在CLOSE表中，则看其是否在CLOSED表中。(g) 若SUCCSSOR在CLOSE表中，则转向(c)。(h) 若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，则把它放入OPEN表中，并添入BESTNODE后裔表，然后转向(7)(i) 计算f值。(7) GO LOOPFigure: A*算法参考框图A A* *算法的应用算法的应用 计算机网络路由算法 机器人探路 交通路线导航 游戏设计 问题求解与搜索策略问题求解与搜索策略u按照一定的策略或规则，从知识库中寻找可利用的知
38、识，从而构造出一条使问题获得解决的推理路线的过程，称为搜索搜索。u搜索包含两层含义：p要找到从初始事实到问题最终答案的一条推理路线推理路线。p所找到的这条路线是时间和空间复杂度时间和空间复杂度最小最小的求解路线。u什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？搜索：搜索：按照一定策略或规则，从知识库中寻找可利用的知识，构造一条使问题获得解决的推理路线的过程。p 有两大类搜索方法，即盲目搜索和启发式搜索。p 盲目搜索：盲目搜索：按照预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。搜索带有盲目性，效率不高。p 启发式搜索：启发式搜索：根据问题本身的特性或搜索过程中产
39、生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，并找到最优解。求解效率更高，更易于求解复杂的问题。 u问题求解与搜索策略问题求解与搜索策略盲目搜索启发性搜索图搜索策略宽度优先搜索深度优先搜索等代价搜索有序搜索A*算法有限深度优先搜索需要掌握并能写出以上搜索原理的各个算法！u盲目搜索包括宽度优先搜索、深度优先搜索和等代价搜索。u启发式搜索主要讨论有序搜索和最优搜索A*算法。启发式搜索运用启发信息。正确选择估价函数，对于寻求最小代价路径或解树至关重要。启发式搜索比盲目搜索有效得多，运用较为普遍。u有界深度优先搜索在某种意义上具有一定的启发性。从搜索效率上看，有界深度优先搜索
40、较好，宽度优先搜索次之，深度优先搜索较差。但如果有解，则宽度优先搜索和深度优先搜索一定能够找到解答，无论付出多大代价；而有界深度优先搜索则可能丢失某些解。搜索效率比较搜索效率比较u列出下列图中树的节点访问序列以满足宽度优先搜索策略：12345671089111213宽度优先搜索：1，2，3，4，5，6，7，8，9，10，11，12，13u列出下列图中树的节点访问序列以满足深度优先搜索策略：12345671089111213深度优先搜索：1，2，5，6，10，11，3，7，12，13，4，8，9例：八数码难题例：八数码难题u把宽度优先搜索应用于八数码难题时所生成的搜索树。283147651238
41、4765起始棋局目标棋局u搜索树上的所有节点都标记它们所对应的状态描述，节点扩展的顺序按顺时针方向移动空格。图中最后一个节点是目标节点。Figure: 八数码难题的宽度优先搜索树例：八数码难题例：八数码难题u按深度优先搜索生成八数码难题搜索树，设深度界限为5。2831476512384765起始棋局目标棋局Figure: 八数码难题的深度优先搜索树u对于如图所示的图，给出宽度优先搜索的OPEN表和CLOSED表的变化情况。ABCDEF GH IJKLMNOPQRSTU宽度优先搜索的宽度优先搜索的OPENOPEN表和表和CLOSEDCLOSED表表OPEN=A;CLOSED=OPEN=A;CLO
42、SED=OPEN=B,C,D;CLOSED=AOPEN=B,C,D;CLOSED=AOPEN=C,D,E,F;CLOSED=B,AOPEN=C,D,E,F;CLOSED=B,AOPEN=D,E,F,G,H;CLOSED=C,B,AOPEN=D,E,F,G,H;CLOSED=C,B,AOPEN=E,F,G,H,I,J;CLOSED=D,C,B,AOPEN=E,F,G,H,I,J;CLOSED=D,C,B,AOPEN=F,G,H,I,J,K,L;CLOSED=E,D,C,B,AOPEN=F,G,H,I,J,K,L;CLOSED=E,D,C,B,AOPEN=G,H,I,J,K,L,M;CLOSED=
43、F,E,D,C,B,AOPEN=G,H,I,J,K,L,M;CLOSED=F,E,D,C,B,AOPEN=H,I,J,K,L,M,N;CLOSED=G,F,E,D,C,B,AOPEN=H,I,J,K,L,M,N;CLOSED=G,F,E,D,C,B,A 以此类推直到找到目标或OPEN=u对于如图所示的图，给出深度优先搜索的OPEN表和CLOSED表的变化情况。ABCDEF GH IJKLMNOPQRSTU深度优先搜索的深度优先搜索的OPENOPEN表和表和CLOSEDCLOSED表表OPEN=A;CLOSED=OPEN=A;CLOSED=OPEN=B,C,D;CLOSED=AOPEN=B,C,
44、D;CLOSED=AOPEN=E,F,C,D;CLOSED=B,AOPEN=E,F,C,D;CLOSED=B,AOPEN=K,L,F,C,D;CLOSED=E,B,AOPEN=K,L,F,C,D;CLOSED=E,B,AOPEN=S,L,F,C,D;CLOSED=K,E,B,AOPEN=S,L,F,C,D;CLOSED=K,E,B,AOPEN=L,F,C,D;CLOSED=S,K,E,B,AOPEN=L,F,C,D;CLOSED=S,K,E,B,AOPEN=T,F,C,D;CLOSED=L,S,K,E,B,AOPEN=T,F,C,D;CLOSED=L,S,K,E,B,AOPEN=F,C,D;CLOSED=T,L,S,K,E,B,AOPEN=F,C,D;CLOSED=T,L,S,K,E,B,A以此类推直到找到目标或OPEN=u什么是估价函数？在估价函数中，g(x)和h(x)各起什么作用？p 估价函数是一种用来表示和度量搜索树中节点的“希望”程度的函数，其任务是估计待搜索节点的重要程度，为它们排定次序。p 在估价函数中，g(x)为初始节点S0到节点x实际付出的代价。h(x)是从节点x到目标节点Sg的最优路径的估计代价。搜索的启发信息主要由h(x)来体现，所以h(x)称作启发函数。
