图搜索技术中的状态空间法

1、第二章 图搜索技术我们经常用八数码难题或十五数码难题来说明问题求解的概念。十五数码难题是指由15个编有数码1至15并放在4×4方格棋盘上的可走动的棋子组成，棋盘上总有一格是空的，以便让周围棋子走入空格，或者说是移动空格，如图给出两种棋局:119415-123413125678758691011121321014131415初始棋局 目标棋局 图2.1 十五数码难题即初始棋局与目标棋局。让我们考虑如何把初始棋局变换为目标棋局。问题的解答就是某个合适的走步序列，如“左移棋子12，下移棋子15，右移棋子4”等等。在这类问题中，对初始情况和目标情况都是明确规定了的。还有一组把一种情况变换为另

2、一种情况的动作或走步。下面我们给出几个基本概念，用于讨论这一类问题的解答。 问题状态与算符要讨论上述问题解法，有必要引入下列几个概念。状态: 是表示问题解法中每一步问题状况的数据结构。算符: 则是把问题从一种状态变换为另一种状态的手段。状态空间: 是从初始状态出发所能达到的状态集合。下面四个相应的算符能够最自然地说明十五数码难题：空格左移、空格上移、空格右移及空格下移。在下棋问题中，这些算符对应于一定的走步。有时，某个算符（走步）不适用于某一状态；例如不能把“空格右移”运用于上述例子中的目标状态。用关于状态和算符的语言来描述一个问题的解即是某个能够把初始状态变为目标状态的算符序列。状态图: 把

3、初始状态可达到的各状态所组成的空间设想为一幅由各状态对应节点组成的图，这些节点与有关状态相对应，这种图称为状态图。 任何问题的求解技术,包括状态空间技术,都包括两方面内容: 表示 先表示 ,后搜索搜索 表示的好坏不同 状态空间大小相差很大 搜索效率 系统性能 关系我们首先研究状态空间的表示，然后再对各种搜索策略及其算法进行讨论。第一节 状态空间的表示211状态描述 在建立某个问题的状态空间（或问题空间）表示的过程中，必须清楚什么是这个问题的状态。在前例十五数码难题中，把棋局作为问题的状态是很自然的。但是，一个问题求解过程要找到一个解而实际上又不想移动棋子，就必须采用某些棋局的描述而不是棋局本身

4、。因此，任何状态问题描述的一个重要部分就是为该问题状态选择一些具体的描述方式。状态描述： 任何类型的数据结构都可以用来描述状态其中包括：符号、字符串、向量、二维数组、树和表格等对于十五数码难题，一个4 ×4 阵列理应是一个自然的状态描述方式。在选择状态描述方式时，我们还必须注意能够易于用算符对它们进行运算，以便从一种状态变换为另一种状态。例如：让我们考虑把代数式（AB+CD）/BC变换为较简单的表达式A/C+D/B的问题。这里，问题的状态显然是代数表达式。不过，我们还必须决定状态描述的方式。(1)一种常用的描述采用二元树。这种描述树的非终端节点代表 式中的算术运算符号（+ ，

5、5;和÷），而终端节点代表 式中的变量或常量符号（A，B，C和D）。这样，式（AB+CD）/BC 的描述树如图(a)所示。图中，节点÷的左分支代表分子，右分支代表分母。应用代数规则（状态空间算符）把这一状态描述变换为另一描述。对于所述的代数式子，可把它变换为如图(b)所描述的状态。 图(a) 图(b) (2)另一种常用的描述方式是线性字符串。式（AB+CD）/BC的一种可能的字符串描述为÷+×AB×CD×BC。其中，算术运算符号（÷+和×）叫做前缀，因为它们位于字符串中运算数的前面。因为我们知道每个运算符号只对两个

6、运算数进行运算，所以字符串是不需要标点符号的。例如，字符串中符号×的运算数必定是两个由合适的代数表达式描述的紧跟在此符号后面的子字符串，即×AB和×CD。应用字符串形式描述，我们可以把上述问题叙述为把字符串÷+×AB×CD×BC变换为字符串+÷AC÷DB的问题。2.1.2 算符与重写规则 算符把一种状态变换为另一种状态。因此，可以把算符看做定义域为状态集合的函数（实际上，算符只是部分函数，因为一个算符不可能适用于一切状态）。 当状态描述采用字符串形式时，我们有一个十分方便的方法来表示算符运算。这个方法应用

7、了重写规则（有时叫做产生式）的概念。 一套重写规则规定了由一个字符串变换为另一个字符串的方法。重写规则全部具有SiSj的形式，即字符串Si可变换为字符串Sj。例如，字符串 A$B$意味着出现在第一个字符串中的符号A 可被符号B 所取代。其中，$代表一任意的子字符串（包括空字符串）。在这条重写规则中，符号$用来指明当以B取代A时，A后面的字符串是不变的，则有字符串AEFDBEFD。在重写规则中可用几个$符号来指出几个不同的字符串。于是我们又可能有下列重写规则的例子：1. A$AA 以A 开始和结束的字符串可用单一出现的A 来取代2. $1BAB$2$1BB$2 出现在两个B之间的字符串可被删去3

8、. $1$2$3$1$2$2$3 任何子字符串均可被重复4. $1$2$2$3$1$2$3 任何相邻重复的子字符串可被删去例如，应用最后两个规则，我们可以把字符串ABCBABC变为字符串ABC：ABCBABCABABCBABCABABCABC一个重写规则常可以不同的方法用于某字符串。在上例中，规则4 完全不能用于字符串ABCBABC，而规则3却可以多种方法加以应用。显然，应用某个具体的重写规则是与某个算符相对应的。由于可以用单条重写规则来表示大量的不同算符，所以在问题求解方法中经常使用重写规则。用重写规则表示算符并不要求只限于由字符串描述的状态。例如，可以把类似的概念用于十五数码难题，其中，自

9、然状态描述是一个4×4的阵列。让我们用八数码难题（十五数码难题的一种简化形式）来说明重写规则的一般概念。在八数码难题中，八个编码棋子摆在一个3×3阵列中。一种表示八数码难题中棋子正当走步的方法是一套对阵列的重写规则。这些规则规定了把一种3×3阵列变换为另一种3×3阵列的方法。八数码难题的一套重写规则表示如下:X1X2X3<-àX1X2X3X4X5X4X5X6X7X8X6X7X8 双向，两条规则2.1.3 目标状态寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及然后检验这些新的状态描述，看其是否描述了该目标状态。这种检验往往只

10、是查看某个状态是否与给定的目标状态描述相匹配。综上所述我们可以看到，要完成某个问题的状态描述，我们必须确定三件事：l 该状态描述的方式，特别是初始状态描述；l 算符集合及其对状态描述的作用；l 目标状态描述的特性。前已述及，把状态空间表达为有向图是有益的。图表示法对于讨论各种状态空间搜索方法是特别有效的。2.1.4 图示法下面介绍图论中的几个术语和一些有关图的正式表示法。一个图由节点的集合构成（不一定是有限的节点）。一对节点用弧线连接起来，这些弧线从对子的一个节点指向该对子的另一节点。这种图叫做有向图。 ni nj如果某条弧线从节点ni指向节点nj ，那么节点nj 就叫做节点ni的后继节点或后

11、裔，而节点ni叫做节点nj 的父辈节点或祖先。在我们感兴趣的各种图中，一个节点只有有限个后继节点，因为产生式系统只有有限个适用规则。一对节点可能互为后裔，这时，该对有向弧线有时就用一条棱线代替。 ni nj当用一个图来表示某个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边标有算符。某个节点序列（ni1，ni2，nik）当j=2，3，k时，如果对于每一个nij-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为K 的路径。如果从节点ni至节点nj存在有一条路径，那么就称节点nj从节点ni可达到的节点，或者称节点nj为节点ni的后裔，而且称节点ni为节

12、点nj祖先。这样，(寻求一种状态è另一种状态的某个算符序列问题)ó寻求图的某一路径问题。费用: 给各弧线指定费用以表示加在相应算符上的费用。用C(ni，nj)来表示从节点ni指向节点nj 的那段弧线的费用。两节点间路径的费用 = 连接该路径上各节点的所有弧线费用之和。 初始状态 -à目标状态 解 某指定节点 -à 另一节点 路径 -最小费用 第二节 状态空间表示举例对各种问题都可以用状态空间法表示，并用状态空间搜索法来求解。下面举例之前，简单介绍产生式系统的描述搜索过程的方法。一个产生式系统由下列三个部分组成： (1)一个总数据库，它含有与具体任务有关的

13、信息。随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。(2)一套对数据库进行操作运算的规则，每条规则由左右两部分组成，左边部分鉴别规则的适用性或先决条件，右边部分描述规则应用时所完成的动作。应用规则来改变数据库，就像应用算符来改变状态一样。(3)一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。下面让我们来介绍几个状态空间表示的例子。例1 推销员旅行问题推销员旅行问题是个古典的综合问题。一个推销员计划做一次旅行，他必须访问如图所示的每个城市。每两个城市间的路径旁标有距离。问题的提法如下：

14、从城市A 出发，访问每个城市一次，且最多一次，并返回到城市A ，要求寻找一条距离最短的路线。为了确定这个问题，我们规定如下：(1)总数据库是到目前为止所访问过的城市表。初始数据库被描述为表（A）。我们不允许表中任一城市的出现多于一次，只有A 城市例外，但也只有当所有其他城市均已出现之后，才能再次出现A。(2)规则对应于决策：（a）下一步走向城市A：（b）下一步走向城市B；，（e）下一步走向城市E。一条规则除非能够把某个数据库变换为一合法的数据库，否则就不适用于这个数据库。因此应用“下一步走向城市A”这条规则就不适用于尚未出现所有城市的任一数据库。(3)任一以A为起点和终点，并出现所有其他城市的

15、总数据库，都满足终止条件。我们可以使用下图的距离图表来计算任一旅程的总距离。提出作为解答的任一旅程，必须是具有最短矩离的旅程。1007 C 推销员旅行问题地图下面给出求解该问题时可能生成的部分搜索树。树枝旁边的数字是应用相应规则时加到旅程上的距离增量。67 （A） (AB) (AC) (AD) (AE)例2 猴子和香蕉问题 状态描述模式: 用来描述一个状态集合的含有变量的表达式下面，我们举例来说明。 在人工智能文献中，“猴子和香蕉”问题常常被用来说明自动求解系统的操作。在一个房间内有一只猴子（可以认为这是一个机器人），一个箱子和一束挂在天花板上的香蕉。但猴子的高度不足以碰到香蕉，那么这只猴子怎

16、样才能摘到香蕉？现在我们用含有变量的状态来描述这个问题。 我们用一个四元表列（W ，x ，Y ，z ）来表示猴子和香蕉问题的状态，其中： W: 猴子的水平位置x: 当猴子在箱子顶上时取x = 1 ；否则取x = 0 Y: 箱子的水平位置z: 当猴子摘到香蕉时取z = 1 ；否则z = 0 这个问题中的操作（算符）如下：(1)goto（U）猴子走到水平位置U ，或者用产生式规则表示为：（W ，0 ，Y ，z ）goto(U)（U ，0 ，Y ，z ） 即应用操作goto（U），能把状态（W ，0 ，Y ，z ）变换为状态（U ，0 ，Y ，z ）。 (2)pushbox（V）猴子把箱子推到水平位

17、置V，即有：（W ，0 ，W ，z ）pushbox(V)（V ，0 ，V ，z ）应当注意的是:要调用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。(3)climbbox猴子爬上箱顶，即有：（W ，0 ，W ，z ）climbbox（W ，1 ，W ，z ）在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上。 (4)grasp猴子摘到香蕉，即有： （C ，1 ，C ，0 ） grasp（C ，1 ，C ，1 ）其中，C 是香蕉正下方的地板位置。

18、在应用算符grasp时，要求猴子和箱子都在位置C 上，并且猴子已在箱子顶上。 应当说明的是，在这种情况下，算符（操作）的适用性及作用均由产生式规则表示。令初始状态为（a ，0 ，b ，0 ）。这时goto(U)是唯一适用的操作，并导致下一状态（U ，0 ，b ，0 ）。现在有三个适用的操作，即goto(U)，pushbox(V)，和climbbox（若U=b）。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图如下。从图中不难看出，把该初始状态变换为目标状态的操作序列为：goto（b），pushbox（c），climbbox，grasp 第三节 搜索过程要点用图 来说明 状态空间。求

19、解一个能满足目标条件的问题可以表达为搜索一个图以找到一个满足目标状态描述的节点问题。讨论的所有状态空间搜索方法可以由下列图论方法来模拟：1.起始节点: 对应于初始状态描述。2.后继节点（又称子节点） 把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点，称为该节点的后继节点。令为推算所有后继节点的特别算符。我们把应用于某节点的过程叫做 扩展一个节点。3.指针: 从每个后继节点返回指向其父辈节点。当最终找到目标节点时，这些指针能够指出一条回到起始节点的路径。4.目标匹配: 检查各后继节点看其是否为目标节点。如果还没有找到目标节点，则继续进行扩展节点和设置指针的过程。当找到一个目标节点时

20、，沿着有关各指针可以从目标节点回溯到起始节点，产生一条解答路径。于是，对应于这条路径上各连线的有关状态描述算符，就构成一个解答序列。 对一个搜索过程的完全说明必须叙述被扩展节点的次序。宽（广）度优先搜索: 如果搜索是以接近起始节点的程度(由节点间连接弧线的数目来衡量)依次扩展节点的，就叫做宽度优先搜索，这种搜索是逐层进行的。深度优先搜索: 如果搜索时首先扩展最新产生的节点, 则称为深度优先搜索。上述两种搜索方法都属于盲目( 或称无信息)搜索过程, 其节点的扩展次序不受目标节点位置的影响。 5.搜索过程的主要控制问题是选出一个适用于待扩展节点的算符( 有时也称为规则) , 以产生后继节点; 或者

21、是在选择一个后继节点之后, 再选择一个合适的算符以产生一个新的后继节点。其他控制任务包括检验算符的适用条件, 测试终止条件以及记住用过的算符等。因此, 我们可以把控制系统( 即选择和确定控制策略的系统) 进行算符( 规则) 选择的过程看做一个搜索过程。 对于许多任务来说, 有可能指出经验法则或原则来简化搜索。任何这种用来加速搜索的技术取决于由图表示问题的特别信息。我们称这种信息为启发信息。利用这些信息, 我们往往能够首先扩展最有希望的节点, 从而把搜索较快地推向目标. 。 S if then if then 控制策略费用规则应用费用.G 系 统 总 费 用 控制策略费用规则应用费用计 算 费

22、用(为选优而增加的费用)搜索空间大小费用00 启发信息量传统的计算费用分为两类：规则应用费用和控制费用。一个完全无信息的控制系统只需要很少的控制费用，因为只是任意选取规则而不需要花费多少控制计算费用。但是，这种策略的规则应用费用却很高，因为一般说来，要找到一个解需要应用大量的规则。第四节 状态空间搜索策略2.4.1 图搜索策略显示图: 各节点及其具有费用的弧线由一张表明确给出;表: 每一节点 后继节点及连接弧线费用对 大型图 不切实际 对无限节点图不可能隐式图: 起始节点已知,后继节点算符已知 扩展节点 显示图可将使用隐式图的状态空间中的各节点划分为以下三类: 未生成节点-暂不放入计算机存储

23、已生成但尚未扩展节点-实现时放入一个OPEN表中 已扩展节点-实现时放入一个CLOSED表中 OPEN表格式 CLOSED表格式状态结构返回指针状态结构编号返回指针 一般的图搜索过程如下：GRAPHSEARCH过程 将始点S放到OPEN表中。 OPEN表为空 ? (Y) 失败退出 (N) 将OPEN表中的第一个节点n 取出，放入CLOSED表 n为目标点否 ? (Y) 输出解并成功退出 (N) 扩展节点n，即生成非n之祖先的后继节点集合M 注1 将M中那些既未在OPEN表,也没在CLOSED表中出现过的节点加入OPEN表,并逐一设置指向n的指针 对M中每一个出现于OPEN中的节点K来说,则要确

24、定一下它们是否应该”投奔新父点”n (当求最小费用路径时,必须进行这一判断) 注2 对M中每一个出现于CLOSED表中的节点K来说,则要:1确定一下 K是否应该”投奔新父点”n 2由于K 已扩展有子代,此时还需确认K 的子孙后代节点的指针方向是否也要修改 注3 按某一方式或按某个试探组，重排OPEN表 说明如下:2.4.2 启发式搜索策略在状态空间的盲目搜索中搜索到一个解，所需要扩展的节点数目可能是很大的。因为这些节点的扩展次序完全是随意的，而且没有应用已解决问题的任何特性。因此，除了那些最简单的问题之外，一般都要占用很多时间或空间（或者两者均有）。这种结果是组合爆炸的一种表现形式。 有关具体

25、问题领域的信息常常可以用来简化搜索。我们假设，初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间，因此，问题就是如何有效地搜索这个给定空间。进行这种搜索的技术一般需要某些有关具体问题领域的特性的信息。我们已把此种信息叫做启发信息，并把利用启发信息的搜索方法叫做启发性搜索方法。启发信息: 具有某些有关具体问题领域的特性的知识 启发信息分三种:用于决定下一个要扩展的节点 扩展节点时,用于决定要生成哪些后继节点,而非全部 用于决定某些应该从搜索树中抛弃或修剪的节点 第七节中，我们将提出一个只利用上述第一种启发信息的状态空间搜索算法，即决定哪一个是下一步要扩展的节点。一般，这种搜索总是

26、选择“最有希望”的节点作为下一个被扩展的节点。执行这种思想的搜索，叫做有序搜索或最佳优先搜索。“最有希望”之节点:标准1 以此节点距离目标节点的估计距离进行估算,近者为优 (注重 ”未来”)标准2 估算从起点S到此点,以及从此点到目标节点的”综合费用”,小者为优 (注重 ”历史”+ ”未来”) 第五节 宽度优先搜索2.5.1 定义在图搜索过程中，如果在有关问题的领域内没有任何启发信息可以用于排列OPEN表上的节点，这样得到的过程，叫做无信息搜索过程，又叫盲目搜索过程。在人工智能中，实际上我们对无信息搜索过程并不感兴趣，但是为了便于进行比较和加深对其他搜索过程或问题的理解，我们还是需要讨论两种类

27、型的无信息搜索，即宽度优先搜索和深度优先搜索。 宽度优先搜索: 按层次搜索 缺点: 时间长,如有解在有限层,必可找到 2.5.2 算法宽度优先搜索的搜索算法如下： 将始点S放到OPEN表中。 OPEN表为空 ? (Y) 失败退出 (N) 从OPEN表首取走一个节点n，将其放入CLOSED表之尾部(并在编号栏给出一个顺序号) 扩展节点n，将其子代节点依次放入OPEN表的 表尾 ,并逐一提供指向n的指针 是否有后继节点为目标节点 ? (Y) 输出解并成功退出 宽度优先搜索算法程序框图注: 2.5.3 例题例: 给出把宽度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有节点都标记它们所对应的

28、状态描述，每个节点旁边的数字表示节点扩展的顺序，我们预先规定产生后继节点的顺序如下：首先空格左移，接着上移，右移，最后向下移。如图示:例: 考虑一个由一张桌子和三个积木玩具组成的世界。这一世界的初始状态是这样的：积木块B 和C 放在桌面上，而积木块A 堆放在积木块B 上，如图所示。我们希望达到一个目标状态，三个积木这样堆叠在一起：积木A 在顶部，B 在中间，而C 在底部。ABACBC 初始态 目标态这个问题中的唯一算符为MOVE（X，Y ），即把物体X 移到物体Y 上面。这个算符应用的先决条件是：(1)被移动物体的顶部必须是空的；(2)如果Y 是积木（即不是桌子），则Y 的顶部也必须是空的；(

29、3)应用算符去操作同一状态不得多于一次（最后这一条件可从扩展节点表和非扩展节点表加以检查）；(4) 移动时按A、B、C顺序进行，即A 能移动时先移A。如图示：树上的节点为状态S0至S10十一个节点；例如，节点S1对应于由“移动积木A 到桌子上”，即MOVE（A，Table）而得到的S0的后继状态。各节点以它们的给定数字次序产生和扩展，即S0，S1，S2，S10。当此运算终止时，我们找到S10这一目标状态。被扩展节点表包括S0至S5，而OPEN表还包括有S6至S10各节点。2.5.4 等费用搜索及其算法(代价推进或代价驱动搜索)( 总朝着当前代价最小的节点方位向前推进 )例: 令c(i,j)表示

30、从节点i 到节点j 的连接弧线费用，g(i)为从起始节点S 到任一节点i 的路径费用。其算法如下： 将始点S放到OPEN表中。 S为目标节点 ? (Y) 退出 (N) 令 g(s) = 0 OPEN表为空? (Y) 失败退出 (N) 在整个OPEN表中选具有最小g(i)的节点i，将其放入CLOSED表 i为目标节点? (Y) 成功退出 (N) 扩展节点i，算出各后继j的g(j)值g(j)=g(i)+c(i,j)将各后继节点及其代价g值放入OPEN表 注 注: OPEN表格式 CLOSED表格式状态字符串代价g(i)代价g(i)状态字符串第六节 深度优先搜索 OPEN表及CLOSED表可设计为:

31、有界深度优先搜索算法 将始点s放到OPEN表中,置d(s)= 0 S为目标节点 ? (Y) 退出 (N) OPEN表为空 ? (Y) 失败退出 (N) 取出OPEN表中最前面(栈顶)的节点n，放入CLOSED表尾,编上顺序号 节点n的深度d(n)是否已到深度界限 ? (Y) (N) 扩展节点n，将其子节点n依次放入OPEN表前面(栈顶),并配上指向n的指针,置d(n)=d(n)+1 是否有任何后继节点为目标节点 (Y) 成功 (N) 首先扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。为了避免考虑太长的

32、路径（防止搜索过程沿着无益的路径扩展下去），往往给出一个节点扩展的最大深度深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。例: 深度优先搜索所产生的八数码难题搜索树其中，我们设置深度界限为5 。第七节 启发式搜索无论是宽度优先搜索或深度优先搜索，这些盲目搜索方法要寻找一个通向目标节点的路径，都是耗费十分大的,所以我们必须寻找比盲目搜索更有效的其他搜索方法。 对于许多任务来说我们能够利用与任务有关的信息来简化搜索过程，称此类信息为启发信息，而称这种利用启发信息的搜索过程为启发式搜索方法。2.

33、7.1 估价函数的应用启发式搜索: 生成子代时,“甩去”无希望者 总扩展最有希望的节点利用某些信息,应用某些规则重排OPEN表 有序搜索 沿着某个被认为是最有希望的边缘区段向外扩展。要应用这种排序过程，我们需要某些估算节点“希望”的量度。我们把这种估算节点“希望”的量度叫做估价函数。 我们用符号f 来标记估价函数，用f(n)表示节点n 的估价函数值。暂时令f 为任意函数，以后我们将会提出f 是从起始节点约束地通过节点n 而到达目标节点的最小费用路径上的一个估算费用。应用某个算法（例如等费用算法）选择OPEN表上具有最小f 值的节点作为下一个要扩展的节点，这种搜索方法叫做有序搜索或最佳优先搜索，

34、而其算法就叫做有序搜索算法或最佳优先算法。2.7.2 有序状态空间搜索算法( Best - First Search )尼尔逊（Nilsson） 1971年提出了一个有序状态空间的基本算法。估价函数f 是这样确定的：一个节点的希望程度越大，其f 值就越小。选为扩展的节点是估价函数最小的节点。假设状态空间为一个一般的图。 有序状态空间搜索算法如下：1.把起始节点S 放到OPEN 表中，计算f(S)并把其值与节点S 联系起来。2.如果OPEN是个空表，则失败退出，无解。3.从OPEN表中选择一个f 值最小的节点i 。4.将i 从OPEN表中移出，并把它放入CLOSED表中,并给出顺序编号。5.若i

35、 为目标节点，则成功退出，求得一个解。6.扩展节点i ，生成其全部后继节点 ，对于i 的每个后继节点j ： a）计算f(j)； b） 如果j 既不在OPEN表中，又不在CLOSED表中，则靠f 把它添入OPEN表，并设置j 指向其父辈节点i 的指针；注1 c） 如果j 已在OPEN表或CLOSED表中时 ，则拿新算出f 值和原OPEN表（或CLOSED表中）的原f 值进行比较 ，如果新的f 值较小，则： i) 以新f值取代原f值； ii) 从j 指向i ，而不再指向它（j）的“原父”点； iii) 若节点j 在CLOSED表中，则将其移回OPEN表。注27.转向2，即GO TO 2.。注释：1

36、) 在算法6中(b)处，每次往OPEN表中插入一新节点时，总按其f值将其插入到一个“合适”的位置（使节点有序）为好，这样做可免去： 算法第3步从OPEN表选最小f值的元素时，要找遍OPEN表； 算法第4步从OPEN表移走一个元素时，会出现“空洞”的麻烦；2) 算法6中(c) 之iii)处的处理方法，可省去一段程序，该段程序对 j的子孙后代进行是否需要修改返回指针及f值的判断与具体操作（参考Graph Search算法第7步）。运行该算法时，当再一次将j 从OPEN表移入CLOSED表中进行扩展时，仍会进行对其子代的相同检查与修改操作，这样逐层次进行下去（可能是间断地进行），最终也达到了检查j的

37、所有后代的指针方向与f值的相同效果。3) 有序搜索算法的特例设 f(n) = d(n) - 宽度优先搜索设 f(n) = - d(n)- 深度优先搜索 设 f(n) = 从起点S至节点n的路径费用 -等费用搜索4) 在Nilsson算法中，并没给出具体的f ：“估计过严”-有可能找不到解 或 最优解 “估计过宽”-可找到最优解 ，但搜索效率下降 5) 问题类型与f的选择类型(a) 问题有多个解，现要找最优解： f 应较“宽”；类型(b) 求解该类问题所需时间、空间费用太高，只要求找到一个较好的解，这时f应稍严；类型(c) 找到任一解，f应尽可能地“严”，使搜索范围尽可能小； 例： 解八数码难题时，对f的几种选法：(1) f(n)= w(n) 对应节点n的数据库中（距目标点的数据库来说）尚有多少没有到位的棋子数 f28=?316475 12384765 目标 “严” (2) f(n)= p(n) 设对应节点n的数据库中，每个数码i（ 1<=i<=8 ）移到目标位置所需的最短距离为li(注：可朝上、下、左、右四方向移动，而不用管该方位是否有子)，则定义 P(n)= li 8 lii=1 f28=?146375 “严”(3) f(n)= d(n)+w(n) d(n): 从n“走”到目标，还需付