算法与数据结构讲义三（搜索算法）

第十三课搜索算法

12.0搜索树

12.1搜索算法的基本原理

12.2广度优先搜索

12.3深度优先搜索

12.4练习

12.0搜索树

引例：在一个4*4的棋盘上的左下角有一个马，按照国际象棋的规则，将这个马跳到右

上角。

分析：首先建立棋盘的坐标，我们以左下角为(1,1),以右上角、

为(4,4)。按照马的移动规则，假定当前马的位置坐标为

(x,y),则移动方法有：

(1)x'=x+l;y'=y+2*

(2)x'=x+l；y'=y-2;

(3)x'=x+2;y'=y+l;

(4)x'=x+2;y'=y-l；

(5)x'=x-l;y'=y+2;

(6)x'=x-l;y'=y-2;

(7)x'=x-2;y'=y+l;

界限制无法到达)；(2,3汉可以跳到(1,1)、(4,4)、(4,2)、(3,1)四个点，(3,2)

可以跳达(1,1)、(1,3)、(2,4)、(4,4)四个点，……。

搜索树：按照数据元素的产生式规则建立起来的数据元素逻辑关系。

特点：(1)数据之间的逻辑关系为一对多。

(2)每个结点数据的下一级子结点是由该结点的产生式规则生成。

（3）目标结点（答案数据）一定在搜索树中能够出现。

（4）对于数据规模较大的问题，搜索树的结点将是海量的。

（5）搜索树可能是无穷无尽的（因为很多结点回重复出现）。

12.1搜索算法的基本原理：

从搜索树中可以看出，一个问题从起始状态，通过穷举的方式建立起搜索树后，目标状态一定能在

搜索树中出现。因此，只要建立起搜索树，就可以在其中搜索到目标状态（数据、路径、位置等）。

搜索算法要解决的问题：

产生式规则：由当前状态按照问题的需求和限制，生成新的状态的方法集合。

搜索树的生成和存储：一般采用一边生成，一边搜索；存储方法有：集合、栈。

搜索的方法：按行搜索：即从上到下，逐层搜索

双向按行搜索：一边从上往下（起始状态到中间状态），一边从下往上逐

层搜索（从目标状态到中间状态），找到相同的中间状态

即可。

回朔法搜索：优先向更深层结点查找，走不通则换一条路，无法换则退回

到上一层。

搜索状态的减少：在生成搜索树时，对于已搜过的中间状态的再次出现，是否需要

再次加入到树中重新搜索。

12.2广度优先搜索（bfs）

又称宽度优先搜索，是一种从搜索树的根结点开始，沿着树的宽度遍历树的结点。如果所有节点均

被访问，则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。

算法过程：

1、首先将根结点放入队列中。

2、从队首取出一个结点，按照产生式规则逐个生成新的结点数据，对新数据：

如果如果是目标结点，则结束算法并返回结果。

如果不是目标结点，则检查它是否已在搜索树中出现过，未出现就将它作为尚未检

查过的子结点加入到队列的队尾（特殊情况下，也有已出现过的结点重新入队的）。

3、重复步骤2。

4、若队列为空，表示整张图都检查过了，即目标无法达到，结束算法并返回“找

不到目标”的信息。

算法细化：

1、用哈希数组判断新生成的结点数据是否已出现过。

2、队列经常要多开一行，记录新结点的父亲（即该结点由上一层的哪个结点扩展而来），

用于最后输出过程。

3、如数据规模过大，需要使用循环队列（后果是无法记录父亲）。

算法框架：

functioncreat（i）

begin

caseiof

1：creat:=按照第一产生式规则生成新状态数据；

2:creat:=按照第二产生式规则生成新状态数据；

end;

end;

////////////////////////////////////////////////////////////////

procedurebfs;

begin

join（起始状态）;

whilenot（队空）do

begin

当前处理状态:=deq;

for;=第一产生式规则to最大产生式规则do

begin

新状态：=creat（i）;

if新状态=目标状态then

begin

print;

exit;

end

elseifnot（haxi［新状态］）then

begin

join（新状态）；

haxi［新状态］:=true;

end;

end;

end;

end;

空间复杂度：线性队列：0（最大可能状态数）

循环队列：0（最大可能状态数/2）

时间复杂度：最差情形下，BFS必须寻找所有到可能结点的所有路径。

0（最大可能状态数）

完全性：广度优先搜索算法具有完全性。只要目标存在，则BFS一定会找到。但是，若

目标不存在，且问题规模为无限大，则BFS将不收敛（不会结束）。

适用范围：广度优先搜索是找到第一个解的算法，即距离根结点的边数最少的解。

如果所有边的权值都相等（即所有产生新状态的代价相同），则这个解

也是最优解。

例一：将一个马从M*N的棋盘的左下角跳到右上角，需要的最少步数是多少？

分析：1、用一个的数组作为工作队列，用于存储搜索树。

2、使用m*n的二维哈希数组判重。

3、生成搜索树的同时，记录父节点的序号和新结点的层数。

4、最后从目标结点向起始结点回朔，用一个栈存储回朔的中间状态。

例二：在一个2n+l的一维棋盘上，有n个黑色棋子和n个白色棋子，初始状态如

••••OOOO

规定棋子移动规则如下：

1、如果某棋子的旁边正好为空，这枚棋子可以移动到空位置上。

2、如果某棋子的一侧有棋子，二那枚棋子的另一侧为空位置，这枚棋子可以跳过那

枚棋子到空位置上。

问：最少经过多少步，可以将棋盘状态变成

OOOO

分析:•**•

1、用2n+I位三进制数表示状态，如初始状态为：222201111,目标状态

为111102222。转化为十进制进行存储，另记录空格位置。

2、产生式规则：将棋子移动转化为空格的移动。

(1)空格向左移动

(2)空格向右移动

(3)空格向左跳动

(4)空格向右跳动

3、用一个［1..3八2n+l］的哈希数组判重。

例三：八数码问题。在一个3X3的九宫中有1一8这8个数及一个空格随机的摆放在

其中的格子里，如图1所示。现在要求实现这个问题：将该九宫格调整为如图2

所示的形式。调整的规则是：每次只能将与空格(上、下、或左、右)相邻的一

个数字平移到空格中。试编程实现这一问题的求解。

分析：1、字符串表达状态，另开一变量w记录空格位置。

2、空格移动规则：

(1)向下移动：w'=w+3。

(2)向上移动：w5=w-3。

(3)向左移动：w,=w-lo

(4)向右移动：w^w+lo

3、用穷举法判重。(将来可以用排序二叉树判重)

12.3深度优先搜索(dfs)

深度优先搜索是从根结点出发，沿着树的深度遍历树的结点。如果当前新产生的结点还有以此为根

的下一层结点，则沿此路继续下去，直到无法再深入访问时，回朔到上一层的结点，选另一条路继续深

人访问。反复此过程，直到所有结点都被访问到为止。

算法过程:

1、首先将根结点放入栈中。

2、取出栈顶结点，按照产生式规则生成新的结点数据，每产生一个：

检查是否是目标结点，如果是且比保存的数据更优，刷新所保存的数据。

检查该结点是否已搜过，如果是且比已保存的数据更优，则刷新所保存的数据，然后

该结点进栈；如没有搜过，则保存数据并进栈。

3、转第二步。

4、如果栈空，则算法结束。

细化说明：

1、一般用回朔法，利用递归使用系统栈。

2、哈希数组不仅用于判断新结点是否出现过，还用于保存到达该结点时的中间数据。

算法框架：

proceduredfs（结点数据）；

vari:integer;

begin

fori:=产生式规则一to最大产生式规则do

begin

新结点数据:=creaKi）;

if（新结点数据没有搜到过）or（新结点数据虽已搜过但本次搜索结果更优）

then

begin

更新新结点搜索结果；

dfs（新结点数据）；

end;

end;

proceduredfs（结点数据）；

vari:longint;

begin

fori:=Ito最大产生式规则do

begin

新结点:=creat⑴；

if新结点是目标结点then

begin

传回新结点；

t:=true;

exit;

end;

if新结点更优then

begin

更新新结点数据;

dfs（新结点）；

iftthenexit;

end;

end;

end;

空间复杂度：0（最大状态数）（主要用于存储各结点搜索结果）

时间复杂度：0（最大产生式规则数人最大状态数）

深度优先搜索的理论依据是建立在穷举基础上的，所以时间是几何级数级的，其优化

剪枝是非常必要的，因此，深搜的主要算法设计是在于如何剪枝，如何既高效地抛弃

不必要的子树，又不至于将最优解剪掉，将是深搜的最大难点。

适用范围：在缺乏有效的数学方法、递推算法，不符合动态规划要求，也没有专用算法

可以应对，一般考虑使用深搜；得分情况将取决于优化剪枝的技巧（30-100

分）。

例一：有A、B、C、D、E5本书，要分给张、王、刘、赵、钱5位同学，每人只能选1本。每个

人都将自己喜爱的书填写在下表中。请你设计一个程序，打印出让每个人都满意的所有分书

方案。

111\।।

|AIBICD|E|

111

张i11111

111V1VI|00110

1111

111

王iJ11

1|V|1|V111001

1111_1_______1

刘i11111

1|V|V1||01100

111_1________1

赵i11111

1111V||00010

111_1________1

钱it1111

1|V|1|V101001

1111111

分析：

1、朴素的穷举法：产生5本书的所有全排列，共有5!=120个,逐个检查各种排列是否

符合所有人的要求，符合则输出，否则丢弃。

穷举法的改进：例如产生一个全排列12345时，第一个数1表示将第一本书给小张。

但从表中可以看出，这是不可能的，因为小张只喜欢第三、第四本书。也就是说，1

XXXX这一类分法是不符合条件的。由此使我们想到，如果选定第一本书后，就立

即检查一下是否符合条件，当发现第一个数的选择不符合条件时，就不必再产生后面

的4个数了，这样做可以减少很多的运算量。换句话说，第一个数只在3和4中选择,

这样就可以减少3/5的运算量。同理，在选定了第一个数后，其他4个数字的选择

也可以用类似的方法处理，即选择第二个数后，立即检查是否符合条件。例如，第一

个数选3,第二个数选4后，立即进行检查，发现不符合条件，就另选第二个数。这

样就又把34XXX一类的分法删去了，从而又减少了一部分运算量。

3、

建立如上搜索树，每一层分发一本书，未向下扩展的结点为当前层已不合理，故剪去。

参考程序：

programdfs1;

consta:array[1..5,1..5]ofboolean=((false,false,true,true,false),

(true,true,false,false,true),

(false,true,true,false,false),

(false,false,false,true,false),

(false,true,false,false,true));

varoutf:text;

c:arrayl1..5Jofinteger;

hx:array[1..5]ofboolean;

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH

procedureprint;

vari:integer;

begin

fori:=lto5do

casec[i]of

l:write(outf,‘张')；

2:write(outf/3E');

3:write(outf,坟『)；

4:write(outf,‘赵')；

5:write（outf,'钱'）;

end;

end;

〃/〃〃〃〃//〃/〃/〃////〃//〃〃//〃〃〃〃/〃/////〃/〃/〃/〃〃/

proceduredfs(n:integer);

vari:integer;

begin

fori:=lto5do

if(a[i,n])and(not(hx[i]))then

begin

c[n]:=i;

ifn=5thenprint;

hx[i]:=true;

dfs(n+l);

hxlij:=false;

end;

end;

〃〃〃〃///〃〃/〃〃///〃〃〃〃〃///〃/〃〃〃///〃///〃〃////〃〃

begin

assign^utf/dfs-l.out);rewrite(outf)；

dfs(l);

close(outf);

end.

例二：跳马问题:在半张中国象棋盘上(5*9),有一匹马自左下角往右上角跳，今规定只许往右

跳，不许往左跳。编程计算共有多少种不同的跳行路线，并将路线打印出来。

例三：01000

01010

00000

OHIO

00010

表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着

走，要求编程序找出从左上角到右下角的路线。

例四：有一个m*n的滑雪场，请找出最长的滑雪道。

比如：244020302844

333520183040

403522151320

303525201218

284030101120

153012152012

从第一排开始下滑，只能向上、下、左、右四个方向，且下一个区域的高度必须低于当前

区域的高度，找出一条滑动距离最长的路径，可以在任何区域停止。

12.4习题:

1、营求(save)

【问题描述】铁达尼号发出了求救信号。距离最近的哥伦比亚号收到了信号，必须尽快赶到那

里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成nXn个比较小的单位,

其中用1标明的是陆地，用。标明的是海洋。船只能从一个格子移到相邻的四个格子。为了尽

快赶到出事地点，哥伦比亚号最少需要走多远的距离。

【输入格式】第一行为n,下面是一个nXn的0,1矩阵，表示海洋地图。最后一行为四个小

于等于n的整数，分别表示哥伦比亚和铁达尼号的位置。

【输出格式】哥伦比亚号到达铁达尼号的最短距离，答案精确到整数。

【输入样例】save,in

3

001

101

100

1133

【输出样例】save,out

4

【数据范围［n<=1000

2^硬币翻转（coin）

【问题描述】在桌面上有一排硬币，共n枚，每一枚硬币均为正面向上。现在要把所有的硬币

翻转成反面向上，规则是每次可翻转任意n—1枚硬币（正面向上的翻转成向下，向下的翻转成

向上）。求一个最短的操作序列（将每次翻转n—1枚硬币定为一次操作）。

【输入格式】只有一行，包含一个自然数n（n为不大于100的偶数）

【输出格式】第一行包含一个整数s,表示最少需要的操作次数。接下来s行每行分别表示每

次操作后桌上硬币的状态（一行包含n个整数（0或1）,表示每个硬币的状态，0正面向上，

1反面向上，不允许出现多余的空格）。对于有多种操作方案的情况，则只需输出一种。

【输入样例】coin,in

4

【输出样例】coin,out

4

0111

1100

0000010010

0010001010

0101010010

0100110110

0010000100

0001111100

0000000000

【输出样例】area.out

15

4、细胞(cell)

【问题描述】一矩形阵列由数字0〜9组成，数字广9代表细胞，细胞的定义是沿细胞数字上下

左右如果还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

如阵列：

0234500067

1034560500

2045600671

0000000089

有4个细胞。

【输入格式】第一行为整数mn,接着m行，每行n个数字

【输出格式】细胞的个数

【输入样例】cell,in

410

0234500067

1034560500

2045600671

0000000089

【输出样例】cell,out

4

5、最少转弯问题(turn)

【问题描述】给出一张地图，这张地图被分为nXm(n,水=100)个方块，任何一个方块不是

平地就是高山。平地可以通过，高山则不能。现在你处在地图(xl,yl)这块平地，问：你至

少需要拐几个弯才能到达目的地(x2,y2)?你只能沿着水平和垂直方向的平地上行进，拐弯

次数就等于行进方向的改变(从水平到垂直从垂直到水平)次数。如右图，最少拐弯5次。

【输入格式】第一行nm

第2到n+1行：整个地图的描述(0：平地，1：高山)。

1000010

第n+2行：xlylx2y2

【输出格式】S

【输入输出样例】

Turn,inTurn,out

575

1000010

0010100

0000101

0110000

0000110

1317

6、骑士周游世界。在国际象棋的棋盘上，有一位骑士按照国际象棋中马的行走规则从棋盘上的某

一方格出发，开始在棋盘上周游。若能不重复地走遍棋盘上的每一个方格，这样的一条周游路线在

数学上被称之为国际象棋盘上马的哈密尔顿链。请你设计一个程序，对于从键盘输入的任意一个起

始方格的坐标，由计算机自动寻找并按如下格式打印出国际象棋盘上马的哈密尔顿链。例如，当马

从坐标点(5,8)出发时，相应的哈密尔顿链如下图所示：

11।।

60|11262954|1324|21|

1111

1111

27|30|611225I22|5114

11

1111

10|59|285550|53|20|23|

1111

111

3161|57624348|1552

11111

1111

58|932|4956|19|42|11

11111

11111

33|663|4447|36|39|16I

1I111

111411|1

8|45|4I35|181237|

I111

1111

5|34|7I46|3|38|17|40|

।।।।।

7、有两个无刻度的量杯A和B,其容积分别为m升和n升(m>n),现在允许用量杯从水缸里取水或将水

倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量

得k