1、第三章 确定性推理3.4 消解原理3.5 规则演绎系统3.6 产生式系统3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索中南大学 智能系统与智能软件研究所CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU 上一章中我们研究了知识表示方法，为人工智能问上一章中我们研究了知识表示方法，为人工智能问题的求解打下了基础。题的求解打下了基础。从问题表示到问题的解决从问题表示到问题的解决，是一个求解的过程，这是一个求解的过程，这其实就是搜索过程其实就是搜索过程，所以搜，所以搜索实际上就是求解
2、问题的一种方法。接下来要研究索实际上就是求解问题的一种方法。接下来要研究的是实现求解的过程，采用的基本方法包括搜索和的是实现求解的过程，采用的基本方法包括搜索和推理。本章先介绍推理。本章先介绍搜索技术搜索技术，将要讨论问题求解的，将要讨论问题求解的搜索原理，包括一些用于解决比较简单问题的搜索搜索原理，包括一些用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的原理和一些比较新的能够求解比较复杂问题的搜索搜索原理和推理技术原理和推理技术。2CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU
3、CSUCSUCSU可把图搜索策略看成一种在图中寻找路径的方可把图搜索策略看成一种在图中寻找路径的方法。第二章我们已经介绍过有关状态空间图的知识法。第二章我们已经介绍过有关状态空间图的知识表示方法，本节着重对表示方法，本节着重对基于状态空间图的搜索策略基于状态空间图的搜索策略进行介绍。状态空间图中的进行介绍。状态空间图中的节点对应于状态节点对应于状态，而，而连连线对应于操作符线对应于操作符，表示一次操作、走步或算符表示一次操作、走步或算符。基于图的搜索策略基于图的搜索策略就等价于求得图中从某一初就等价于求得图中从某一初始状态节点到另一目标状态节点的一条始状态节点到另一目标状态节点的一条路径问题路
4、径问题。在介绍图搜索策略之前，先来看一个例子。在介绍图搜索策略之前，先来看一个例子。3.1 图搜索策略3CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU例子：从某王姓家族的四代中找王例子：从某王姓家族的四代中找王A A的后代且其寿命为的后代且其寿命为X X的人。的人。王王A A：寿命：寿命4747，有儿子王，有儿子王B1B1、王、王B3B3、王、王B2B2王王B1B1：寿命：寿命7777，有儿子王，有儿子王C1C1、王、王C2C2王王B3B3：寿命：寿命5252，有儿子王，有儿子王
5、D1D1王王B2B2：寿命：寿命6565，有儿子王，有儿子王E1E1、王、王E2E2王王C1C1：寿命：寿命2727，没有儿子，没有儿子王王C2C2：寿命：寿命8787，有儿子王，有儿子王F1F1王王D1D1：寿命：寿命7777，没有儿子，没有儿子王王E1E1：寿命：寿命5757，有儿子王，有儿子王G1G1王王E2E2：寿命：寿命9292，有儿子王，有儿子王H1H1王王F1F1：寿命：寿命3232王王G1G1：寿命：寿命9696王王H1H1：寿命：寿命5151若要查找寿命若要查找寿命X=57X=57的后代，试给出其答案。的后代，试给出其答案。4CSUCSUCSUCSUCSUCSUCSUCSUC
6、SUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU如果是一个如果是一个N N代的家族表中找其寿命为代的家族表中找其寿命为X X的人，人工方法是的人，人工方法是从家族表的开始往下，若从家族表的开始往下，若N N的数目很大，可能就比较复杂。的数目很大，可能就比较复杂。若这若这个问题用图来表示和求解，就比较直观和容易了个问题用图来表示和求解，就比较直观和容易了。图中省去姓氏，。图中省去姓氏，每个成员的后代按所给名字的先后顺序。图示为：每个成员的后代按所给名字的先后顺序。图示为：5CSUCSUCSUCSUCSUCSUCSUCSUCSUCSU
7、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU利用利用搜索方法求解问题的基本思想搜索方法求解问题的基本思想：首先将问：首先将问题的题的初始状态初始状态（即状态空间图中的初始节点）作为（即状态空间图中的初始节点）作为当前状态，选择一当前状态，选择一适当的算符适当的算符作用于当前状态，生作用于当前状态，生成一组成一组后继状态后继状态（或称后继节点），检查这组后继（或称后继节点），检查这组后继状态节点中有没有目标状态。如果有，则说明搜索状态节点中有没有目标状态。如果有，则说明搜索成功，从成功，从初始状态到目标状态的一系列算符即是问初始状态到目标
8、状态的一系列算符即是问题的解题的解；若没有，则按照某种；若没有，则按照某种控制策略控制策略从已生成的从已生成的状态中再选择一个状态作为当前状态，重复上述过状态中再选择一个状态作为当前状态，重复上述过程，直到出现目标状态或不再有可供操作的状态及程，直到出现目标状态或不再有可供操作的状态及算符为止。该过程类似于隐式状态空间图的扩展。算符为止。该过程类似于隐式状态空间图的扩展。图搜索（图搜索（GRAPHSEARCHGRAPHSEARCH）的一般过程如下：）的一般过程如下：6CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC
9、SUCSUCSUCSUCSUCSU(1)(1)建立一个只含有起始节点建立一个只含有起始节点S S的搜索图的搜索图G G，把，把S S放到一个叫做放到一个叫做OPENOPEN的未扩展节点表的未扩展节点表中（简称中（简称OPENOPEN表）。表）。(2)(2)建立一个叫做建立一个叫做CLOSEDCLOSED的已扩展节点表的已扩展节点表（简称（简称CLOSEDCLOSED表），表），其初始为空表。其初始为空表。(3)LOOP(3)LOOP：若：若OPENOPEN表是空表，则失败退出。表是空表，则失败退出。(4)(4)选择选择OPENOPEN表上的第一个节点，把它从表上的第一个节点，把它从OPENOP
10、EN表移出并放进表移出并放进CLOSEDCLOSED表中。称为节点表中。称为节点n n，它是在，它是在CLOSEDCLOSED表中节点的编号表中节点的编号。(5)(5)若若n n为目标节点，则有解并成功退出，此解是追踪图为目标节点，则有解并成功退出，此解是追踪图G G中沿着中沿着指针从指针从n n到到S S这条路径而得到的（这条路径而得到的（指针将在第指针将在第7 7步中设置步中设置）。）。(6)(6)扩展节点扩展节点n n，同时生成，同时生成n n的后继节点的集合的后继节点的集合MM。把。把MM的这些成的这些成员作为员作为n n的后继节点添入图的后继节点添入图G G中。中。(7)(7)对那些
11、未曾在对那些未曾在G G中出现过的（既未曾在中出现过的（既未曾在OPENOPEN表上或表上或CLOSEDCLOSED表上出现过的）表上出现过的）MM成员设置一个指向父节点成员设置一个指向父节点n n的指针。把的指针。把MM的这的这些成员加进些成员加进OPENOPEN表。对已经在表。对已经在OPENOPEN或或CLOSEDCLOSED表上的每一个表上的每一个MM成员，确定是否需要更改通到成员，确定是否需要更改通到n n的指针方向，若需要更改，并的指针方向，若需要更改，并相应地在图相应地在图G G中更改指针方向，使得中更改指针方向，使得指向现在的父节点指向现在的父节点n n。(8)(8)按某一任意
12、方式或按某个探试值，按某一任意方式或按某个探试值，重排重排OPENOPEN表表。(9)GO LOOP(9)GO LOOP。7CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU开始开始把把S S放入放入OPENOPEN表表OPENOPEN表为空表？表为空表？把第一个节点把第一个节点(n)(n)从从OPENOPEN表移至表移至CLOSEDCLOSED表表n n为目标节点吗？为目标节点吗？把把n n的后继节点放入的后继节点放入OPENOPEN表的表的末端，提供返回节点末端，提供返回节点n
13、n的指针的指针修改父节点指针指向修改父节点指针指向n n重排重排OPENOPEN表表失败失败成功成功图搜索过程框图图搜索过程框图是是是是否否否否8CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU图搜索算法中的几个重要名词图搜索算法中的几个重要名词1 1扩展节点和未扩展节点扩展节点和未扩展节点扩展就是用合适的算符对某个节点进行操作生成一组后继节扩展就是用合适的算符对某个节点进行操作生成一组后继节点。对于状态空间图中的某个节点，如果求出了它的后继节点，点。对于状态空间图中的某个节点，如
14、果求出了它的后继节点，则此节点就是则此节点就是已扩展节点已扩展节点，而尚未被求出后继节点称为，而尚未被求出后继节点称为未扩展节未扩展节点点。将。将未扩展的节点存于未扩展的节点存于一个名为一个名为OPENOPEN的表中，而将的表中，而将已扩展的已扩展的节点存于节点存于一个名一个名CLOSEDCLOSED的表中。的表中。2 2OPENOPEN表表状态节点状态节点父节点父节点 3 3CLOSEDCLOSED表表编号编号状态节点状态节点父节点父节点 9CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUC
15、SUCSU4 4搜索图搜索图图搜索过程会生成一个明确的图图搜索过程会生成一个明确的图G G，它是问题状，它是问题状态空间图的一部分，称为态空间图的一部分，称为搜索图（也称为搜索树）搜索图（也称为搜索树）。G G中的每个节点（除中的每个节点（除S S外）都有一个只指向外）都有一个只指向G G中一个父中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。到达由算法发现的某个节点上，每条可一父辈节点。到达由算法发现的某个节点上，每条可能的路径被明确地保存在图中，对任何节点的单独一能的路径被明确地保存在图中，对任何节点的单独一条明显路径是用条明
16、显路径是用T T来定义的。来定义的。OPENOPEN表上的节点都是搜索树上未被扩展的端节点表上的节点都是搜索树上未被扩展的端节点；在在CLOSEDCLOSED表上的节点，或者是几个已扩展但是在搜表上的节点，或者是几个已扩展但是在搜索树中没有生成后继节点的端节点，或者是搜索树的索树中没有生成后继节点的端节点，或者是搜索树的非端节点非端节点。10CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU当被选作扩展的节点为目标节点时，这一过程当被选作扩展的节点为目标节点时，这一过程就宣告成功结束
17、。这时，重现从起始节点到目标节就宣告成功结束。这时，重现从起始节点到目标节点的这条成功路径的方法是：点的这条成功路径的方法是：从目标节点按指针向从目标节点按指针向初始点初始点S S返回追溯返回追溯。如果目标节点还没找到，且搜索。如果目标节点还没找到，且搜索图不再剩有未被扩展的端节点时，过程就以失败告图不再剩有未被扩展的端节点时，过程就以失败告终（某些节点最终可能没有后继节点，所以终（某些节点最终可能没有后继节点，所以OPENOPEN表表可能最后变成一张空表）。可能最后变成一张空表）。11CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU
18、CSUCSUCSUCSUCSUCSUCSUCSUCSU上述状态空间图的上述状态空间图的图搜索算法具有通用性图搜索算法具有通用性。本。本章后面各小节讨论的几种搜索策略都可以是它的一章后面各小节讨论的几种搜索策略都可以是它的一个特例。个特例。各种策略的主要区别就是在于第各种策略的主要区别就是在于第8 8步对步对OPENOPEN表上的节点进行排序的策略不同表上的节点进行排序的策略不同。在第。在第8 8步对步对OPENOPEN表中的节点排序，主要目的是希望从未扩展表中的节点排序，主要目的是希望从未扩展节点中选出一个节点中选出一个“最有希望最有希望”的节点作为第的节点作为第4 4步扩步扩展用。若这种排序
19、是任意指定或盲目的，则搜索过展用。若这种排序是任意指定或盲目的，则搜索过程称为程称为盲目搜索（无信息搜索）盲目搜索（无信息搜索）；若这种对未扩展；若这种对未扩展节点的排序是按照某种启发信息或准则为依据就是节点的排序是按照某种启发信息或准则为依据就是启发式搜索（有信息搜索）启发式搜索（有信息搜索）。12CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU盲目搜索盲目搜索过程中，没有任何启发信息来改变未扩过程中，没有任何启发信息来改变未扩展节点的排列顺序，从而不太可能按展节点的排列顺序，从
20、而不太可能按“最有希望最有希望”的的路径或方向进行搜索，使得搜索带有盲目性，效率低，路径或方向进行搜索，使得搜索带有盲目性，效率低，适用于相对简单的问题适用于相对简单的问题。启发式启发式搜索能根据问题本身搜索能根据问题本身的特性或某些信息不断改变调整搜索的方向，使搜索的特性或某些信息不断改变调整搜索的方向，使搜索朝朝“最有希望最有希望”的方向前进，加速问题的求解，并可的方向前进，加速问题的求解，并可能找到最优解。能找到最优解。启发式搜索启发式搜索求解效率更高，求解效率更高，更易于求更易于求解复杂的问题解复杂的问题。但并不是所有的问题都能方便地抽取到其相关的但并不是所有的问题都能方便地抽取到其相
21、关的特性或信息特性或信息，因此尽管启发式搜索明显优于盲目搜索，因此尽管启发式搜索明显优于盲目搜索，但盲目搜索仍会在很多的问题求解中得到应用。但盲目搜索仍会在很多的问题求解中得到应用。13CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU无需重排无需重排OPENOPEN表的搜索方法叫做盲目搜索或无表的搜索方法叫做盲目搜索或无信息搜索信息搜索，它包括，它包括宽度优先宽度优先搜索和搜索和深度优先深度优先搜索和搜索和等代价等代价搜索。盲目搜索方法效率不高，一般适用于搜索。盲目搜索方法效率不高
22、，一般适用于求解相对简单的问题。求解相对简单的问题。3.2.1 宽度优先搜索回顾上一节的寻找寿命为回顾上一节的寻找寿命为X X的人的例子，若搜索的人的例子，若搜索时，从节点时，从节点A A开始，对他三个儿子按从左至右搜索，开始，对他三个儿子按从左至右搜索，然后对他的所有孙子按从左至右搜索，依此下去，然后对他的所有孙子按从左至右搜索，依此下去，这种搜索就是这种搜索就是宽度优先搜索宽度优先搜索。3.2 盲目搜索14CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU1 1、宽度优先搜索的定
23、义、宽度优先搜索的定义如果如果搜索是以接近起始节点的程度依次扩展节搜索是以接近起始节点的程度依次扩展节点的点的，那么，那么这种搜索就叫做宽度优先搜索这种搜索就叫做宽度优先搜索。如下图。如下图所示，这种搜索是逐层进行的；在对下一层的任一所示，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。节点进行搜索之前，必须搜索完本层的所有节点。在搜索过程中，未扩展节点在搜索过程中，未扩展节点OPENOPEN表中节点的排序表中节点的排序准则准则是：先进入表的节点排在最前面，后进入表的是：先进入表的节点排在最前面，后进入表的节点排在最后面（节点排在最后面（即将扩展得到的后继节点
24、放入即将扩展得到的后继节点放入OPENOPEN表的末端表的末端）。）。15CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU宽度优先搜索示意图宽度优先搜索示意图16CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2 2、宽度优先搜索算法如下：、宽度优先搜索算法如下：(1)(1)把起始节点放到把起始节点放到OPENOPEN表中（如果该起始节表中（如果该起始节点为一目标节点，
25、则求得一个解答）。点为一目标节点，则求得一个解答）。(2)(2)如果如果OPENOPEN表是个空表，则没有解，失败退表是个空表，则没有解，失败退出；否则继续。出；否则继续。(3)(3)把第一个节点（节点把第一个节点（节点n n）从）从OPENOPEN表移出，并表移出，并把它放入把它放入CLOSEDCLOSED扩展节点表中。扩展节点表中。(4)(4)扩展节点扩展节点n n，如果没有后继节点，则转向上述，如果没有后继节点，则转向上述第第(2)(2)步。步。(5)(5)把把n n的所有后继节点放到的所有后继节点放到OPENOPEN表的末端表的末端，并，并提供从这些后继节点回到提供从这些后继节点回到n
26、 n的指针。的指针。(6)(6)如果如果n n的任一个后继节点是目标节点，则找到的任一个后继节点是目标节点，则找到一个解答，成功退出；否则转向第一个解答，成功退出；否则转向第(2)(2)步。步。宽度优先搜索过程如下图所示：宽度优先搜索过程如下图所示：17CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU开始开始把把S S放入放入OPENOPEN表表OPENOPEN表为空表？表为空表？把第一个节点把第一个节点(n)(n)从从OPENOPEN表移至表移至CLOSEDCLOSED表表是否有
27、后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n n，把，把n n的后继节点放入的后继节点放入OPENOPEN表的表的末端末端，提供返回节点，提供返回节点n n的指针的指针失败失败成功成功宽度优先算法框图宽度优先算法框图是是否否是是否否18CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUv例子：应用宽度优先搜索算法来求解八数码难题例子：应用宽度优先搜索算法来求解八数码难题（8-puzzle problem8-puzzle problem）12384567（目标状态）（目标状
28、态）12384567（初始状态（初始状态）规定规定：将牌移入空格的顺序为：从空格左边开始，：将牌移入空格的顺序为：从空格左边开始，再上，然后右，最后下的顺时针方向。不许斜向移动，再上，然后右，最后下的顺时针方向。不许斜向移动，也不返回先辈节点。也不返回先辈节点。19CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU1238456712384123845674123856712 384123845671238456767891011121312384567567567123845671
29、123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 384567123845671238456712384567141516171819202112384567g g20CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU从图可见从图可见，搜索树上的所有节点都
30、标记它们所，搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩对应的状态描述，每个节点旁边的数字表示节点扩展的顺序，要扩展展的顺序，要扩展1616个节点，共生成个节点，共生成2727个节点之后个节点之后才求得解（目标节点）。才求得解（目标节点）。3 3、宽度优先搜索方法分析、宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情况，宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第将图搜索一般过程中的第8 8步具体化为本算法中的第步具体化为本算法中的第5 5步，这就是步，这就是将将OPENOPEN表作为表作为“先进先出先进先出”的队列的队列进进行操作。行
31、操作。21CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU宽度优先搜索的宽度优先搜索的缺点缺点：搜索方向：搜索方向盲目性较大盲目性较大，当目标节点距离初始节点较远时，将会产生大量的当目标节点距离初始节点较远时，将会产生大量的无用节点，无用节点，搜索效率低搜索效率低。但是，但是，只要问题有解只要问题有解，用宽度优先搜索总可以用宽度优先搜索总可以找到它的解找到它的解，而且是而且是搜索树中从初始节点到目标节搜索树中从初始节点到目标节点点路径最短的解路径最短的解（不考虑每条弧线的长度、代价
32、、（不考虑每条弧线的长度、代价、扩展节点数等，只考虑扩展节点数等，只考虑经历的步数经历的步数）。因此，）。因此，宽度宽度优先搜索策略是完备的优先搜索策略是完备的。搜索树能提供所有存在的。搜索树能提供所有存在的路径（如果没有路径存在，对有限图来说，就以失路径（如果没有路径存在，对有限图来说，就以失败退出；对于无限图来说，则永远不会终止）。败退出；对于无限图来说，则永远不会终止）。22CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU3.2.2 深度优先搜索另一种盲目（无信息）搜索叫做另
33、一种盲目（无信息）搜索叫做深度优先搜索深度优先搜索(depth-first(depth-first search)search)。下面是一个深度优先搜索示意图。下面是一个深度优先搜索示意图。分析该图可看出，在深分析该图可看出，在深度优先搜索中，我们度优先搜索中，我们首先扩首先扩展最新产生的（即最深的）展最新产生的（即最深的）节点节点，深度相等的节点可以，深度相等的节点可以任意排列。任意排列。23CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU下面，我们给出下面，我们给出节点的深度节
34、点的深度定义：定义：(1)(1)起始节点起始节点(即根节点即根节点)的深度为的深度为0 0。(2)(2)任何其它节点的深度等于其父辈节点深度加上任何其它节点的深度等于其父辈节点深度加上1 1。首先，扩展最深的节点使得搜索从起始节点沿某条单一路首先，扩展最深的节点使得搜索从起始节点沿某条单一路径进行下去；只有径进行下去；只有当搜索到达一个没有后裔的状态时，才考虑当搜索到达一个没有后裔的状态时，才考虑最近的另一条替代的路径最近的另一条替代的路径。替代路径与前面已经试过的路径不。替代路径与前面已经试过的路径不同之处仅仅在于：同之处仅仅在于：改变最后改变最后n n步，而且保持步，而且保持n n尽可能小
35、尽可能小。对于许多问题，其状态空间搜索树的深度可能为无限深，对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了防止搜索过程沿着无益的路径扩展下去，往往深。为了防止搜索过程沿着无益的路径扩展下去，往往给出一给出一个节点扩展的最大深度个节点扩展的最大深度深度界限深度界限。任何节点如果达到了深。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的是，即使应用了深度界限的规定
36、，所求得的解答路径并不一定解答路径并不一定就是最短的路径就是最短的路径。24CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU含有深度界限的深度优先搜索算法含有深度界限的深度优先搜索算法如下：如下：(1)(1)把起始节点把起始节点S S放到未扩展节点放到未扩展节点OPENOPEN表中。如果表中。如果此节点为一目标节点，则得到一个解。此节点为一目标节点，则得到一个解。(2)(2)如果如果OPENOPEN为一空表，则失败退出；否则继续。为一空表，则失败退出；否则继续。(3)(3)把把OP
37、ENOPEN表第一个节点表第一个节点(节点节点n)n)移到移到CLOSEDCLOSED表。表。(4)(4)如果节点如果节点n n的深度等于最大深度，则转向的深度等于最大深度，则转向(2)(2)。(5)(5)扩展节点扩展节点n n，产生其全部后裔，并把它们放入，产生其全部后裔，并把它们放入OPENOPEN表的前头表的前头，并提供从这些后继节点回到节点，并提供从这些后继节点回到节点n n的的指针。如果节点指针。如果节点n n没有后裔，则转向没有后裔，则转向(2)(2)。(6)(6)如果后继节点中有任一个为目标节点，则求得如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向一个解，成
38、功退出；否则，转向(2)(2)。25CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU前端前端26CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU例例：按深度优先搜索生成的八数码难：按深度优先搜索生成的八数码难题搜索树，我们设置题搜索树，我们设置深度界限为深度界限为5 5，空格移，空格移动为先左，后上，再右，最后下的动为先左，后上，再右，最后下的顺时针方顺时针方向向。从图
39、可见，深度优先搜索过程是沿着一。从图可见，深度优先搜索过程是沿着一条路径进行下去，条路径进行下去，直到深度界限为止直到深度界限为止，然后，然后再考虑只有最后一步有差别的相同深度或较再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径浅深度可供选择的路径，接着再考虑最后两，接着再考虑最后两步有差别的那些路径，等等。步有差别的那些路径，等等。27CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU28CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU
40、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU12385671 12 23 38 84 4123845674 412384567123845673 37 71212g g123845675 56 67 712 384567123845671 1123845671238456712384567123845672 21111八数码难题的深度优先搜索树深度界限为41 13 34 45 56 61 12 23 38 84 45 56 67 71238456712384567123845671 23845671 12 23 36 67 78 812384567123845
41、671 238456712 384567123845671238456781234567123845674 48 81313123845675 56 69 910101414151529CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU有界深度优先搜索算法中，有界深度优先搜索算法中，深度界限的选择很重深度界限的选择很重要要。选择。选择过大过大，可能，可能会影响会影响搜索的搜索的效率效率；选择；选择过小过小，对于某些问题，可能它的解就位于某一分支较深的位对于某些问题，可能它的解就位于某
42、一分支较深的位置，这样置，这样可能导致找不到问题的解可能导致找不到问题的解。所以，。所以，有界深度有界深度优先搜索策略是不完备的优先搜索策略是不完备的。深度优先搜索与宽度优先搜索的区别在于深度优先搜索与宽度优先搜索的区别在于：在对：在对节点节点n n进行扩展时，进行扩展时，宽度优先宽度优先搜索是将后继节点搜索是将后继节点放入放入OPENOPEN表的末端先进先出队列表的末端先进先出队列，而，而深度优先深度优先搜索则搜索则是将后继节点是将后继节点放入放入OPENOPEN表的前端后进先出栈表的前端后进先出栈。宽。宽度优先一般效率低，是一种完备的搜索策略，且能找度优先一般效率低，是一种完备的搜索策略，
43、且能找到路径最短的解；深度优先一般效率高，不是一种完到路径最短的解；深度优先一般效率高，不是一种完备的搜索策略，不一定找到最短路径的解。备的搜索策略，不一定找到最短路径的解。30CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU3.2.3 等代价搜索有些问题要求在搜索树中求得具有最小代价的解答路径。有些问题要求在搜索树中求得具有最小代价的解答路径。宽宽度优先搜索可以被推广用来解决这种寻找从起始状态节点至目标度优先搜索可以被推广用来解决这种寻找从起始状态节点至目标状态节点的具有最小代价
44、的路径问题状态节点的具有最小代价的路径问题，这种推广的宽度优先搜索，这种推广的宽度优先搜索叫做等代价搜索算法，有如下一些记号：叫做等代价搜索算法，有如下一些记号：起始节点记为起始节点记为 S S；从节点；从节点 i i 到它的后继节点到它的后继节点 j j 的连接弧线代的连接弧线代价记为价记为 c c(i i,j j)；从起始节点；从起始节点 S S 到任一节点到任一节点 j j 的的路径代价路径代价标记为标记为g g(j j)=)=g g(i i)+)+c c(i i,j j)。搜索树上，我们假设。搜索树上，我们假设 g g(i i)是从起始节点是从起始节点 S S到节到节点点 i i 的最
45、少代价路径上的代价。的最少代价路径上的代价。等代价优先搜索的基本思想等代价优先搜索的基本思想：每次从：每次从OPENOPEN表中选择一代价表中选择一代价最小的节点，移入最小的节点，移入CLOSEDCLOSED表。每当表。每当对某一节点扩展之后，就要对某一节点扩展之后，就要计算它所有后继节点的代价计算它所有后继节点的代价，并将它们，并将它们与与OPENOPEN表中已有的待扩表中已有的待扩展节点按代价从小到大依次排序（代价小的排在展节点按代价从小到大依次排序（代价小的排在OPENOPEN表最前）表最前）。31CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU
46、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU等代价搜索方法以代价等代价搜索方法以代价 g g(i i)的大小扩展其节点，其算法如下：的大小扩展其节点，其算法如下：(1)(1)把起始节点把起始节点 S S 放到未扩展节点表放到未扩展节点表OPENOPEN中。如果此起始节点中。如果此起始节点为一目标节点，则求得一个解；否则令为一目标节点，则求得一个解；否则令 g g(S S)=0)=0 ；(2)(2)如果如果OPENOPEN是个空表，则没有解而失败退出；是个空表，则没有解而失败退出；(3)(3)从从OPENOPEN表中选择一个节点表中选择一个节点 i i ，使其，使其
47、g g(i i)为最小。如果有几为最小。如果有几个节点都合格，那么就要选择是目标的节点作为节点个节点都合格，那么就要选择是目标的节点作为节点 i i （要是有目（要是有目标节点的话）；否则，就从中选一个作为节点标节点的话）；否则，就从中选一个作为节点 i i 。把节点。把节点 i i 从从OPENOPEN表移至扩展节点表表移至扩展节点表CLOSEDCLOSED中；中；(4)(4)如果节点如果节点 i i 为目标节点，则求得一个解；为目标节点，则求得一个解；(5)(5)扩展节点扩展节点 i i ，如果没有后继节点，则转向第，如果没有后继节点，则转向第(2)(2)步；步；(6)(6)对于节点对于节
48、点 i i 的每个后继节点的每个后继节点 j j ，计算，计算 g g(j j)=)=g g(i i)+)+c c(i i,j j)，并把，并把所有后继节点所有后继节点 j j 放进放进OPENOPEN表。提供回到节点表。提供回到节点 i i 的指针；的指针；(7)(7)转向第转向第(2)(2)步。步。当所有弧线上的代价相等时，就变成了宽度优先搜索了当所有弧线上的代价相等时，就变成了宽度优先搜索了。32CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU开始把S放入OPEN表OPENO
49、PEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表i是否为目标节点？失败成功等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g g(s s)=0)=0S S是否目标节点是否目标节点？是是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否否33CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU盲目搜索有效率低，耗费过多的计算空间与时间盲目搜索有效率低，耗费过多的计算空间与时间等不足。分析前面介绍的宽度优先、深度优先搜索，等不足。分析前面
50、介绍的宽度优先、深度优先搜索，或等代价搜索算法或等代价搜索算法,其主要的差别是其主要的差别是OPENOPEN表中待扩展表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。那么，搜索效率将会大为提高。启发信息启发信息：进行搜索技术一般需要某些有关具体：进行搜索技术一般需要某些有关具体问题领域的特性的信息问题领域的特性的信息，把此种信息叫做启发信息。，把此种信息叫做启发信息。把利用启发信息的搜索方法叫做把利用启发信息的搜索方法
