人工智能导论：搜索问题.doc

第1章 搜索问题人类的思维过程，可以看作是一个搜索的过程。从小学到现在，你一定遇到过很多种的智力游戏问题，比如说传教士和野人问题。有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次至多可供2人乘渡。问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目（但允许在河的某一岸或者船上只有野人而没有传教士）。如果你来做这个智力游戏的话，在每一次渡河之后，都会有几种渡河方案供你选择，究竟哪种方案才有利于在满足题目所规定的约束条件下顺利过河呢？这就是搜索问题。经过反复努力和试探，你终于找到了一种解决办法。在高兴之余，你马上可能又会想到，这个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题就是本章我们要介绍的搜索问题。一般地，很多问题可以转化为状态空间的搜索问题。S0问题全状态空间搜索空间解路径Sg图1.1搜索空间示意图比如传教士和野人问题，当我们用在河的左岸的传教士人数、野人人数和船的情况表示问题时，该问题的初始状态可以用三元组表示为（3，3，1），结束状态可以表示为（0，0，0），而中间状态则可以表示为（2，2，0）、（3，2，1）、（3，0，0）等，每个三元组对应了三维空间上的一个点，而问题的解，则是一个合法状态的序列，其中序列的第一个状态是问题的初始状态，而最后的一个状态则是问题的结束状态。介于初始状态和结束状态之间的则是中间状态。除了第一个状态外，该序列中任何一个状态，都可以通过一条规则，由与他相邻的前一个状态转换得到。图1.1给出了一个搜索问题的示意图。其含义是如何在一个比较大的问题空间中，只通过搜索比较小的范围，就找到问题的解。使用不同的搜索策略，找到解的搜索空间范围是有区别的。一般来说，对大空间问题，搜索策略是要解决组合爆炸的问题。通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好的某种固定排序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法，一般统称为无信息引导的搜索策略。另一种是考虑问题领域可应用的知识，动态地确定规则的排序，优先调用较合适的规则使用，这就是通常称为启发式搜索策略或有信息引导的搜索策略。本章及下一章将介绍几个常用的搜索策略。1.1 回溯策略（Backtracking Strategies）这里介绍的回溯搜索策略，在有些书中称为“深度优先”搜索，而在本书中“深度优先”搜索有另外的含义，具体请见“深度优先”搜索一节。回溯策略属于盲目搜索的一种。所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。下面我们以一个简单的迷宫问题为例，说明回溯策略的基本思想。迷宫问题如图x所示，迷宫的入口坐标为（0,0），出口坐标为（5,4），图中的粗实线是可以通行的道路。问如何找到一条从入口到出口的路线。图中箭头给出了按照回溯策略进行搜索的过程。这里的规则，假定在任何一个路口，按照“上、右、下、左”的次序前进，当无路可走或者试探过所有前进方式后则回溯到前一个路口。从（0,0）出发，向上前进到（0,1），前进到（1,1），再一次前进到（1,2）、（1,3）。由于（1,3）无路可走，则回溯到它的前一个路口（1,2）。在（1,2）处已经尝试过向上前进，这次则向右前进到（2,2），然后到达（3,2）。在（3,2）处先向上走到达（3,3），由于再无路可走，又回溯到（3,2），向右到达（4,2）。（4,2）无路可走再次回溯到（3,2）。到此为止（3,2）处已经尝试了所有可能的前进方式，只能再回溯到（2,2）。在（2,2）处尝试还没有走过的向下，进入到（2,1）。由（2,1）逐次前进到（3,1）、（4,1）、（5,1）、（5,2）、（5,3），最后到达出口（5,4）。到此为止，搜索结束。那么，如何得到从迷宫入口到出口的路线呢？在搜索过程中，每前进一步都要记录所走的方向（向可以走的方向前进一步，可以认为是一条规则），如果发生了回溯，则删除该方向的记录。对照图上标示的箭头，如果一个路段旁边有两个方向相反的箭头，则这两个箭头都需要删除，最后保留的箭头所指示的路线，就是从入口到出口的路线。在这个例子中，得到路线就是（0,0）、（0,1）、（1,1）、（1,2）、（2,2）、（2,1）、（3,1）、（4,1）、（5,1）、（5,2）、（5,3）、（5,4）。出口xy01234510234入口 图x，迷宫问题回溯策略可以有多种实现的方法，其中递归法是一种最直接的实现方法。下面定义一个递归过程BACKTRACK，实现回溯搜索策略。其功能是：如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径；如果从当前状态DATA到目标状态没有路径存在，则返回FAIL。下面用类LISP语言的形式给出一个具有两个回溯点（即设置两个回溯条件）的简单算法，并通过四皇后问题说明算法的运行过程。在下面的算法中，“；”号后面的内容表示注释。1递归过程BACKTRACK(DATA)递归过程BACKTRACK(DATA) IF TERM(DATA)，RETURN NIL；TERM取真即找到了目标，则过程返回空表NIL。也就是说，如果当前状态就是目标，则不需再搜索就结束。IF DEADEND(DATA)，RETURN FAIL；DEADEND取真，表示该状态不合法，则过程返回FAIL，必须回溯。RULES：APPRULES(DATA)；APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。LOOP：IF NULL(RULES)，RETURN FAIL；如果NULL取真，则表示规则已用完仍未找到目标，过程返回FAIL，必须回溯。R：FIRST(RULES)；取第一个可应用规则。RULES：TAIL(RULES)；从可应用规则表中删除第一个规则。RDATA：GEN(R，DATA)；将规则R作用于当前状态DATA，生成DATA的下一个状态RDATA。PATH：BACKTRACK(RDATA)；对RDATA递归调用本过程。IF PATHFAIL，GO LOOP；当PATHFAIL时，表示递归调用未能找到从RDATA到达目标的路径，则转移尝试调用DATA的下一条规则进行新的尝试。RETURN CONS(R，PATH)；到达这一步说明递归调用找到了从RDATA到目标的路径PATH。这样将从DATA产生RDATA的规则R从前插入到PATH，就得到了从DATA到达目标的路径。过程返回表示该解路径的规则表（或局部解路径子表）。递归过程BACKTRACK是将循环与递归结合在一起的。下面通过一个示意图，说明一下该算法的思想。如下图所示，当前状态n相当于算法中的DATA，(r1，r2，ri-1，ri)是n的可应用规则集RULES，m1、m2、mi-1、mi是n的i个子状态，它们分别可以通过r1、r2、ri-1、ri这i个规则作用于状态n得到。t是目标状态。当前状态nm1m2mi-1mi目标状态tr1r2ri-1ri为了得到从当前状态n到目标状态t的路径，可以从两个方面考虑。一是要探索n的i个子状态m1、m2、mi-1、mi中，通过哪一个状态可以到达目标状态t。这一点，算法是通过循环实现的，每次从n的可应用规则集中，选取一个规则作用于n。所体现的是“横向”探索。二是“纵向”探索。为了探索n的某一个子状态mk (k=1，2，i)是否可以达到目标状态t，算法通过递归来完成这个试探。整个算法的思想就是：要想求得从n到t的路径，首先查看m1到t是否有路径存在。如果从m1到t有路径存在，则在该路径前加上r1，就得到了从n到t的路径（这里的路径是用规则的集合表示的）。在试探m1到t有没有路径的过程中，m1又成为了当前状态，又要探索m1的子状态到t是否有路径存在，如此进行下去。递归所起的正是这样的作用。如果从m1到t没有路径存在，算法则试探m2到t是否存在路径，它同样也要试探m2的子状态到t有无路径存在，等等。所以算法中循环和递归是交叉进行的，一方面是“横向”探索，一方面是“纵向”探索。下面对这个算法作几点说明。首先解释一下其中的变量、常量、谓词、函数等符号的意义。变量符号DATA、RULES、R、RDATA、PATH分别表示当前状态、（某个状态的）可应用规则集、当前调用规则、新生成的状态（即R作用于DATA产生的状态）、当前解路径表。常量符号NIL、FAIL、LOOP分别表示空表、回溯点标记、循环标号。当状态变量DATA满足结束条件时，TERM(DATA)取真；当DATA为非法状态时，DEADEND(DATA)取真；当规则集变量表RULES取空时，NULL取真。函数RETURN、APPRULES、FIRST、TAIL、GEN、GO、CONS的作用是：RETURN返回其自变量值；APPRULES求可应用规则集；FIRST和TAIL分别取可应用规则集的第一个规则和取除第一个规则以外的所有规则；GEN调用规则R生成一个新状态；GO执行转移；CONS构造新表，把其第一个自变量加到一个表（第二个自变量）的前面。BACKTRACK(RDATA)表示调用递归过程作用于新自变量上。这里再说明一下该过程的运行情况。当某一个状态Sg满足结束条件时，算法才在第1步结束并返回NIL，此时BACKTRACK(Sg)NIL。失败退出发生在第2、4步，第2步是处理不合法状态的回溯点，而第4步是处理全部规则应用均失败时的回溯点。若处在递归调用过程期间失败，过程会回溯到上一层继续运行，而在最高层失败则整个过程宣告失败退出。构造成功结束时的规则表在第10步完成。算法第3步实现可应用规则的排序，可以是固定排序或根据启发信息排序。这个简单的BACKTRACK过程只设置了两个回溯点，可用于求解N皇后这类性质的问题，下面以四皇后问题为例进一步说明算法的运行过程。2四皇后问题在一个44的国际象棋棋盘上，一次一个地摆放四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。图1.2给出棋盘的几个状态，其中a，b满足目标条件，c，d，e为不合法状态，即不可能构成满足目标条件的中间状态。QQQQQQQQQQQQQQQ(a)(b)(c)(d)(e)图1.2四皇后问题棋盘的几个状态四皇后问题的一个状态可以用一个表表示，表的元素为ij(1i, j4)，表示棋子所在的行和列。因最多只有4个棋子，故表元素个数最多为4。图1.2中a，b分别可以记为(12 24 31 43)和(13 21 34 42)，c，d，e分别可以记为(11 21)，(11 22)，(11 23 31)等等。可以简单地定义规则Rij(1i, j4)，表示在满足前提条件下，在第i行第j列摆放一个棋子。当规则序列以R11，R12，R13，R14，R21，R44这种固定排序方式调用BACKTRACK时，四皇后问题的搜索示意图如图1.3所示（为简单起见，每个状态只写出其增量部分）。可以看出，总共回溯22次，主过程结束时返回规则表(R12 R24 R31 R43)。( )(11)(21)(22)(23)(24)(31)(32)(33)(34)(31)(32)(33)(34)(41)(42)(43)(44)(12)(21)(22)(23)(24)(31)(41)(42)(43)图1.3 固定排序搜索树在回溯策略中，也可以通过引入一些与问题有关的信息来加快搜索到解的速度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置数是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的，可以想象，如果当把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留有的余地就大，找到解的可能行也大；反之留有的余地就小，找到解的可能行也小。如下图所示，（a）图皇后所影响的最长对角线是3，而（b）图皇后所影响的最长对角线是2，显然在（b）图位置放置皇后找到解的可能性大于（a）图位置。利用这样的信息对可应用规则集进行动态排序，可以加快找到解的速度。图1.4给出采用这种方法后四皇后问题的搜索树，比较图1.3和图1.4，可以说明这种方法对于加快找到解的速度是很有效的，只回溯了2次就找到了问题的解。QQ（a） （b）( )(12)(21)(24)(31)(42)(43)图 1.4 动态排序搜索树3递归过程BACKTRACK1(DATALIST，BOUND)在前面的回溯算法BACKTRACK中，设置了两个回溯点，一个是当遇到非法状态时回溯，一个是当试探了一个状态的所有子状态后，仍然找不到解时回溯。对于某些问题，可能会遇到这样的问题：一个是问题的某一个（或者某些）分支具有无穷个状态，算法可能会落入某一个“深渊”，永远也回溯不回来，这样，就不能找到问题的解。另一个问题是，在某一个分支上具有环路，搜索会在这个环路中一直进行下去，同样也回溯不出来，从而找不到问题的解。如下图所示。为了解决这两个问题，下面将给出回溯算法BACKTRACK1，该算法比前面的回溯算法又增加了两个回溯点：一个是用一个参数BOUND来限制算法所能够搜索的最大深度，当当前状态的深度达到了限制深度时，算法将强制进行回溯，从而可以避免落入“深渊”；另一个是将过程的参数用从初始状态到当前状态的表来替代原来的当前状态，当新的状态产生时，查看是否已经在该表中出现过了，如果出现过，则表明有环路存在，算法也将进行回溯，从而解决了环路问题。改进后的算法如下：递归过程BACKTRACK1(DATALIST，BOUND)；DATALIST为从初始状态到当前状态的逆序表，即表的第一个元素为当前状态，最后一个状态为初始状态。BOUND为给定的最大深度限制。DATA：FIRST(DATALIST)；设置DATA为当前状态IF MEMBER(DATA，TAIL(DATALIST)，RETURN FAIL；TAIL是取尾操作，表示取表DATALIST中除了第一个元素以外的所有元素。如果DATA在TAIL(DATALIST)中存在，则表示有环路出现，过程返回FAIL，必须回溯。IF TERM(DATA)，RETURN NIL；TERM取真即找到了目标，则过程返回空表NIL。也就是说，如果当前状态就是目标，则不需再搜索就结束。IF DEADEND(DATA)，RETURN FAIL；DEADEND取真，表示该状态不合法，则过程返回FAIL，必须回溯。IF LENGTH(DATALIST)BOUND，RETURN FAIL；LENGTH计算DATALIST的长度，即搜索的深度，当搜索深度大于给定值BOUND时，则过程返回FAIL，必须回溯。RULES：APPRULES(DATA)；APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则排列）排列后赋给RULES。LOOP：IF NULL(RULES)，RETURN FAIL；NULL取真，即规则用完仍未找到目标，过程返回FAIL，必须回溯。R：FIRST(RULES)；取第一个可应用规则。RULES：TAIL(RULES)；从可应用规则表中删去第一个规则。RDATA：GEN(R，DATA)；将规则R作用于当前状态DATA，生成DATA的下一个状态RDATA。RDATALIST：CONS(RDATA，DATALIST)；将下一个状态RDATA从前插入到表DATALIST中。PATH：BACKTRACK1(RDATALIST，BOUND)；递归调用本过程。IF PATHFAIL，GO LO0P；当PATHFAIL时，表示递归调用未能找到从RDATA到达目标的路径，则转移尝试调用DATA的下一条规则进行新的尝试。RETURN CONS(R，PATH)；到达这一步说明递归调用找到了从RDATA到目标的路径PATH。这样将从DATA产生RDATA的规则R从前插入加入到PATH，就得到了从DATA到达目标的路径。过程返回表示该解路径的规则表（或局部解路径子表）。这个算法与前一个算法的差别是递归过程自变量是状态的链表。在过程BACKTRACK1中，形参DATALIST是从初始状态到当前状态的逆序表，即初始状态排在表的最后，而当前状态排在表的最前面。返回值同前面的算法一样，是以规则序列表示的路径表（当求解成功时），或者是FAIL（当求解失败时）。此外在第2、5步增设了两个回溯点以检验是否重访已出现过的状态和限定搜索深度范围，这分别由谓词MEMBER和，函数LENGTH，参数BOUND实现。另外，上述两个算法得到的解路径均是以规则表表示的，也可以修改为用状态表表示路径，只需对算法进行简单修改就可完成，这里不再赘述。推广的回溯算法可应用于一般问题的求解，但这两个算法只描述了回溯一层的情况，即第n层递归调用失败，则控制退回到(n-1)层继续搜索。实际上往往造成深层搜索失败在于浅层原因引起，因此也可以利用启发信息，分析失败的原因，再回溯到合适的层次上，这就是多层回溯策略的思想，目前已有一些系统使用了这种策略。1.2 图搜索策略回溯搜索策略的一个特点就是只保留了从初始状态到当前状态的一条路径（无论是BACKTRACK还是BACKTRACK1都是如此），当回溯出现时，回溯点处进行的搜索将被算法“忘记”，其好处是节省了存储空间，而不足是这些被回溯掉的已经搜索过的部分，不能被以后使用。与此相对应的，将所有搜索过的状态都记录下来的搜索方法称为“图搜索”，搜索过的路径除了可以重复利用外，其最大的优点是可以更有效地利用与问题有关的一些知识，从而达到启发式搜索的目的。实际上图搜索策略是实现从一个隐含图中，生成出一部分确实含有一个目标节点的显式表示子图的搜索过程。图搜索策略在人工智能系统中广泛被使用，本节将对算法及涉及的基本理论问题进行讨论。首先回顾一下图论中几个术语的含义。节点深度：根节点的深度为0，其他节点的深度规定为父节点深度加1，即dn+1dn1。路径：设一节点序列为(n0，n1，ni，nk)，对i1，2，k，若任一节点ni-1都具有一个后继节点ni，则该节点序列称为从节点n0到节点nk长度为k的一条路径。路径耗散值：令C(ni，nj)为节点ni到nj这段路径（或弧线）的耗散值，一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。路径耗散值可按如下递归公式计算：C(ni，t)C(ni，nj)+C(nj，t)C(nj，t)为nit这条路径的耗散值。耗散值是一个抽象的概念，反应的是一个路径的代价。可以是一段路程的长度，也可以是走完该路程所需要花费的时间，或者花费的金额等。扩展一个节点：后继节点操作符（相当于可应用规则）作用到节点（对应于某一状态描述）上，生成出其所有后继节点（新状态），并给出连接弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点。扩展节点可使定义的隐含图生成为显式表示的状态空间图。下面首先给出一般的图搜索算法框架，该框架的一些内容具体化后，就可以得到不同的图搜索算法。一般图搜索算法框架G:G0(G0s)，OPEN:(s)；G表示图，s为初始节点，设置OPEN表，最初只含初始节点。CLOSED:( )；设置CLOSED表，起始设置为空表。LOOP: IF OPEN( )，THEN EXIT(FAIL)；n:FIRST(OPEN)，REMOVE(n，OPEN)，ADD(n，CLOSED)；称n为当前节点。IF GOAL(n)，THEN EXIT(SUCCESS)；由n返回到s路径上的指针，可给出解路径。EXPAND(n)mi，G:ADD(mi，G)；子节点集mi中不包含n的父辈节点。标记和修改指针ADD(mj，OPEN)，并标记mj连接到n的指针；mj为OPEN和CLOSED中未出现过的子节点，mimjmkml。计算是否要修改mk，m1到n的指针；mk为已出现在OPEN中的子节点，m1为已出现在CLOSED中的子节点。计算是否要修改m1到其后继节点的指针；对OPEN中的节点按某种原则重新排序；GO LOOP；这是一个一般的图搜索过程，通过不断的循环，过程便生成出一个显式表示的图G（搜索图）和一个G的子集T（搜索树）。该搜索树T是由第7步中标记的指针决定，除根节点s外，G中每个节点只有一个指针指向G中的一个父节点，显然树中的每一个节点都处在G中。由于图G是无环的，因此可根据树定义任一条特殊的路径。可以看出，OPEN表上的节点，都是搜索树的端节点，即那些已经生成出来但至今尚未被选作为扩展的节点；而CLOSED表上的节点，可以是已被扩展而不能生成后继节点的那些端节点，也可以是树中的非端节点。以上的图搜索过程，在第8步要对OPEN表上的节点按照某种原则进行排序，以便在第4步能选出一个“最好”的节点优先扩展。不同的排序方法便可构成形式多样的专门搜索算法，这在后面还要进一步讨论。如果选出待扩展的节点是目标节点，则算法在第5步成功结束，并可通过一步步追踪到s的指针给出解路径。如果在该过程的某个循环中，搜索树不再剩有待选的节点，即OPEN表变空时，则过程失败结束，问题找不到解。11234561123456（a）（b）ss图1.5 扩展节点6和节点1得到的搜索图现在再说明一下第7步中标记和修改指针的问题。如果要搜索的隐含图是一棵树，则可肯定第6步生成的后继节点不可能是以前生成过的，这时搜索图就是搜索树，不存在mk、m1这种类型的子节点，因此不必进行修改指针的操作。如果要搜索的隐含图不是一棵树，则有可能出现mk这样的子节点，就是说这时又发现了到达mk的新通路，这样就要比较不同路径的耗散值，把指针修改到具有较小耗散值的路径上。例如，图1.5所示的两个搜索图中，实心圆点在CLOSED表中（已扩展过的节点），空心圆点则在OPEN表中（待扩展点）。先设下一步轮到要扩展节点6，并设生成的两个子节点，其中有一个节点4已在OPEN中，那么原先路径(s324)耗散值为5（设每段路径均为单位耗散，即相邻两个节点间的耗散值为1），新路径(s64)的耗散值为4，所以节点4的指针应由指向节点2修正到指向节点6，如图1.5(a)所示。接着设下一循环要扩展节点1，若节点1只生成一个子节点2（它已在CLOSED中），显然这时节点2原先指向节点3的指针，要修改到指向节点1，由此又引起子节点3的指针又修改为指向节点2，如图1.5(b)所示。1.3 无信息图搜索过程无信息图搜索过程是在算法的第8步中使用任意排列OPEN表节点的顺序，通常有两种排列方式，分别构成了深度优先搜索和宽度优先搜索。1深度优先在有些书中，“深度优先”指的是本书1.1节介绍的“回溯策略”，本书中的“深度优先”算法与“回溯策略”有所不同，是一种图搜索算法。所谓深度优选，就是每次循环中，优选扩展OPEN表中深度最深的节点。下面先给出深度优先算法，后面再给出对算法的说明。过程DEPTHFIRSTSEARCHG:=G0(G0=s)，OPEN:=(s)，CLOSED:=( )；LOOP：IF OPEN( )THEN EXIT(FAIL)；n:FIRST(OPEN)；IF GOAL(n) THEN EXIT(SUCCESS)；REMOVE(n，OPEN)，ADD(n，CLOSED)；EXPAND(n)mi；G:ADD(mi，G)；ADD(mj，OPEN)，并标记mj到n的指针；把不在OPEN或CLOSED中的节点放在OPEN表的最前面，使深度大的节点可优先扩展。GO LOOP；该算法是根据一般的图搜索算法改变而成的。所谓深度优先搜索，就是在每次扩展一个节点时，选择到目前为止深度最深的节点优先扩展。这一点是在算法的第7步体现出来的。第7步中的ADD(mj，OPEN)表示将被扩展节点n的所有新子节点mj加到OPEN表的前面。开始时，OPEN表中只有一个初始节点s，s被扩展，其子节点被放入OPEN表中。在算法的第3步，OPEN表的第一个元素设为n被取出扩展，这时节点n的深度在OPEN表中是最大的，OPEN表中的其他节点的深度都不会超过n的深度。n的子节点被放到OPEN表的最前面。由于子节点的深度要大于父节点的深度，实际上OPEN表是按照节点的深度进行排序的，深度深的节点被排在了前面，而深度浅的节点被放在了后面。这样当下一个循环再次取出OPEN表的第一个元素时，实际上选择的就是到目前为止深度最深的节点，从而实现了深度优先的搜索策略。一般情况下，当问题有解时，深度优先搜索不但不能保证找到最优解，也不能保证一定能找到解。如果问题的状态空间是有限的，则可以保证找到解，当问题的状态空间是无限的时，则可能陷入“深渊”，而找不到解。为此，像回溯算法一样，可以加上对搜索的深度限制。其方法是在算法的第7步，当节点的深度达到限制深度时，则不将其子节点加入到OPEN表中，从而实现对搜索深度的限制。当然，这个深度限制应该设置的合适，深度过深影响搜索的效率，而深度过浅，则可能影响找到问题的解。下面以八数码问题为例，说明深度优先搜索是如何求解问题的。八数码问题（EightPuzzle）描述如下：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有18数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。问题的解答其实就是给出一个合法的走步序列。1 2 38 47 6 52 31 8 47 6 5 初始状态 目标状态 图 八数码问题图x给出了用深度优先方法求解八数码问题的搜索树，其中深度限制设置为4。图中圆圈中的序号表示节点的扩展顺序。除了初始节点外，每个节点用箭头指向其父节点，当搜索到目标节点后，沿着箭头所指反向追踪到初始节点，即可得到问题的解答。图x 用深度优先搜索求解八数码问题2宽度优先同深度优先算法一样，宽度优先算法也是从一般的图搜索算法变化而成。在深度优先搜索中，每次选择深度最深的节点首先扩展，而宽度优先搜索则正好相反，每次选择深度最浅的节点优先扩展。与深度优先算法不同的只是第7步，这里ADD(OPEN，mj)表示将mj类子节点放到OPEN表的后边，从而实现了对OPEN表中的元素按节点深度排序，只不过这次将深度浅的节点放在OPEN表的前面了，而深度深的节点被放在了OPEN表的后边。当问题有解时，宽度优先算法一定能找到解，并且在单位耗散的情况下，可以保证找到最优解。过程BREADTHFIRSTSEARCHG:=G0(G0=s)，OPEN:=(s)，CLOSED:=( )；LOOP: IF OPEN( ) THEN EXIT(FAIL)；n:FIRST(OPEN)；IF GOAL(n) THEN EXIT(SUCCESS)；REMOVE(n，OPEN)，ADD(n，CLOSED)；EXPAND(n)mi，G:ADD(mi，G)；ADD(OPEN，mj)，并标记mj到n的指针；把不在OPEN或CLOSED中的节点放在OPEN表的后面，使深度浅的节点可优先扩展。GO LOOP；对于前面的八数码问题，同样可以用宽度优先进行求解，搜索树如图x所示。3渐进式回溯策略宽度优先搜索具有的优势是，在单位耗散值的情况下，当问题有解时必能找到最优解。其不足是产生的节点数随目标所在的深度呈几何增长，当最优解路径比较长时，会消耗大量的内存空间，以至于因占用空间过大而不能求解。回溯策略虽然不一定找到最优解，且生成的节点数并不少，但由于其在回溯过程中发生回溯的节点并不保留，仅保留从初始状态到当前状态的一条路径，在设置了最大搜索深度限制BOUND的情况下，需要保留的节点数最多仅为BOUND+1个，具有占用空间小的优势。能否把回溯策略与宽度优先的思想结合起来，在小空间下实现最优路径的求解呢？我们首先分析一下为什么宽度优先可以找到最优解。宽度优先搜索，每次优先扩展深度浅的节点，在扩展了初始节点之后，首先扩展深度为1的节点，然后再扩展深度为2的节点，扩展的节点深度一层层逐渐加深，直到找到目标节点为止。在搜索树上体现的是一种“横着走”的形式，逐步加深搜索深度。如果问题是单位耗散值的话，其节点深度就是从初始节点到该节点路径的耗散值，所以一旦扩展出了目标节点，就找到了从初始节点到目标节点的最优路径，即耗散值最小的路径。在1.1节给出的回溯过程BACKTRACK1中，有一个控制搜索深度的参数BOUND，在搜索深度达到该值时将强制进行回溯。如果目标节点的深度大于BOUND的话，回溯过程将搜索到所有深度小于等于BOUND的节点，而不会搜索任何深度大于BOUND的节点。如果我们设置BOUND的初始值为1，然后逐渐加大BOUND值，循环调用BACKTRACK1过程，直到BOUND值等于目标节点的深度时，搜索到目标结束。这样的搜索效果将等同于宽度优先搜索，可以找到问题的最优解，并且具有回溯策略占用空间小的性质，仅使用目标节点深度量级的存储空间。下面给出渐进式回溯策略搜索算法。过程ITERATIVE-DEEPENING-BACKTRACK(DATA0)；DATA0为初始状态 BOUND := 1； PATH := FAIL; While (PATH != FAIL) DATALIST := LIST(DATA0)；用初始状态组成一个表 PATH := BACKTRACK1(DATALIST，BOUND)；调用回溯过程，如果PATH等于FAIL表示没有搜索到目标，否则PATH得到一条从初始节点到目标节点的路径 BOUND := BOUND + 1; 加大一层搜索深度 End While； RETURN PATH；返回解路径从以上算法可以看出，如果最佳解的深度为d时，算法要调用d次回溯算法BACKTRACK1，会不会使得算法的求解时间大幅度增加呢？下面就分析一下宽度优先算法和渐进式回溯策略算法之间的时间关系。为了分析上的方便，我们假设在一个满b叉树上搜索，最佳解的深度为d。有理由认为算法的时间与所产生的节点数成正比，这样，我们只需分析两个算法所生成的节点数的关系即可。设宽度优先产生的节点数记为NBF，则：设渐进式回溯策略产生的节点数记为NIDBT，则在下面的公式推导中，省略了从第一行推导出第二行的过程。其基本思想是：b*NIDBT-NIDBT可以得到一个等比数列，然后通过求和公式求解出NIDBT的计算公式。：由于分叉数b 2，所以有：如果假设搜索所用的时间与产生的节点数成正比，则渐进式回溯策略所用时间不大于宽度优先搜索所用时间的b/(b-1)倍，分支数越大，二者所用时间越接近。下表给出了不同b值时所用时间比k，当b=2时k值最大为2。也就是说，渐进式回溯策略所用时间不会超过宽度优先搜索所用时间的2倍。b2345678910时间倍数k21.51.331.251.21.171.141.131.11渐进式回溯策略除了为了节省空间外，还可以应用到一些在规定的时间内，尽可能做出最优选择的场合。比如计算机下棋程序，一般来说搜索的深度越深，性能越好，但是一般下棋每一步会有时间限制，不能超时。这时就可以采用渐进式的思想，逐步加深搜索范围，在限时快结束时，用当前得到的最好结果作为决策。否则如果开始设置的搜索深度过深，可能限时结束时还得不到结果。反之如果设置的搜索深度过浅，则没有充分利用时间。1.4 启发式图搜索过程启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。这种利用启发信息的搜索过程称为启发式搜索方法。在研究启发式搜索方法时，先说明一下启发信息应用、启发能力度量及如何获得启发信息这几个问题，然后再来讨论算法及一些理论问题。一般来说启发信息过弱，搜索算法在找到一条路径之前将扩展过多的节点，即求得解路径所需搜索的耗散值（搜索花费的工作量）较大；相反引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径（最佳路径），因此实际应用中，希望最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。