《搜索求解与编程》唐瑞圭，韩靖编著|(epub+azw3+mobi+pdf)电子书下载

图书名称：《搜索求解与编程》

【作　者】唐瑞圭，韩靖编著

【页 数】 168

【出版社】 广州：中山大学出版社 , 1993.10

【ISBN号】7-306-00782-3

【价 格】$7.00

【分 类】搜索-运算方法 运算方法-搜索

【参考文献】 唐瑞圭，韩靖编著. 搜索求解与编程. 广州：中山大学出版社, 1993.10.

图书目录：

《搜索求解与编程》内容提要：

《搜索求解与编程》内容试读

第一章状态空间问题求解

第一节状态空间问题求解概念

状态空间问题求解是采用试探搜索的方法，在某一可能的解答空间中寻找一个解来解答一个问题的。到底何谓解答空间，搜索方法求解又是什么回事，我们不妨从一实际问题出发来说明它。

八位数码难题是由八个编有数码】至8并放在3×3的方格棋盘上的可走动的棋子组成，棋盘总有一格是空的。以便可以让周围的棋子走进空格，也可以说是移动空格，八位数码难题如（图1.1）所示，图中给出的两种棋局，即初始棋局和目标棋局。

初始棋局

目标棋局

图1.1

如何把初始棋局变成目标棋局呢？最直接的求解方法是尝试各种不同的走步，如“下移棋子8，右移棋子2，上移棋子1，…”等等，直到偶然得到该目标棋局为止。这种尝试在本质上涉及某种试探搜索，从初始棋局开始，我们要计算机由每一合适走步得到各种新棋局，然后计算机再走下一步，又得到下一组棋局，这样继续进行下去，直至找到目标棋局为止。我们把这种在搜索尝试过程中产生的所有棋局的集合看成是这一问题求解的状态空间，最后得出的一条由初始状态到目标状态的走步序列便是搜索求解的具体实现

要计算机实现状态空间求解，首先要解决的是有一计算机能接受的每一状态的表示和从一种状态变成另一状态的重写规则（也可说是产生新状态的途径）。实际上任何类型的数据结构都可用来描述各类问题的状态，其中包括符号、字符串、向量、二维数组、树和表格等。但是我们在解答某一具体问题时应注意所选的数据结构的形式与解决的问题在某些自然特征上要具有相似性，同时还必须注意所选择的这种状态描述具有方便的算法去重写它（即有方便的产生新状态的途径）。对于8数码难题采用3×3阵列表示是自然的，而棋子的正当走步（即改写途径）可以有32条，即左移棋子1，右移棋子1，上移棋子1,下移棋子1，左移棋子2…等。但我们立即可以发现，用左移空格，右移空格，上移空格，下移空格四条改写途径就完全可以代替上述32条途径。而后者的描述和操作要比前者简单得多，也将大大缩小搜索的状态空间，故我们应尽可能用经济的方法描述问题状态和走步规则。它是高效率解决问题的需要。

。1✉

图1.2是八数码难题的四条改写途径的图示。

2

8

3

1

4

65

左移空格

右移空格

上移空格

下移空格

283

8

2

3

2

3

28

1

1

4

8

16

765

7

65

7:6

7

图1.2

1

283

11

765

3

4

5

283

23

283

283

14

184

14■

164

765

765

765

75

6

7

8

9

10

2

12

13

83

283

23

23

28

283

283

283

21M

714

184

18M

143

145

164

164

765

65

765

765

765

76

75

75

14

15

16

17

18

19

20

3

83

283

123

234

28

283

283

283

21M

71M

84

18

143

145

64

16

765

65

765

765

765

76

175

751

22

23

2

25

26

83

813

283

283

123

需

61M

765

615

65

765

目标节点

图1.3

在图1.2图中我们可以把每一棋局看成一个节点，把从一棋局遵照所有可能的改写途径得出一组棋局的过程，称作扩展节点过程。最上方的一个节点称为下面4个节点的父节点，而下面4个节点又称为是上面一个节点的子节点（或称后继节点）。遵照这四条

·2。

改写途径，我们可将图1.1中初始棋局变换成目标棋局的一种搜索过程用图1.3表示出来，图1.3是一种树结构，初始节点为树根，它的深度为0，其它节点的深度等于其父节点的深度加1，也即第2行的节点深度为1，第3行节点深度为2…。其中每一节点左上方的数字是搜索过程中产生该节点的序号，同时也是用来扩展节点的顺序。按这种搜索方法从初始节点到目标节点遵照我们规定的走步原则共产生了26个棋局，也就是说这一问题求解的整个状态空间由26个节点组成，而粗线连接的一条走步序列就是一条解答路径。

第二节状态空间搜索要点

1.起始节点，对应于初始状态的描述。

2.扩展子节点，即用适合问题求解的改写途径扩展新节点。

3.为子节点设定指针，即记录其父辈节点的标号，以便找到目标节点时，沿指针能找出一条回到起始节点的途径。

4.检查各子节点是否为目标节点，如果还没有找到目标节点则又转回2，继续进行扩展子节点和设定指针的工作：当找到目标节点时，沿着有关指针从目标节点回湖！起始节点，打印这条解答路径。

从上面八数码难题例子，我们可能已经发现了一个问题，在我们扩展的所有节点中，没有两个状态是完全相同的，也就是说，在一般搜索过程中，我们把凡产生的节点状态与以前产生的某节点状态相同的节点都删掉，这就避免了搜索过程在原地兜图子的现象。

上述要点只是对状态空间搜索的一种简单描述，而当我们实际做某一具体搜索过程时，都会遇到被扩展节点的次序问题。我们可以根据被扩展节点的不同次序，分成宽度优

先、深度优先、等代价和A*算法几种不同的搜索方法。

L

(M

F

(F

(a)

(b】

宽度优先搜索节点扩展次序

深度优先搜索节点扩展次序

图1.4

如搜索是以接近起始节点的程度依次扩展节点的，就叫宽度优先搜索法。如图1.4()所示。图1.3所示八位数码难题搜索方法也就是用宽度优先搜索法进行的，在对下一层任一节点进行搜索之前，必须搜索完本层所有节点。

如果搜索是首先扩展最新产生的节点，则称这种搜索为深度优先搜索，如图1.4(b)

·3

所示。对于深度优先搜索，除非搜索失败（即不存在任何子节点，有时是指达到约定的最大深度还未找到目标节点)，而需要退出来去搜索其它原来被暂时忽略的节点外，否则每层只对一个节点进行扩展。

上述两种搜索方法都属盲目或称无信息搜索过程。

对于许多任务来说，有可能存在某些经验法则或原则来简化搜索。我们可以把这种经验法则称作一种启发信息，利用这些信息往往能首先扩展最有希望的节点，从而把搜索较

快地推向目标。这正是A·算法在搜索过程中最突出的长处，它往往能使搜索过程的时间

和状态空间大大缩小，对于那些因内存容量限制而难于解答的问题，采用带启发信息的

A·算法往往容易获得满意的解答。

还有一种搜索要求求解具有最小代价的特定解，对于这类问题，节点之间的连线具有

一定的代价，从起始节点到每一节点n都有一路径代价，我们用cost(n)表示，如果我们在搜索过程中，节点的扩展顺序按cost值的递增顺序扩展的。我们称此为等代价搜索（旧称等费用搜索)。它也是一种无信息搜索。

下面就各种搜索方法加以叙述。

第二章状态空间问题求解常用算法及例解

本章讲述状态空间中的各种搜索的算法和程序实现模式，并附实例说明。

第一节宽度优先搜索

一、定义与算法

在这种搜索过程中，树上的节点扩展是沿着深度的“断层”进行的，比如要对深度为的任一节点进行搜索扩展之前，深度为3的所有节点必须全部被搜索出来。所以这种搜索方法一定能保证找到最短（步数最少）的解答序列。在不少题中要求找到经历步骤最少而达到目标的方案时，多采用此种搜索方法。

宽度优先搜索的算法：

l.把初始节点放入待扩展节点的opn表中，此表开始只有起始节点，其结构为队结构，即先进先处理。

2.如果open表空，（即待扩展节点已全部扩展完毕），失败退出。

3.把opn表中队列前的节点取出，按合适的途径扩展全部子节点，并把新生的子节点依次加入opn表的后面，同时提供这些子节点返回父节点的指针，若无子节点，则返回2。

4.如果有任一子节点为目标节点，则找到一个解，打印路径退出。否则转2继续。

二、宽度优先搜索的程序实现

如何用程序实现宽度优先搜索法呢？下面介绍其具体的程序实现算法。为方便描述和阅读，本书对所有程序和算法描述中统一规定各变量的意义（有改变时再另行说明）。

算法描述中各变量意义

state(x):表示节点X的状态。state(1)表示初始状态。object:

表示作扩展的节点。

top:

表示由节点object扩展的子节点。也是栈顶指针或队尾指针。

father (x):表示节点X的父节点标号。也称父指针。

way(x):

表示扩展子节点的途径的第X种途径。

waymax:表示所有可能扩展子节点的途径的总数目。

waynum:

表示所选途径编号。

next(x):

链指针，用于表示按代价从小到大排序中节点的先后次序。

m(i,j):

表示从i节点到j节点的实际代价。

cost(x):

表示从初始节点到节点X的总代价。

·5

guess(x):表示节点X到目标节点的估计代价。也称启发函数的值

guesscost(x):表示从初始节点到节点X的总代价加上节点X到目标节点的估价函数作

有：

guesscost(X)=cost(X)+guess(X)

例题程序中对上述变量进行了简化。算法中

Pascal程序中

PC-BASIC和True BASIC中

state(x）

state (x)

S(x)

object

object

P

top

top

T

father(x)

father(x)

F(x)

way(x)

w(x)

W(x)

waynum

wayn

w

waymax

waymax

M

next(x)

next(x)

N(x)

cost (x)

cost(x)

C(x)

guesscost (x)

gcost(x)

G(x)

注意：下文算法中的1,2,3,4与流程图及程序实现模式中的1,2,3,4对应，与例题程序注释中的part 1,part2,part3,part4对应。另外在例题程序中Pascal程序中的数据文件可参考Basic程序中的data语句。

宽度搜索程序实现算法

1.把初始状态赋值到队头state(1)中，并初始化指针，1→object,.1→top。

2.分别用waymax种途径扩展object的子节点。

①从途径l开始扩展新节点，l→waynum。

②判断途径waynum可行吗？（即可否扩展新节点），若不可行转2一⑤。

③按途径waynum改写state(object)得到新节点状态，对新节点设父指针，新状

态入队。

top+l→top,object--→father(top),新状态→state(top)。

④state(top)是目标状态吗？是则调用打印结果子程序print打印路径。若只要求

一个方案则结束，否则top一1→top。

⑤waynum+l→waynum(选择下一途径再扩展)，若waynum≤waymax,则转2

-②。

3.选择用来扩展的新节点。

取队列首节点用来扩展节点，即object-+l→object,若object>top(即open表已

空)则结束，否则转2。

·仿

···试读结束···