第一题跳棋（1.PAS）
题目：跳棋的原始状态如下图。其中"0"表示空格，"-"表示白子，"+"表示黑子，"1——7"表示棋盘格编号。跳棋的规则是：
⒈任意一个棋子可移到相邻的空位上；
⒉可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关；
⒊棋子向左向右跳不限。
例如：4到1、5到4、3到5、6到3是成功的四步走法。请编一程序，用10步完成从原始状态跳变成目标状态。要求打印跳每一步后的状态，用数字表示棋盘格子的代号。如果有多种方法，请都分别打印出来。
1 2 3 4 5 6 7
原始位置 0 - - - + + +
目标位置 + + + - - - 0
输入:原始位置和目标位置，分别占一行，共两行。
0 - - - + + + (原始位置)
+ + + - - - 0（目标位置）
输出：10步完成从原始状态跳变成目标状态的过程
START:0 - - - + + +
NO.1:- 0 - - + + +
NO.2:- + - - 0 + +
……
NO.10:+ + + - - - 0
END
(注意:输入和输出的相邻两个棋子之间没有空格)
分析:
⒈数据库：数组ｇ构成堆栈，存放棋子的状态。
⒉结点的产生：与空位置间距－３到３的棋子可移入空位，生成新结点状态。
⒊搜索策略：含有深度界限的深度优先搜索。
program ex143_2;
type
status=string[7];
{const
start='0---+++';
obj='+++---0';}
var
g: array [0..10] of status;
i,j,k: integer;
start,obj:string;
fin,fout:text;
procedure draw;{输出}
var
i,j: integer;
begin
writeln(fout,'Start:',start);
for i:=1 to 10 do
writeln(fout,'No.',i,':',g[i]);
writeln(fout,'End');
end;
function exampass(w: integer): boolean;{判断有否重复状态} var
i: integer;
begin
for i:=1 to w-1 do
if g[i]=g[w] then begin
exampass:=false;
exit;
end;
exampass:=true;
end;
procedure run(t: integer);{搜索生成新结点}
var
i,k: integer;
begin
k:=pos('0',g[t-1]);
for i:=-3 to 3 do
if (i<>0) and (k+i>=1) and (k+i<=7) then begin
g[t]:=g[t-1];
g[t,k]:=g[t,k+i]; g[t,k+i]:='0';
if exampass(t) then
if g[t]=obj then draw
else
if t<10 then run(t+1); end; end;
begin
assign(fin,'1.in'); assign(fout,'1.out'); reset(fin); rewrite(fout); readln(fin,start); readln(fin,obj); close(fin);
g[0]:=start; run(1);
close(fout); end.
第二题 跳马程序（2.PAS ）
题目：在5*5格的棋盘上，从（1,1）点出发，按日字跳马，要求不重复地跳经所有方格。求出符合要求的所有跳马方案总数N 。
输入: 无
输出：前5行表示第一种移动方案。分别是5*5格棋盘每个方格被马通过时属于方案中的第几步。
第六行一个值N ，表示马不重复地跳经所有方格方案总数 输入输出样例:
1 1
2
3
4
5 2 3 4 5
program horse;
var
a:array[1..5,1..5] of integer; {记每一步走在棋盘的哪一格}
b:array[1..5,1..5] of boolean; {棋盘的每一格有没有被走过}
u,v:array[1..8] of integer; {8个方向上的x,y增量}
i,j,num:integer;
fout:text;
procedure print; {打印方案}
var
k,kk:integer;
begin
num:=num+1; {统计总方案}
if num=1 then {打印出前5种方案}
begin
for k:=1 to 5 do {打印本次方案}
begin
for kk:=1 to 5 do write(fout,a[k,kk],' ');
writeln(fout,'');
end;
end;
end;
procedure try(i,j,n:integer); {以每一格为阶段，在每一阶段中试遍8个方向}
var
k,x,y:integer; {这三个变量一定要定义局部变量}
begin
if n>25 then begin print; exit;end ; {达到最大规模打印、统计方案}
for k:=1 to 8 do {试遍8个方向}
begin
x:=i+u[k]; y:=j+v[k] ; {走此方向，得到的新坐标}
if (x<=5) and (x>=1) and (y<=5) and (y>=1)and b[x,y] then {如果新坐标在棋盘上，并且这一格可以走}
begin
b[x,y]:=false;
a[x,y]:=n;
try(x,y,n+1); {从(x,y)去搜下一步该如何走}
b[x,y]:=true;
a[x,y]:=0;
end;
end;
end;
begin
assign(fout,'2.out');
rewrite(fout);
u[1]:=1; v[1]:=-2; {8个方向的x,y增量} u[2]:=2; v[2]:=-1;
u[3]:=2; v[3]:=1;
u[4]:=1; v[4]:=2;
u[5]:=-1; v[5]:=2;
u[6]:=-2; v[6]:=1;
u[7]:=-2; v[7]:=-1;
u[8]:=-1; v[8]:=-2;
for i:=1 to 5 do {初始化}
for j:=1 to 5 do
begin
a[i,j]:=0;
b[i,j]:=true;
end;
a[1,1]:=1; b[1,1]:=false; {从(1,1)第一步开始走}
try(1,1,2); {从(1,1)开始搜第2步该怎样走}
writeln(fout,num); {输出总方案(304)}
close(fout);
end.
广度优先搜索训练题 一、奇怪的电梯 源程序名LIFT.PAS 可执行文件名 LIFT.EXE 输入文件名 LIFT.IN 输出文件名 LIFT.OUT 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？ 输入 输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 输出 输出文件仅一行，即最少按键次数,若无法到达，则输出-1。 样例 LIFT.IN 5 1 5 3 3 1 2 5 LIFT.OUT 3 二、字串变换 [问题描述]: 已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）: A1$ -> B1$ A2$ -> B2$ 规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为B2$ …。例如：A$＝'abcd' B$＝'xyz' 变换规则为： ‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’ 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换，使得 A$ 变换为B$。 [输入]: 键盘输人文件名。文件格式如下： A$ B$ A1$ B1$ \
/*程序利用C++程序设计语言，在VC6.0下采用宽度优先的搜索方式， 成功的解决了八数码问题。程序中把OPEN表和CLOSED表用队列的方式存储， 大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序 最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/ #include "iostream" #include "stdio.h" #include "stdlib.h" #include "time.h" #include "string.h" #include 图的广度优先搜索的应用 ◆内容提要 广度优先搜索是分层次搜索，广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。本讲座就最短路径问题、分酒问题、八数码问题三个典型的范例，从问题分析、算法、数据结构等多方面进行了讨论，从而形成图的广度优先搜索解决问题的模式，通过本讲座的学习，能明白什么样的问题可以采用或转化为图的广度优先搜索来解决。在讨论过程中，还同时对同一问题进行了深层次的探讨，进一步寻求解决问题的最优方案。 ◆知识讲解和实例分析 和深度优先搜索一样，图的广度优先搜索也有广泛的用途。由于广度优先搜索是分层次搜索的，即先将所有与上一层顶点相邻接的顶点搜索完之后，再继续往下搜索与该层的所有邻接而又没有访问过的顶点。故此，当某一层的结点出现目标结点时，这时所进行的步骤是最少的。所以，图的广度优先搜索广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。 本次讲座就几个典型的范例来说明图的广度优先搜索的应用。 先给出图的广度优先搜索法的算法描述： F:=0;r:=1;L[r]:=初始值; H:=1;w:=1;bb:=true; While bb do begin H:=h+1;g[h]:=r+1; For I:=1 to w do Begin F:=f+1; For t:=1 to 操作数do Begin ⑴m:=L[f]; {出队列}； ⑵判断t操作对m结点的相邻结点进行操作;能则设标记bj:=0,并生成新结点;不能,则设标记bj:=1; if bj:=0 then {表示有新结点生成} begin for k:=1 to g[h]-1 do if L[k]=新结点then {判断新扩展的结点是否以前出现过} begin bj:=1;k:=g[h]-1 有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有 连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。 深度优先搜索： 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 下面图中的数字显示了深度优先搜索顶点被访问的顺序。 "* ■ J 严-* 4 t C '4 --------------------------------- --- _ 为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则： (1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。 (2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。 (3) 如果不能执行规则1和规则2，就完成了整个搜索过程。 广度优先搜索： 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。 在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中， 算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区 域。它是用队列来实现的。 下面图中的数字显示了广度优先搜索顶点被访问的顺序。 实现广度优先搜索，也要遵守三个规则: ⑴ 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。（2）如果因为已经没有未访问顶点而不能执行规则1 第3章作业题参考答案 2.综述图搜索的方式和策略。 答：用计算机来实现图的搜索，有两种最基本的方式：树式搜索和线式搜索。 树式搜索就是在搜索过程中记录所经过的所有节点和边。 线式搜索就是在搜索过程中只记录那些当前认为是处在所找路径上的节点和边。线式搜索的基本方式又可分为不回溯和可回溯的的两种。 图搜索的策略可分为：盲目搜索和启发式搜索。 盲目搜索就是无向导的搜索。树式盲目搜索就是穷举式搜索。 而线式盲目搜索，对于不回溯的就是随机碰撞式搜索，对于回溯的则也是穷举式搜索。 启发式搜索则是利用“启发性信息”引导的搜索。启发式搜索又可分为许多不同的策略，如全局择优、局部择优、最佳图搜索等。 5.（供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态 为0，关状态为1，全部可能的状态为： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。 翻动琴键的操作抽象为改变上述状态的算子，即F ＝{a, b, c} a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次 问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}> 问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。 6.解：用四元组(f 、w 、s 、g)表示状态， f 代表农夫，w 代表狼，s 代表羊，g 代表菜，其中每个元素都可为0或1，用0表示在左 （0，0， （1，0，（0，0，（0，1，（1，1，（1，0，（0，1， （1，1， a c a b a c a b c b b c “八”数码问题的宽度优先搜索与深度优先 搜索 我在观看视频和查看大学课本及网上搜索等资料才对“八”数码问题有了更进一步的了解和认识。 一、“八”数码问题的宽度优先搜索 步骤如下： 1、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步； 2、由初始节点向第1层扩展，得到3个节点：2、 3、4；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若2、3、4节点均不是目标节点则转到第3步； 3、从第1层的第1个节点向第2层扩展，得到节点5；从第1层的第2个节点向第2层扩展，得到3个节点：6、7、8；从第1层的第3个节点向第2层扩展得到节点9；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若6、7、8、9节点均不是目标节点则转到第4步； 4、按照上述方法对下一层的节点进行扩展，搜索目标节点；直至搜索到目标节点为止。 二、“八”数码问题的深度优先搜索 步骤如下： 1、设置深度界限，假设为5； 2、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步； 3、由初始节点向第1层扩展，得到节点2，判断节点2是否为目标节点；若是则搜索过程结束；若不是，则将节点2向第2层扩展，得到节点3； 4、判断节点3是否为目标节点，若是则搜索过程结束；若不是则将节点3向第3层扩展，得到节点4； 5、判断节点4是否为目标节点，若是则搜索过程结束；若不是则将节点4向第4层扩展，得到节点5； 6、判断节点5是否为目标节点，若是则搜索过程结束；若不是则结束此轮搜索，返回到第2层，将节点3向第3层扩展得到节点6； 7、判断节点6是否为目标节点，若是则搜索过程结束；若不是则将节点6向第4层扩展，得到节点7； 8、判断节点7是否为目标节点，若是则结束搜索过程；若不是则将节点6向第4层扩展得到节点8； 9、依次类推，知道得到目标节点为止。 三、上述两种搜索策略的比较 在宽度优先搜索过程中，扩展到第26个节点时找到了目标节点；而在深度优先搜索过程中，扩展到第18个节点时得到了目标节点。 广度优先搜索（BFS）算法 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。 之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。 为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。 在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v 的路径中，那么u称为v的祖先，v是u的后裔。 下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点u∈V，其色彩存储于变量color[u]中，结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u 还没有被检索到)，则π[u]=NIL，由算法算出的源点s和顶点u之间的距离存于变量d[u]中，算法中使用了一个先进先出队列Q来存放灰色节点集合。其中 基于C语言的广度优先搜素算法的实现 1.算法说明 广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形： （1）把根节点放到队列的末尾。 （2）每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。 （3）找到所要找的元素时结束程序。 （4）如果遍历整个树还没有找到，结束程序。 本次算法的应用中，我用这个队列来保存最短路径。首先我定义队列为“真进假出”，所谓“真进”就是当添加一个元素时，把元素放置队尾，然后rear++, 而“假出”就是当删除一个元素时，并没有真的删除队首元素，只是front++。 通过比较搜索所得的所有可行路径的长度，这样我们就可以从队列中获取一条最短路径！ 2.代码及结果 #include 广度优先搜索 广度优先搜索 广度优先搜索类似于树的按层次遍历的过程。它和队有很多相似之处，运用了队的许多思想，其实就是对队的深入一步研究，它的基本操作和队列几乎一样。 三、队和广度优先搜索的运用 图4表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。 图4 分析：看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。如图5。 图5 首先想到的是用队的思想。我们可以a记录搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。具体过程如 下： （1）将城市A入队，队首0、队尾都为1。 （2）将队首所指的城市所有可直通的城市入队（如果这个城市在队中 出现过就不入队，可用一个集合来判断），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。 以下为参考程序： const ju:array[1..8,1..8] of integer=((1,0,0,0,1,0,1,1), (0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1)); type r=record {记录定义} city:array[1..100] of char; pre:array[1..100] of integer; end; var h,d,i:integer; a:r; s:set of 'A'..'H'; procedure out; {输出过程} begin write(a.city[d]); repeat d:=a.pre[d]; write('--',a.city[d]); until a.pre[d]=0; writeln; halt; end; procedure doit; begin h:=0; d:=1; a.city[1]:='A'; a.pre[1]:=0; s:=['A']; repeat {步骤2} inc(h); {队首加一，出队} for i:=1 to 8 do {搜索可直通的城市} if （ju[ord(a.city[h])-64,i]=0）and （not（chr（i+64） in s））then {判断城市是否走过} begin inc(d); {队尾加一，入队} 算法选择题（初级版）256道 1.二分搜索算法是利用（）实现的算法。 [单选题] * A.分治策略(正确答案) B.动态规划法 C.贪心法 D.回溯法 2.回溯法解旅行售货员问题时的解空间树是（）。 [单选题] * A.子集树 B.排列树(正确答案) C.深度优先生成树 D.广度优先生成树 3.下列算法中通常以自底向上的方式求解最优解的是（）。 [单选题] * A.备忘录法 B.动态规划法(正确答案) C.贪心法 D.回溯法 4.下面不是分支界限法搜索方式的是（）。 [单选题] * A.广度优先 B.最小耗费优先 C.最大效益优先 D.深度优先(正确答案) 5.采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（）。 [单选题] * A.O（n2^n） B.O（nlogn)(正确答案) C.O（2^n） D.O（n） 6. 分支限界法求解最大团问题时，活结点表的组织形式是（）。 [单选题] * A.最小堆 B.最大堆(正确答案) C.栈 D.数组 7. 下面问题（）不能使用贪心法解决。 [单选题] * A.单源最短路径问题 B.N皇后问题(正确答案) C.最小花费生成树问题 D.背包问题 8. 下列算法中不能解决0/1 背包问题的是（）。 [单选题] * A.贪心法(正确答案) B.动态规划 C.回溯法 D.分支限界法 9. 背包问题的贪心算法所需的计算时间为（）。 [单选题] * A.O（n2n） B.O（nlogn）(正确答案) C.O（2n） D.O（n） 10. 二分查找是利用（）实现的算法。 [单选题] * A. 分治策略(正确答案) B. 动态规划法 C. 分支限界法 D. 概率算法 11. 下列不是动态规划算法基本步骤的是（）。 [单选题] * A.找出最优解的性质 B.构造最优解(正确答案) C.算出最优解 D.定义最优解 12. 最大效益优先是（）的一种搜索方式。 [单选题] * A.分支界限法(正确答案) B.动态规划法 C.贪心法 D.回溯法 13. 在下列算法中有时找不到问题解的是（）。 [单选题] * A.蒙特卡罗算法 B.拉斯维加斯算法(正确答案) C.舍伍德算法 D.数值概率算法 Y 八数码问题 具体思路： 宽度优先算法实现过程 （1）把起始节点放到OPEN表中； （2）如果OPEN是个空表，则没有解，失败退出；否则继续； （3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中； （4）扩展节点n。如果没有后继节点，则转向（2） （5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针； （6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2）。 深度优先实现过程 （1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出； （3）把第一个节点从OPEN表移到CLOSED表； （4）如果节点n的深度等于最大深度，则转向（2）； （5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）； （6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。 方法 一：用C语言实现 #include 课程设计题目九：图的广度优先遍历 基本要求： 采用邻接表存储结构实现图的广度优先遍历。 （2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/ #include 算法设计：深度优先遍历和广度优先遍历实现 深度优先遍历过程 1、图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 以下假定遍历过程中访问顶点的操作是简单地输出顶点。 2、布尔向量visited[0．．n-1]的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。 -------------------------- 深度优先遍历(Depth-First Traversal) 1．图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的 一、深度优先搜索和广度优先搜索的深入讨论 （一）深度优先搜索的特点是： （1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。 但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法（二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。 （2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2-5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。 （3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。 （4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。 （5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。 如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是： （1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。 （2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。 《数据结构课程设计》报告题目：深度与广度优先搜索 --迷宫问题 专业计算机科学与技术 学生姓名李柏 班级B计算机115 学号1110704512 指导教师巩永旺 完成日期2013年1月11日 目录 1简介 (1) 2算法说明 (1) 3测试结果 (3) 4分析与探讨 (7) 5小结 (9) 附录 (10) 附录1 源程序清单 (10) 迷宫问题 1 简介 1、图的存储结构 图的存储结构又称图的表示，其最常用的方法是邻接矩阵和邻接表。无论采用什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。 2、图的遍历 图的遍历就是从指定的某个顶点（称其为初始点）出发，按照一定的搜索方法对图中的所有顶点各做一次访问过程。根据搜索方法不同，遍历一般分为深度优先搜索遍历和广度优先搜索遍历。 本实验中用到的是广度优先搜索遍历。即首先访问初始点v i，并将其标记为已访问过，接着访问v i的所有未被访问过的邻接点，顺序任意，并均标记为已访问过，以此类推，直到图中所有和初始点v i有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为最短路径。因此我们采用了广度优先搜索。 无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。广度优先搜索采用队列作为数据结构。 本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。具体实验内容如下： 选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“☆”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，则只输出迷宫原型图。 2算法说明 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。设置迷宫的长为n、宽为m，范围为49×49，用int maze[N+2][M+2]来表示，这样相当于在迷宫外层包了一层1，即防止搜索路径时跳出迷宫。 （1）手动生成迷宫 广度优先搜索实例 【例题】八数码难题(Eight-puzzle)。在3X3的棋盘上，摆有 8个棋子，在每个棋子上标有1～8中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局(初始状态)和目标布局(目标状态)，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。初始状态和目标状态如下： 初始状态目标状态 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 求解本题我们可以分3步进行。 问题分析： 由的解于题目要找是达到目标的最少步骤，因此可以这样来设计解题的方法： 初始状态为搜索的出发点，把移动一步后的布局全部找到，检查是否有达到目标的布局，如果没有，再从这些移动一步的布局出发，找出移动两步后的所有布局，再判断是否有达到目标的。依此类推，一直到某布局为目标状态为止，输出结果。由于是按移动步数从少到多产生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。 建立产生式系统： (1) 综合数据库。用3X3的二维数组来表示棋盘的布局比较直观。我们用Ch[i,j]表示第i 行第j列格子上放的棋子数字，空格则用0来表示。为了编程方便，还需存储下面3个数据：该布局的空格位置(Si，Sj)；初始布局到该布局的步数，即深度dep；以及该布局的上一布局，即父结点的位置(pnt)。这样数据库每一个元素应该是由上述几个数据组成的记录。 在程序中，定义组成数据库元素的记录型为： Type node＝record ch：array[1..3，1..3] of byte；{存放某种棋盘布局} si,sj:byte； {记录此布局中空格位置} dep,pnt：byte； end； 因为新产生的结点深度(从初始布局到该结点的步数)一般要比数据库中原有的结点深度大(或相等)。按广度优先搜索的算法，深度大(步数多)的结点后扩展，所以新产生的结点应放在数据库的后面。而当前扩展的结点从数据库前面选取，即处理时是按结点产生的先后次序进行扩展。这样广度优先搜索的数据库结构采用队列的结构形式较合适。我们用记录数组data来表示数据库，并设置两个指针：Head为队列的首指针，tail为队列的尾指针。(2) 产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看作空格向上、下、左、右4个位置移动，这样处理更便于编程。设空格位置在(Si，sj)，则有4条规则： ①空格向上移动： if si-1>=1 then ch[si,sj]:=ch[si-1,sj]；ch[si-1,sj]:=0 ②空格向下移动： if si+1<=3 then [si,sj]:=ch[si+1,sj]；ch[si+1,sj]:=0 宽度优先搜索算法 1.概述: 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。 之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。 例题hdu 1242 https://www.doczj.com/doc/f113075181.html,/showproblem.php?pid=1242 https://www.doczj.com/doc/f113075181.html,/zhuihunmiling/article/details/897 9570（DFS做法） 这一此我们介绍广度优先搜索 按照惯例，我们还是先说一下该题目的主要易错点 1.天使可能有多个朋友，所以不能从朋友的位置开始着天使，只能是从天使找离他最近的朋友 2.题目要求的是找到一个用时最少的朋友，而不是步数最少 既然是广度优先，那么必然用到队列，但是队列只能是先进先出，即是步数少的先遍历到，显然是不符合题目要求的，那应该怎么办呢？ c++给我们提供了标准的函数库，可以引入#include 《数据结构课程设计》报告 题目：深度与广度优先搜索 --迷宫问题 专业 计算机科学与技术 学生姓名 李柏 班级 B 计算机115 学 号 1110704512 指导教师 巩 永 旺 完成日期 2013年1月11日 目录 1简介 (1) 2算法说明 (1) 3测试结果 (3) 4分析与探讨 (7) 5小结 (8) 附录 (10) 附录1 源程序清单 (10) 迷宫问题 1 简介 1、图的存储结构 图的存储结构又称图的表示，其最常用的方法是邻接矩阵和邻接表。无论采用什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。 2、图的遍历 图的遍历就是从指定的某个顶点（称其为初始点）出发，按照一定的搜索方法对图中的所有顶点各做一次访问过程。根据搜索方法不同，遍历一般分为深度优先搜索遍历和广度优先搜索遍历。 本实验中用到的是广度优先搜索遍历。即首先访问初始点v i，并将其标记为已访问过，接着访问v i的所有未被访问过的邻接点，顺序任意，并均标记为已访问过，以此类推，直到图中所有和初始点v i有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为最短路径。因此我们采用了广度优先搜索。 无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。广度优先搜索采用队列作为数据结构。 本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。具体实验内容如下： 选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“☆”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，则只输出迷宫原型图。 2算法说明 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。设置迷宫的长为n、宽为m，范围为49×49，用int maze[N+2][M+2]来表示，这样相当于在迷宫外层包了一层1，即防止搜索路径时跳出迷宫。 （1）手动生成迷宫 数据结构复习题：查找 判断题 1、散列法存储的基本思想是由关键码的值决定数据的存储地址。 2、n个顶点的无向图至多有n(n-1)条边. 3、在有向图中,各顶点的入度之和等于各顶点的出度之和. 4、邻接矩阵只存储了边的信息,没有存储顶点的信息. 5、对同一个有向图来说,只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多. 6、如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图. 7、如果表示有向图的邻接矩阵是对称矩阵,则该有向图一定是完全有向图. 8、如果表示某个图的邻接矩阵是不对称矩阵,则该图一定是有向图. 9、连通分量是无向图中的极小连通子图. 10、强连通分量是有向图中的极大强连通子图. 11、对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图. 12、连通图的广度优先搜索中一般要采用队列来暂时存刚访问过的顶点. 13、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点. 14、有向图的遍历不可采用广度优先搜索方法. 15、连通图的生成树包含了图中所有顶点. 16、对n个顶点的连通图G来说,如果其中的某个子图有n个顶点、n-1条边,则该子图一定是G的生成树. 17、最小生成树是指边数最少的生成树. 18、从n个顶点的连通图中选取n-1条权值最小的边,即可构成最小生成树. 19、只要无向网中没有权值相同的边,其最小生成树就是惟一的. 20、只要无向网中有权值相同的边,其最小生成树就不可能是惟一的. 21、最短路径一定是简单路径. 22、有环图也能进行拓扑排序. 23、拓扑排序算法仅适用于有向无环图. 24、任何有向无环图的结点都可以排成拓扑排序,而且拓扑序列不惟一. 25、关键路径是由权值最大的边构成的. 26、在AOE网中,减小任一关键活动上的权值后,整个工期也就相应减少. 27、在AOE网中工程工期为关键活动上的权值之和. 28、在关键路径上的活动都是关键活动,而关键活动也必在关键路径上. 29、关键活动不按期完成就会影响整个工程的完成时间. 32、某些关键活动若提前完成,将可能使整个工程提前完成.图的广度优先搜索的应用
广度优先搜索和深度优先搜索
代价树如下图所示分别给出宽度优先及深度优先搜索策略-Read
“八”数码问题的宽度优先搜索与深度优先搜索
广度优先搜索
基于C语言的广度优先搜索
宽度优先搜索算法
算法选择题(初级版 )256道
深度宽度优先搜索 - 八数码
课程设计题目九：图的广度优先遍历
算法设计：深度优先遍历和广度优先遍历
深度优先搜索和广度优先搜索的深入讨论.
深度与广度优先搜索：迷宫问题
广度优先搜索 实例
广度优先搜索(Breadth-First-Search)
深度与广度优先搜索：迷宫问题
查找判断试题
相关主题
文本预览