第三章确定性推理

第三章第三章 确定性推理确定性推理CSUCSUCSUCSUCSUCSUCSUCSUCSU 上一章中我们研究了知识表示方法，为人工智上一章中我们研究了知识表示方法，为人工智能问题的求解打下了基础。能问题的求解打下了基础。从问题表示到问题的解从问题表示到问题的解决决，是一个求解的过程，这，是一个求解的过程，这其实就是搜索过程其实就是搜索过程，所，所以搜索实际上就是求解问题的一种方法。接下来要以搜索实际上就是求解问题的一种方法。接下来要研究的是实现求解的过程，采用的基本方法包括搜研究的是实现求解的过程，采用的基本方法包括搜索和推理。本章先介绍索和推理。本章先介绍搜索技术搜索技术，将要讨论问题求，将要讨论问题求解的搜索原理，包括一些用于解决比较简单问题的解的搜索原理，包括一些用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理和推理技术搜索原理和推理技术。CSUCSUCSUCSUCSUCSUCSUCSUCSU可可把把图图搜搜索索策策略略看看成成一一种种在在图图中中寻寻找找路路径径的的方方法法。第第二二章章我我们们已已经经介介绍绍过过有有关关状状态态空空间间图图的的知知识识表表示示方方法法，本本节节着着重重对对基基于于状状态态空空间间图图的的搜搜索索策策略略进进行行介介绍绍。状状态态空空间间图图中中的的节节点点对对应应于于状状态态，而而连连线线对对应应于操作符于操作符，表示一次操作、走步或算符表示一次操作、走步或算符。基基于于图图的的搜搜索索策策略略就就等等价价于于求求得得图图中中从从某某一一初初始状态节点到另一目标状态节点的一条始状态节点到另一目标状态节点的一条路径问题路径问题。在介绍图搜索策略之前，先来看一个例子。在介绍图搜索策略之前，先来看一个例子。3.1图搜索策略CSUCSUCSUCSUCSUCSUCSUCSUCSU例子：从某王姓家族的四代中找王例子：从某王姓家族的四代中找王A A的后代且其寿命为的后代且其寿命为X X的人。的人。王王A A：寿命：寿命4747，有儿子王，有儿子王B1B1、王、王B3B3、王、王B2B2王王B1B1：寿命：寿命7777，有儿子王，有儿子王C1C1、王、王C2C2王王B3B3：寿命：寿命5252，有儿子王，有儿子王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的后代，试给出其答案。的后代，试给出其答案。CSUCSUCSUCSUCSUCSUCSUCSUCSU如果是一个如果是一个N N代的家族表中找其寿命为代的家族表中找其寿命为X的人，人工方法是从的人，人工方法是从家族表的开始往下，若家族表的开始往下，若N N的数目很大，可能就比较复杂。的数目很大，可能就比较复杂。若这个若这个问题用图来表示和求解，就比较直观和容易了问题用图来表示和求解，就比较直观和容易了。图中省去姓氏，。图中省去姓氏，每个成员的后代按所给名字的先后顺序。图示为：每个成员的后代按所给名字的先后顺序。图示为：CSUCSUCSUCSUCSUCSUCSUCSUCSU利用利用搜索方法求解问题的基本思想搜索方法求解问题的基本思想：首先将问：首先将问题的题的初始状态初始状态（即状态空间图中的初始节点）作为（即状态空间图中的初始节点）作为当前状态，选择一当前状态，选择一适当的算符适当的算符作用于当前状态，生作用于当前状态，生成一组成一组后继状态后继状态（或称后继节点），检查这组后继（或称后继节点），检查这组后继状态节点中有没有目标状态。如果有，则说明搜索状态节点中有没有目标状态。如果有，则说明搜索成功，从成功，从初始状态到目标状态的一系列算符即是问初始状态到目标状态的一系列算符即是问题的解题的解；若没有，则按照某种；若没有，则按照某种控制策略控制策略从已生成的从已生成的状态中再选择一个状态作为当前状态，重复上述过状态中再选择一个状态作为当前状态，重复上述过程，直到出现目标状态或不再有可供操作的状态及程，直到出现目标状态或不再有可供操作的状态及算符为止。该过程类似于隐式状态空间图的扩展。算符为止。该过程类似于隐式状态空间图的扩展。图搜索（图搜索（GRAPHSEARCH）的一般过程如下：）的一般过程如下：CSUCSUCSUCSUCSUCSUCSUCSUCSU(1)(1)建建立立一一个个只只含含有有起起始始节节点点S S的的搜搜索索图图G G，把把S S放放到到一一个个叫叫做做OPENOPEN的未扩展节点表的未扩展节点表中（简称中（简称OPENOPEN表）。表）。(2)(2)建建立立一一个个叫叫做做CLOSEDCLOSED的的已已扩扩展展节节点点表表（简简称称CLOSEDCLOSED表表），其初始为空表。其初始为空表。(3)LOOP(3)LOOP：若：若OPENOPEN表是空表，则失败退出。表是空表，则失败退出。(4)(4)选选择择OPENOPEN表表上上的的第第一一个个节节点点，把把它它从从OPENOPEN表表移移出出并并放放进进CLOSEDCLOSED表中。称为节点表中。称为节点n n，它是在，它是在CLOSEDCLOSED表中节点的编号表中节点的编号。(5)(5)若若n n为为目目标标节节点点，则则有有解解并并成成功功退退出出，此此解解是是追追踪踪图图G G中中沿沿着指针从着指针从n n到到S S这条路径而得到的（这条路径而得到的（指针将在第指针将在第7 7步中设置步中设置）。）。(6)(6)扩扩展展节节点点n n，同同时时生生成成n n的的后后继继节节点点的的集集合合M M。把把M M的的这这些些成成员作为员作为n n的后继节点添入图的后继节点添入图G G中。中。(7)(7)对对那那些些未未曾曾在在G G中中出出现现过过的的（既既未未曾曾在在OPENOPEN表表上上或或CLOSEDCLOSED表表上上出出现现过过的的）M M成成员员设设置置一一个个指指向向父父节节点点n n的的指指针针。把把M M的的这这些些成成员员加加进进OPENOPEN表表。对对已已经经在在OPENOPEN或或CLOSEDCLOSED表表上上的的每每一一个个M M成成员员，确确定定是是否否需需要要更更改改通通到到n n的的指指针针方方向向，若若需需要要更更改改，并并相相应应地地在在图图G G中更改指针方向，使得中更改指针方向，使得指向现在的父节点指向现在的父节点n n。(8)(8)按某一任意方式或按某个探试值，按某一任意方式或按某个探试值，重排重排OPENOPEN表表。(9)GO LOOP(9)GO LOOP。CSUCSUCSUCSUCSUCSUCSUCSUCSU开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改父节点指针指向修改父节点指针指向n重排重排OPEN表表失败失败成功成功图搜索过程框图图搜索过程框图是是是是否否否否CSUCSUCSUCSUCSUCSUCSUCSUCSU图搜索算法中的几个重要名词图搜索算法中的几个重要名词1扩展节点和未扩展节点扩展节点和未扩展节点扩扩展展就就是是用用合合适适的的算算符符对对某某个个节节点点进进行行操操作作生生成成一一组组后后继继节节点点。对对于于状状态态空空间间图图中中的的某某个个节节点点，如如果果求求出出了了它它的的后后继继节节点点，则则此此节节点点就就是是已已扩扩展展节节点点，而而尚尚未未被被求求出出后后继继节节点点称称为为未未扩扩展展节节点点。将将未未扩扩展展的的节节点点存存于于一一个个名名为为OPEN的的表表中中，而而将将已已扩扩展展的的节点存于节点存于一个名一个名CLOSED的表中。的表中。2OPEN表表状态节点状态节点父节点父节点3CLOSED表表编号编号状态节点状态节点父节点父节点CSUCSUCSUCSUCSUCSUCSUCSUCSU4搜索图搜索图图图搜搜索索过过程程会会生生成成一一个个明明确确的的图图G G，它它是是问问题题状状态态空空间间图图的的一一部部分分，称称为为搜搜索索图图（也也称称为为搜搜索索树树）。G G中中的的每每个个节节点点（除除S S外外）都都有有一一个个只只指指向向G G中中一一个个父父辈辈节节点点的的指指针针，该该父父辈辈节节点点就就定定为为树树中中那那个个节节点点的的唯唯一一父父辈辈节节点点。到到达达由由算算法法发发现现的的某某个个节节点点上上，每每条条可可能能的的路路径径被被明明确确地地保保存存在在图图中中，对对任任何何节节点点的的单单独独一一条明显路径是用条明显路径是用T T来定义的。来定义的。OPENOPEN表表上上的的节节点点都都是是搜搜索索树树上上未未被被扩扩展展的的端端节节点点；在在CLOSEDCLOSED表表上上的的节节点点，或或者者是是几几个个已已扩扩展展但但是是在在搜搜索索树树中中没没有有生生成成后后继继节节点点的的端端节节点点，或或者者是是搜搜索索树树的的非非端节点端节点。CSUCSUCSUCSUCSUCSUCSUCSUCSU当当被被选选作作扩扩展展的的节节点点为为目目标标节节点点时时，这这一一过过程程就就宣宣告告成成功功结结束束。这这时时，重重现现从从起起始始节节点点到到目目标标节节点点的的这这条条成成功功路路径径的的方方法法是是：从从目目标标节节点点按按指指针针向向初初始始点点S返返回回追追溯溯。如如果果目目标标节节点点还还没没找找到到，且且搜搜索索图图不不再再剩剩有有未未被被扩扩展展的的端端节节点点时时，过过程程就就以以失失败败告告终终（某某些些节节点点最最终终可可能能没没有有后后继继节节点点，所所以以OPEN表表可可能能最最后后变成一张空表）。变成一张空表）。CSUCSUCSUCSUCSUCSUCSUCSUCSU上上述述状状态态空空间间图图的的图图搜搜索索算算法法具具有有通通用用性性。本本章章后后面面各各小小节节讨讨论论的的几几种种搜搜索索策策略略都都可可以以是是它它的的一一个个特特例例。各各种种策策略略的的主主要要区区别别就就是是在在于于第第8步步对对OPEN表表上上的的节节点点进进行行排排序序的的策策略略不不同同。在在第第8步步对对OPEN表表中中的的节节点点排排序序，主主要要目目的的是是希希望望从从未未扩扩展展节节点点中中选选出出一一个个“最最有有希希望望”的的节节点点作作为为第第4步步扩扩展展用用。若若这这种种排排序序是是任任意意指指定定或或盲盲目目的的，则则搜搜索索过过程程称称为为盲盲目目搜搜索索（无无信信息息搜搜索索）；若若这这种种对对未未扩扩展展节节点点的的排排序序是是按按照照某某种种启启发发信信息息或或准准则则为为依依据据就就是是启启发式搜索（有信息搜索）发式搜索（有信息搜索）。CSUCSUCSUCSUCSUCSUCSUCSUCSU盲盲目目搜搜索索过过程程中中，没没有有任任何何启启发发信信息息来来改改变变未未扩扩展展节节点点的的排排列列顺顺序序，从从而而不不太太可可能能按按“最最有有希希望望”的的路路径径或或方方向向进进行行搜搜索索，使使得得搜搜索索带带有有盲盲目目性性，效效率率低低，适适用用于于相相对对简简单单的的问问题题。启启发发式式搜搜索索能能根根据据问问题题本本身身的的特特性性或或某某些些信信息息不不断断改改变变调调整整搜搜索索的的方方向向，使使搜搜索索朝朝“最最有有希希望望”的的方方向向前前进进，加加速速问问题题的的求求解解，并并可可能能找找到到最最优优解解。启启发发式式搜搜索索求求解解效效率率更更高高，更更易易于于求求解复杂的问题解复杂的问题。但但并并不不是是所所有有的的问问题题都都能能方方便便地地抽抽取取到到其其相相关关的的特特性性或或信信息息，因因此此尽尽管管启启发发式式搜搜索索明明显显优优于于盲盲目目搜搜索索，但盲目搜索仍会在很多的问题求解中得到应用。但盲目搜索仍会在很多的问题求解中得到应用。CSUCSUCSUCSUCSUCSUCSUCSUCSU无无需需重重排排OPEN表表的的搜搜索索方方法法叫叫做做盲盲目目搜搜索索或或无无信信息息搜搜索索，它它包包括括宽宽度度优优先先搜搜索索和和深深度度优优先先搜搜索索和和等等代代价价搜搜索索。盲盲目目搜搜索索方方法法效效率率不不高高，一一般般适适用用于于求求解解相对简单的问题。相对简单的问题。3.2.1宽度优先搜索回回顾顾上上一一节节的的寻寻找找寿寿命命为为X的的人人的的例例子子，若若搜搜索索时时，从从节节点点A开开始始，对对他他三三个个儿儿子子按按从从左左至至右右搜搜索索，然然后后对对他他的的所所有有孙孙子子按按从从左左至至右右搜搜索索，依依此此下下去去，这这种搜索就是种搜索就是宽度优先搜索宽度优先搜索。3.2盲目搜索CSUCSUCSUCSUCSUCSUCSUCSUCSU1、宽度优先搜索的定义、宽度优先搜索的定义如如果果搜搜索索是是以以接接近近起起始始节节点点的的程程度度依依次次扩扩展展节节点点的的，那那么么这这种种搜搜索索就就叫叫做做宽宽度度优优先先搜搜索索。如如下下图图所所示示，这这种种搜搜索索是是逐逐层层进进行行的的；在在对对下下一一层层的的任任一一节节点点进进行行搜搜索索之之前前，必必须须搜搜索索完完本本层层的的所所有有节节点点。在在搜搜索索过过程程中中，未未扩扩展展节节点点OPEN表表中中节节点点的的排排序序准准则则是是：先先进进入入表表的的节节点点排排在在最最前前面面，后后进进入入表表的的节节点点排排在在最最后后面面（即即将将扩扩展展得得到到的的后后继继节节点点放放入入OPEN表的末端表的末端）。）。CSUCSUCSUCSUCSUCSUCSUCSUCSU宽度优先搜索示意图宽度优先搜索示意图CSUCSUCSUCSUCSUCSUCSUCSUCSU2、宽度优先搜索算法如下：、宽度优先搜索算法如下：(1)把把起起始始节节点点放放到到OPEN表表中中（如如果果该该起起始始节节点为一目标节点，则求得一个解答）。点为一目标节点，则求得一个解答）。(2)如如果果OPEN表表是是个个空空表表，则则没没有有解解，失失败败退退出；否则继续。出；否则继续。(3)把把第第一一个个节节点点（节节点点n）从从OPEN表表移移出出，并并把它放入把它放入CLOSED扩展节点表中。扩展节点表中。(4)扩扩展展节节点点n，如如果果没没有有后后继继节节点点，则则转转向向上上述述第第(2)步。步。(5)把把n的的所所有有后后继继节节点点放放到到OPEN表表的的末末端端，并并提供从这些后继节点回到提供从这些后继节点回到n的指针。的指针。(6)如如果果n的的任任一一个个后后继继节节点点是是目目标标节节点点，则则找找到到一个解答，成功退出；否则转向第一个解答，成功退出；否则转向第(2)步。步。宽度优先搜索过程如下图所示：宽度优先搜索过程如下图所示：CSUCSUCSUCSUCSUCSUCSUCSUCSU开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的末端末端，提供返回节点，提供返回节点n的指针的指针失败失败成功成功宽度优先算法框图宽度优先算法框图是是否否是是否否CSUCSUCSUCSUCSUCSUCSUCSUCSUv例子：应用宽度优先搜索算法来求解八数码难题例子：应用宽度优先搜索算法来求解八数码难题（8-puzzle problem）12384567（目标状态）（目标状态）12384567（初始状态（初始状态）规定规定：将牌移入空格的顺序为：从空格左边开始，：将牌移入空格的顺序为：从空格左边开始，再上，然后右，最后下的顺时针方向。不许斜向移动，再上，然后右，最后下的顺时针方向。不许斜向移动，也不返回先辈节点。也不返回先辈节点。CSUCSUCSUCSUCSUCSUCSUCSUCSU1238456712384123845674123856712 384123845671238456767891011121312384567567567123845671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 384567123845671238456712384567141516171819202112384567gCSUCSUCSUCSUCSUCSUCSUCSUCSU从图可见从图可见，搜索树上的所有节点都标记它们所，搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩对应的状态描述，每个节点旁边的数字表示节点扩展的顺序，要扩展展的顺序，要扩展16个节点，共生成个节点，共生成27个节点之后个节点之后才求得解（目标节点）。才求得解（目标节点）。3、宽度优先搜索方法分析、宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情况，宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第将图搜索一般过程中的第8步具体化为本算法中的第步具体化为本算法中的第5步，这就是步，这就是将将OPEN表作为表作为“先进先出先进先出”的队列的队列进行进行操作。操作。CSUCSUCSUCSUCSUCSUCSUCSUCSU宽度优先搜索的宽度优先搜索的缺点缺点：搜索方向：搜索方向盲目性较大盲目性较大，当目标节点距离初始节点较远时，将会产生大量的当目标节点距离初始节点较远时，将会产生大量的无用节点，无用节点，搜索效率低搜索效率低。但是，但是，只要问题有解只要问题有解，用宽度优先搜索总可以用宽度优先搜索总可以找到它的解找到它的解，而且是而且是搜索树中从初始节点到目标节搜索树中从初始节点到目标节点点路径最短的解路径最短的解（不考虑每条弧线的长度、代价、（不考虑每条弧线的长度、代价、扩展节点数等，只考虑扩展节点数等，只考虑经历的步数经历的步数）。因此，）。因此，宽度宽度优先搜索策略是完备的优先搜索策略是完备的。搜索树能提供所有存在的。搜索树能提供所有存在的路径（如果没有路径存在，对有限图来说，就以失路径（如果没有路径存在，对有限图来说，就以失败退出；对于无限图来说，则永远不会终止）。败退出；对于无限图来说，则永远不会终止）。CSUCSUCSUCSUCSUCSUCSUCSUCSU3.2.2 深度优先搜索另另一一种种盲盲目目（无无信信息息）搜搜索索叫叫做做深深度度优优先先搜搜索索(depth-first search)。下面是一个深度优先搜索示意图。下面是一个深度优先搜索示意图。分分析析该该图图可可看看出出，在在深深度度优优先先搜搜索索中中，我我们们首首先先扩扩展展最最新新产产生生的的（即即最最深深的的）节节点点，深深度度相相等等的的节节点点可可以以任意排列。任意排列。CSUCSUCSUCSUCSUCSUCSUCSUCSU下面，我们给出下面，我们给出节点的深度节点的深度定义：定义：(1)起始节点起始节点(即根节点即根节点)的深度为的深度为0。(2)任何其它节点的深度等于其父辈节点深度加上任何其它节点的深度等于其父辈节点深度加上1。首先，扩展最深的节点使得搜索从起始节点沿某条单一路首先，扩展最深的节点使得搜索从起始节点沿某条单一路径进行下去；只有径进行下去；只有当搜索到达一个没有后裔的状态时，才考虑当搜索到达一个没有后裔的状态时，才考虑最近的另一条替代的路径最近的另一条替代的路径。替代路径与前面已经试过的路径不。替代路径与前面已经试过的路径不同之处仅仅在于：同之处仅仅在于：改变最后改变最后n步，而且保持步，而且保持n尽可能小尽可能小。对于许多问题，其状态空间搜索树的深度可能为无限深，对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了防止搜索过程沿着无益的路径扩展下去，往往深。为了防止搜索过程沿着无益的路径扩展下去，往往给出一给出一个节点扩展的最大深度个节点扩展的最大深度深度界限深度界限。任何节点如果达到了深。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的是，即使应用了深度界限的规定，所求得的解答路径并不一定解答路径并不一定就是最短的路径就是最短的路径。CSUCSUCSUCSUCSUCSUCSUCSUCSU含有深度界限的深度优先搜索算法含有深度界限的深度优先搜索算法如下：如下：(1)把起始节点把起始节点S放到未扩展节点放到未扩展节点OPEN表中。如果表中。如果此节点为一目标节点，则得到一个解。此节点为一目标节点，则得到一个解。(2)如果如果OPEN为一空表，则失败退出；否则继续。为一空表，则失败退出；否则继续。(3)把把OPEN表第一个节点表第一个节点(节点节点n)移到移到CLOSED表。表。(4)如果节点如果节点n的深度等于最大深度，则转向的深度等于最大深度，则转向(2)。(5)扩展节点扩展节点n，产生其全部后裔，并把它们放入，产生其全部后裔，并把它们放入OPEN表的前头表的前头，并提供从这些后继节点回到节点，并提供从这些后继节点回到节点n的的指针。如果节点指针。如果节点n没有后裔，则转向没有后裔，则转向(2)。(6)如果后继节点中有任一个为目标节点，则求得如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向一个解，成功退出；否则，转向(2)。CSUCSUCSUCSUCSUCSUCSUCSUCSU前端前端CSUCSUCSUCSUCSUCSUCSUCSUCSU例例：按深度优先搜索生成的八数码难：按深度优先搜索生成的八数码难题搜索树，我们设置题搜索树，我们设置深度界限为深度界限为5 5，空格移，空格移动为先左，后上，再右，最后下的动为先左，后上，再右，最后下的顺时针方顺时针方向向。从图可见，深度优先搜索过程是沿着一。从图可见，深度优先搜索过程是沿着一条路径进行下去，条路径进行下去，直到深度界限为止直到深度界限为止，然后，然后再考虑只有最后一步有差别的相同深度或较再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径浅深度可供选择的路径，接着再考虑最后两，接着再考虑最后两步有差别的那些路径，等等。步有差别的那些路径，等等。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU12385671238412384567412384567123845673712g1238456756712 38456712384567112384567123845671238456712384567211八数码难题的深度优先搜索树深度界限为413456123845671238456712384567123845671 238456712367812384567123845671 238456712 38456712384567123845678123456712384567481312384567569101415CSUCSUCSUCSUCSUCSUCSUCSUCSU有界深度优先搜索算法中，有界深度优先搜索算法中，深度界限的选择很重深度界限的选择很重要要。选择。选择过大过大，可能，可能会影响会影响搜索的搜索的效率效率；选择；选择过小过小，对于某些问题，可能它的解就位于某一分支较深的位对于某些问题，可能它的解就位于某一分支较深的位置，这样置，这样可能导致找不到问题的解可能导致找不到问题的解。所以，。所以，有界深度有界深度优先搜索策略是不完备的优先搜索策略是不完备的。深度优先搜索与宽度优先搜索的区别在于深度优先搜索与宽度优先搜索的区别在于：在对：在对节点节点n n进行扩展时，进行扩展时，宽度优先宽度优先搜索是将后继节点搜索是将后继节点放入放入OPENOPEN表的末端先进先出队列表的末端先进先出队列，而，而深度优先深度优先搜索则是搜索则是将后继节点将后继节点放入放入OPENOPEN表的前端后进先出栈表的前端后进先出栈。宽度优。宽度优先一般效率低，是一种完备的搜索策略，且能找到路先一般效率低，是一种完备的搜索策略，且能找到路径最短的解；深度优先一般效率高，不是一种完备的径最短的解；深度优先一般效率高，不是一种完备的搜索策略，不一定找到最短路径的解。搜索策略，不一定找到最短路径的解。CSUCSUCSUCSUCSUCSUCSUCSUCSU3.2.3 等代价搜索有有些些问问题题要要求求在在搜搜索索树树中中求求得得具具有有最最小小代代价价的的解解答答路路径径。宽宽度度优优先先搜搜索索可可以以被被推推广广用用来来解解决决这这种种寻寻找找从从起起始始状状态态节节点点至至目目标标状状态态节节点点的的具具有有最最小小代代价价的的路路径径问问题题，这这种种推推广广的的宽宽度度优优先先搜搜索索叫做等代价搜索算法，有如下一些记号：叫做等代价搜索算法，有如下一些记号：起起始始节节点点记记为为 S；从从节节点点 i 到到它它的的后后继继节节点点 j 的的连连接接弧弧线线代代价记为价记为 c(i,j)；从起始节点；从起始节点 S 到任一节点到任一节点 j 的的路径代价路径代价标记为标记为g(j)=g(i)+c(i,j)。搜搜索索树树上上，我我们们假假设设 g(i)是是从从起起始始节节点点 S到到节节点点 i 的最少代价路径上的代价。的最少代价路径上的代价。等等代代价价优优先先搜搜索索的的基基本本思思想想：每每次次从从OPEN表表中中选选择择一一代代价价最最小小的的节节点点，移移入入CLOSED表表。每每当当对对某某一一节节点点扩扩展展之之后后，就就要要计计算算它它所所有有后后继继节节点点的的代代价价，并并将将它它们们与与OPEN表表中中已已有有的的待待扩扩展节点按代价从小到大依次排序（代价小的排在展节点按代价从小到大依次排序（代价小的排在OPEN表最前）表最前）。CSUCSUCSUCSUCSUCSUCSUCSUCSU等代价搜索方法以代价等代价搜索方法以代价 g(i)的大小扩展其节点，其算法如下：的大小扩展其节点，其算法如下：(1)(1)把把起起始始节节点点 S 放放到到未未扩扩展展节节点点表表OPENOPEN中中。如如果果此此起起始始节节点点为一目标节点，则求得一个解；否则令为一目标节点，则求得一个解；否则令 g(S)=0；(2)(2)如果如果OPENOPEN是个空表，则没有解而失败退出；是个空表，则没有解而失败退出；(3)(3)从从OPENOPEN表表中中选选择择一一个个节节点点 i，使使其其 g(i)为为最最小小。如如果果有有几几个个节节点点都都合合格格，那那么么就就要要选选择择是是目目标标的的节节点点作作为为节节点点 i（要要是是有有目目标标节节点点的的话话）；否否则则，就就从从中中选选一一个个作作为为节节点点 i。把把节节点点 i 从从OPENOPEN表移至扩展节点表表移至扩展节点表CLOSEDCLOSED中；中；(4)(4)如果节点如果节点 i 为目标节点，则求得一个解；为目标节点，则求得一个解；(5)(5)扩展节点扩展节点 i，如果没有后继节点，则转向第，如果没有后继节点，则转向第(2)(2)步；步；(6)(6)对对于于节节点点 i 的的每每个个后后继继节节点点 j，计计算算 g(j)=g(i)+c(i,j)，并把所有后继节点并把所有后继节点 j 放进放进OPENOPEN表。提供回到节点表。提供回到节点 i 的指针；的指针；(7)(7)转向第转向第(2)(2)步。步。当所有弧线上的代价相等时，就变成了宽度优先搜索了当所有弧线上的代价相等时，就变成了宽度优先搜索了。CSUCSUCSUCSUCSUCSUCSUCSUCSU开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表i是否为目标节点？失败成功等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S是否目标节点是否目标节点？是是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否否CSUCSUCSUCSUCSUCSUCSUCSUCSU盲盲目目搜搜索索有有效效率率低低，耗耗费费过过多多的的计计算算空空间间与与时时间间等等不不足足。分分析析前前面面介介绍绍的的宽宽度度优优先先、深深度度优优先先搜搜索索，或或等等代代价价搜搜索索算算法法,其其主主要要的的差差别别是是OPENOPEN表表中中待待扩扩展展节节点点的的顺顺序序问问题题。人人们们就就试试图图找找到到一一种种方方法法用用于于排排列列待待扩扩展展节节点点的的顺顺序序，即即选选择择最最有有希希望望的的节节点点加加以以扩扩展展，那么，搜索效率将会大为提高。那么，搜索效率将会大为提高。启启发发信信息息：进进行行搜搜索索技技术术一一般般需需要要某某些些有有关关具具体体问问题题领领域域的的特特性性的的信信息息，把把此此种种信信息息叫叫做做启启发发信信息息。把利用启发信息的搜索方法叫做把利用启发信息的搜索方法叫做启发式搜索方法启发式搜索方法。3.3启发式搜索CSUCSUCSUCSUCSUCSUCSUCSUCSU假假设设初初始始状状态态、算算符符和和目目标标状状态态的的定定义义都都是是完完全全确确定定的的，然然后后决决定定一一个个搜搜索索空空间间。因因此此，问问题题就就在在于于如如何何有有效效地地搜搜索索这这个给定空间。个给定空间。启发信息按其用途可分为下列启发信息按其用途可分为下列3种：种：(1)用用于于决决定定要要扩扩展展的的下下一一个个节节点点，以以免免像像在在宽宽度度优优先先或或深深度优先搜索中那样盲目地扩展。度优先搜索中那样盲目地扩展。(2)在在扩扩展展一一个个节节点点的的过过程程中中，用用于于决决定定要要生生成成哪哪一一个个或或哪哪几个后继节点，以免盲目地同时生成所有可能的节点。几个后继节点，以免盲目地同时生成所有可能的节点。(3)用于决定某些应该从搜索树中抛弃或修剪的节点。用于决定某些应该从搜索树中抛弃或修剪的节点。在本节中，我们只讨论利用上述第一种启发信息的状态空在本节中，我们只讨论利用上述第一种启发信息的状态空间搜索算法，即间搜索算法，即决定哪个是下一步要扩展的节点决定哪个是下一步要扩展的节点。这种搜索总。这种搜索总是选择是选择“最有希望最有希望”的节点作为下一个被扩展的节点。这种搜索的节点作为下一个被扩展的节点。这种搜索叫做叫做有序搜索有序搜索(ordered search)。3.3.1 启发式搜索策略和估价函数CSUCSUCSUCSUCSUCSUCSUCSUCSU一一个个比比较较灵灵活活的的利利用用启启发发信信息息的的方方法法是是应应用用某某些些准准则则来来重重新新排排列列图图搜搜索索算算法法步步骤骤（8）中中OPEN表表上上的的所所有有节节点点的的顺顺序序。然然后后，搜搜索索就就可可能能沿沿着着某某个个被被认认为为是是最最有有希希望望的的边边缘缘区区段段扩扩展展。利利用用这这种种排排序序过过程程，需需要要某某些些估估算算节节点点“希希望望”的的量量度度，这这种种量量度度称称为为估价函数（估价函数（evaluation function）。估估价价函函数数提提供供了了一一个个评评定定侯侯选选扩扩展展节节点点的的方方法法。对对于于一一个个节节点点的的“希希望望”可可能能有有几几种种不不同同的的定定义义方方法法：如如试试图图确确定定一一个个处处在在最最佳佳路路径径上上的的节节点点的的概概率率；在在状状态态空空间间问问题题中中，一一种种方方法法是是估估算算目目标标节节点点到到此此节节点点的的距距离离或或差差别别；另另一一种种方方法法，如如棋棋盘盘式式的的博博弈弈难难题题中中根根据据棋棋局局的的某某些些特特点点来来决决定定中中间间状状态态棋棋局局的的估估价价值值，这这些些特特点点被被认认为为与与向向目目标标节节点点前前进进一一步步的的希希望望程程度度有有关关。每每种种不不同同的的衡衡量标准只能考虑该问题中这个节点的某些决定性特性。量标准只能考虑该问题中这个节点的某些决定性特性。我我们们用用符符号号 f 来来标标记记估估价价函函数数，用用 f(n)表表示示节节点点 n 的的估估价价函函数值。暂时令数值。暂时令 f 为任意函数形式。为任意函数形式。CSUCSUCSUCSUCSUCSUCSUCSUCSU我我们们用用估估价价函函数数 f 来来排排列列图图搜搜索索算算法法第第8 8步步中中OPENOPEN表表上上的的节节点点。根根据据习习惯惯，OPENOPEN表表上上的的节节点点按按照照它它们们 f 函函数数值值的的递递增增顺顺序序排排列列。根根据据推推测测，某某个个具具有有低低的的估估价价函函数数值值的的节节点点较较有有可可能能处处在在最最佳佳路路径径上上。应应用用某某个个算算法法（例例如如等等代代价价算算法法）选选择择OPENOPEN表表上上具具有有最最小小 f 值值的的节节点点作作为为下下一一个个要要扩扩展展的的节节点点。这这种种搜搜索索方方法法叫叫做做有有序序搜搜索索或或最最佳佳优优先先搜搜索索，而而其其算算法法就就叫叫做做有有序序搜搜索索算算法法或或最最佳佳优优先先算算法法。可可见见它它总总是是选选择择最最有有希希望望的的节节点点作作为为下下一一个要扩展的节点。个要扩展的节点。上上述述方方法法实实际际上上是是尼尼尔尔逊逊曾曾提提出出一一个个有有序序搜搜索索的的算算法法。估估价价函函数数 f 的的确确定定：一一个个节节点点的的“希希望望程程度度”越越大大，其其 f 值值越越小小。被选为扩展的节点，是估价函数最小的节点。被选为扩展的节点，是估价函数最小的节点。有序状态空间搜索算法如下：有序状态空间搜索算法如下：3.3.2 有序搜索CSUCSUCSUCSUCSUCSUCSUCSUCSU(1)(1)把把起起始始节节点点 S 放放到到OPENOPEN表表中中，计计算算 f(S)并并把把其其值值与与节节点点S 联系起来；联系起来；(2)(2)如果如果OPENOPEN是个空表，则失败退出，无解；是个空表，则失败退出，无解；(3)(3)从从OPENOPEN表表中中选选择择一一个个 f 值值最最小小的的节节点点 i。若若有有几几个个节节点点合合格格，当当其其中中一一个个为为目目标标节节点点时时，则则选选择择此此目目标标节节点点，否否则则就就选选择其中任一个节点作为节点择其中任一个节点作为节点 i；(4)(4)把把节节点点 i 从从OPENOPEN表表中中移移出出，并并把把它它放放入入CLOSEDCLOSED的的扩扩展展节节点表中；点表中；(5)(5)如果如果 i 是个目标节点，则成功退出，求得一个解。是个目标节点，则成功退出，求得一个解。(6)(6)扩扩展展节节点点 i，生生成成其其全全部部后后继继节节点点。对对于于 i 的的每每一一个个后后继节点继节点 j：(a)(a)计算计算 f(j)；(b)(b)如如果果 j 既既不不在在OPENOPEN表表中中，又又不不在在CLOSEDCLOSED表表中中，则则根根据据估估价价函函数数 f 把把它它添添入入OPENOPEN表表。从从 j 加加一一指指向向其其父父辈辈节节点点 i 的的指指针针，以便一旦找到目标节点时记住一个解答路径；以便一旦找到目标节点时记住一个解答路径；CSUCSUCSUCSUCSUCSUCSUCSUCSU(c)(c)如如果果 j 已已在在OPENOPEN表表上上或或CLOSEDCLOSED表表上上，则则比比较较刚刚对对 j 计计算算过过的的 f 值值和和前前面面计计算算过过该该节节点点在在表表中中的的 f 值值。如如果果新新的的 f 值值较较小，则小，则(i)(i)以此新值取代旧值；以此新值取代旧值；(ii)(ii)从从 j 指向指向 i，而不是指向它原来的父辈节点；，而不是指向它原来的父辈节点；(iii)(iii)如果节点如果节点 j 在在CLOSEDCLOSED表中，则把它移回表中，则把它移回OPENOPEN表；表；(7)(7)转向转向(2)(2)，即，即GO TO(2)GO TO(2)。步步骤骤（6.c）是是一一般般搜搜索索图图算算法法所所需需要要的的，该该节节点点在在图图中中可可能能有有一一个个以以上上的的父父辈辈节节点点。使使得得具具有有最最小小估估价价函函数数值值 f(j)的的节节点点被被选选为为父父辈辈节节点点。但但是是，对对于于搜搜索索树树，搜搜索索树树中中和和每每个个节节点点最最多多只只是是一一个个父父辈辈节节点点，所所以以（6.c6.c）可可以以略略去去。需需要要指指出出的的是是，即即使使搜搜索索空空间间是是一一般般的的搜搜索索图图，其其显显式式子子搜搜索索图图总总是是一一棵棵树树，因因为为节节点点 j 从来没有同时记录过一个以上的父辈节点。从来没有同时记录过一个以上的父辈节点。有序搜索算法框图下图所示：有序搜索算法框图下图所示：CSUCSUCSUCSUCSUCSUCSUCSUCSU开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小值最小的节点的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点，得后继节点j，计算，计算f(j)，提供返回，提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功有序搜索算法框图有序搜索算法框图是是否否是是否否v算法CSUCSUCSUCSUCSUCSUCSUCSUCSU宽宽度度优优先先搜搜索索、等等代代价价搜搜索索和和深深度度优优先先搜搜索索都都可可看看作作有有序序搜搜索索的的特特例例：对对于于宽宽度度优优先先，选选择择节节点点i 的的深深度度 d(i)作作为为估估价价函函数数 f(i)；对对于于深深度度优优先先，选选择择 1/d(i)作作为为估估价价函函数数 f(i)；对对于于等等代代价价搜搜索索，从从起起始始节节点点 S 至至节节点点 i 这这段段路路径径的的代代价价 g(i)作作估估价价函函数数为为f(i)。CSUCSUCSUCSUCSUCSUCSUCSUCSU有有序序搜搜索索的的有有效效性性直直接接取取决决于于估估价价函函数数 f 的的选选择择，如如果果选选择择的的 f 不不合合适适，有有序序搜搜索索就就可可能能失失去去一一个个最最好好的的解解甚甚至至全全部部的的解解。如如果果没没有有适适用用的的准准确确的的希希望望量量度度，那那么么 f 的的选选择择将将涉涉及及两两个个方方面面的的内内容容：一一方方面面是是考考虑虑效效率率、时时间间和和开开销销；另另一一方方面面是是保保证证有有一一个最优的解或任意解个最优的解或任意解。下下面面让让我我们们再再次次用用八八数数码码难难题题的的例例子子来来说说明明图图搜搜索索过过程程是是如如何应用估价函数排列节点的。我们考虑采用了简单的何应用估价函数排列节点的。我们考虑采用了简单的估价函数估价函数：f(n)=d(n)+W(n)其其中中 d(n)是是搜搜索索树树中中节节点点 n 的的深深度度；W(n)用用来来计计算算节节点点n 对应于目标棋局错放的棋子个数。对应于目标棋局错放的棋子个数。CSUCSUCSUCSUCSUCSUCSUCSUCSU例子：八数码难题（例子：八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：八数码难题的有序搜索树见下图：例如，起始节点棋局例如，起始节点棋局S0，其在搜索树中位于，其在搜索树中位于0层，所以层，所以d(S0)=0而它与而它与Sg中棋子位置不同的个数是中棋子位置不同的个数是4，即，即 W(S0)=4，所以有，所以有f(S0)=0+4=4CSUCSUCSUCSUCSUCSUCSUCSUCSU571453123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）612384（5）567813245671 2384567（5）（7）八数码难题的有八数码难题的有序搜索树序搜索树123846（4）75CSUCSUCSUCSUCSUCSUCSUCSUCSU上上图图表表示示出出利利用用这这个个估估价价函函数数 f 把把GRAPHSEARCH应应用用于于八八数数码码难难题题的的结结果果。图图中中的的数数字字表表示示该该节节点点的的 f 值值，由由 f 值值我我们们能能很很容容易易确确定定节节点点的的扩扩展展顺顺序序。从从图图可可见见，这这里里所所求求得得的的解解答答路路径径和和用用其其它它搜搜索索方方法法找找到到的的解解答答路路径径相相同同。不不过过，由由于于估估价价函函数数的的使使用用明明显显地地减减少少了了被被扩扩展展的的节节点点数数（如如果果估估价价函函数数定义为定义为 f(n)=d(n)，那么就得到了宽度优先搜索过程）。，那么就得到了宽度优先搜索过程）。正正确确地地选选择择估估价价函函数数对对确确定定搜搜索索结结果果具具有有决决定定性性的的作作用用。使使用用不不能能识识别别某某些些节节点点“真真实实希希望望”的的估估价价函函数数会会形形成成非非最最小小代代价价路路径径；而而使使用用一一个个过过多多地地估估计计了了全全部部节节点点希希望望的的估估价价函函数数（就就像像宽宽度度优优先先搜搜索索方方法法得得到到的的估估价价函函数数一一样样）又又会会扩扩展展过过多多的节点，降低求解效率。的节点，降低求解效率。CSUCSUCSUCSUCSUCSUCSUCSUCSU作业作业:试试比比较较宽宽度度优优先先、深深度度优优先先、等等代代价价搜搜索索和和有有序序搜索的主要区别。搜索的主要区别。CSUCSUCSUCSUCSUCSUCSUCSUCSU3.3.3 A*算法1、A*算法的估价函数：算法的估价函数：下面描述一特别的估价函数，该下面描述一特别的估价函数，该估价函数估价函数f使得任使得任意节点上函数值意节点上函数值f(n)能估算出从初始节点能估算出从初始节点S到节点到节点n的最的最小代价路径的代价和从节点小代价路径的代价和从节点n到某一目标节点的最小代到某一目标节点的最小代价路径的代价之总和价路径的代价之总和，即，即f(n)是约束地通过节点是约束地通过节点n的一条的一条最小代价路径的代价的一个估计值。因此，最小代价路径的代价的一个估计值。因此，OPEN表上表上具有最小具有最小f值的那个节点就是下一步要扩展的节点。正值的那个节点就是下一步要扩展的节点。正式讨论式讨论A*算法之前，先介绍几个记号：算法之前，先介绍几个记号：CSUCSUCSUCSUCSUCSUCSUCSUCSU令令k(ni，nj)表示任意两个节点表示任意两个节点ni和和nj之间最小代价之间最小代价路径的路径的实际代价实际代价(对于两节点间没有通路，函数对于两节点间没有通路，函数k没有没有定义定义)。从节点。从节点n到某个目标节点到某个目标节点ti，某条最小代价路径，某条最小代价路径的实际代价由的实际代价由k(n，ti)给出。令给出。令h*(n)表示目标节点集合表示目标节点集合ti上所有上所有k(n，ti)中最小的一个，因此，中最小的一个，因此，h*(n)就是从就是从节点节点n到目标节点最小代价路径的代价到目标节点最小代价路径的代价，而且，而且从从n到目到目标节点能够获得标节点能够获得h*(n)值的任一路径就是一条从值的任一路径就是一条从n到某到某个目标节点的最佳路径个目标节点的最佳路径(对于不能到达目标的节点对于不能到达目标的节点n，函数函数h*(n)没意义没意义)。CSUCSUCSUCSUCSUCSUCSUCSUCSU通常我们想知道通常我们想知道从已知起始节点从已知起始节点S到任意节点到任意节点n的一条最佳的一条最佳路径的代价路径的代价k(S，n)。为此，引进一个。为此，引进一个新函数新函数g*，这将使我们的，这将使我们的记号得到某些简化。对所有从记号得到某些简化。对所有从S开始可达到开始可达到n的路径来说，函数的路径来说，函数g*定义为：定义为：g*(n)=k(S，n)其次，我们定义函数其次，我们定义函数f*，使得在任一节点，使得在任一节点n上其上其函数值函数值f*(n)就是就是从节点从节点S到节点到节点n的一条最佳路径的实际代价加上从节点的一条最佳路径的实际代价加上从节点n到到某目标节点的一条最佳路径的代价之和某目标节点的一条最佳路径的代价之和，即，即 f*(n)=g*(n)+h*(n)因而因而f*(n)的值就是从初始节点值就是从初始节点S开始约束地通过节点开始约束地通过节点n的一的一条最佳路径的代价条最佳路径的代价，我们希望估价函数，我们希望估价函数f是是f*的一个估计，此估的一个估计，此估计由下式给出：计由下式给出：f(n)=g(n)+h(n)CSUCSUCSUCSUCSUCSUCSUCSUCSU其中：其中：g是是g*的估计；的估计；h是是h*的估计。对于的估计。对于g(n)，一个明显的选择就是搜索树中从一个明显的选择就是搜索树中从S到到n这段路径的代价，这段路径的代价，这一代价可以由从这一代价可以由从n到到S寻找指针时，把所遇到的各段寻找指针时，把所遇到的各段弧线的代价加起来给出弧线的代价加起来给出(这条路径就是从这条路径就是从S到到n的最小的最小代价路径代价路径)，显然有显然有g(n)g*(n)。对于。对于h*(n)的估计的估计h(n)，依赖于有关问题的启发信息，这类信息与八数码难，依赖于有关问题的启发信息，这类信息与八数码难题中的函数题中的函数W(n)所用的信息相似，因此把所用的信息相似，因此把h叫做启发叫做启发函数函数。CSUCSUCSUCSUCSUCSUCSUCSUCSU一般地，在一般地，在f(n)=g(n)+h(n)中，中，g(n)的比重越大，搜的比重越大，搜索方式就越倾向于宽度优先搜索；索方式就越倾向于宽度优先搜索；h(n)的比重越大，搜的比重越大，搜索方式就越倾向于深度优先搜索索方式就越倾向于深度优先搜索。g(n)的作用一般不可的作用一般不可忽略，因为它代表从初始节点到达目标节点的忽略，因为它代表从初始节点到达目标节点的总代价估总代价估值中实际已付出的部分值中实际已付出的部分，体现了搜索的宽度优先趋势体现了搜索的宽度优先趋势，这有利于搜索算法的这有利于搜索算法的完备性完备性，但影响算法搜索效率。当，但影响算法搜索效率。当g(n)远远小于远远小于h(n)时，时，g(n)可以忽略，则可以忽略，则f(n)=h(n)，这体，这体现了搜索的深度优先趋势现了搜索的深度优先趋势，有利于搜索，有利于搜索效率的提高效率的提高，但，但影响搜索算法的完备性，可能找不到问题的解。影响搜索算法的完备性，可能找不到问题的解。CSUCSUCSUCSUCSUCSUCSUCSUCSU2、A算法和算法和A*算法的定义算法的定义定义定义3.1 在一般图搜索过程中，如果第在一般图搜索过程中，如果第8步的重排步的重排OPEN表是表是依据依据 f(x)=g(x)+h(x)进行的，则称该过程为进行的，则称该过程为A算法。算法。定义3.2 在在A算法中，如果对所有的