广度和深度优先搜索.doc

广度和深度优先搜索.doc 深度优先搜索和广度优先搜索——产生式系统 ?1 深度优先搜索和广度优先搜索 一、产生式系统 首先通过一个具体事例说明什么是产生式系统。 [例题4-1八数码难题] 在3X3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是:找到一种移动方法，实现从初始布局到目标布局的转变。 例如输入:(代表从前一布局到后一布局) 2 8 3 1 2 3 1 6 4 8 0 4 7 0 5 7 6 5 [ 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ] 状态表示:用二维数组来表示布局。(s,s)表示第i行、第j列上放的棋子数字。空格用0表示。 ij 产生规则:原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看做空格向四周移动。这样处理更便于编程。如果空格位置在(s,s)，则有四条规则: ij (1)空格向上移动: If s-1>=1 then ch(s,s):=ch(s-1,s);ch(s-1,s):=0 iijijij (2)空格向下移动: If s+1<=3 then ch(s,s):=ch(s+1,s);ch(s+1,s):=0 iijijij (3)空格向左移动: If s-1>=1 then ch(s,s):=ch(s,s-1);ch(s,s-1):=0 jijijij (4)空格向右移动: If s+1<=3 then ch(s,s):=ch(s,s+1);ch(s,s+1):=0 jijijij 搜索策略: (1)把初始状态作为当前状态; (2)从当前状态出发，运用四条移动规则，产生新的状态; (3)判断新的状态是否达到目的状态，如果是，转(5); (4)把新的状态记录下来，取出下一个中间状态作为当前状态，返回(2); (5)输出从初始状态到目标状态的路径，结束。 这个例子就是产生式系统。 产生式系统的组成: 产生式系统是由三个基本要素组成的:一个综合数据库(GOLBLE DATABASE)，一组产生式规则(Set of rules)，和一个控制系统(Control System)。 1、综合数据库:它是产生式系统所有的主要数据结构。它主要表示问题的状态，即初始状态，目标状态，和中间状态等，以及状态之间的关系。它不是固定不变的，在求解过程中，它的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 将越来越多，状态之间的关系也越来越复杂。经常用来表示数据库的数据结构有串，集合，数组，树，表，记录，队列等。[例题4-1八数码难题]使用数组这种数据结构表示状态，若压缩数据存储，把二维数组压缩为串，则数据库采用的数据结构就是串。 2、产生式规则:是对数据库进行操作的一系列规则。 规则的一般形式是:if 条件 then 操作 即满足应用的先决条件后，就对数据库实行后面的操作。 3、控制策略:它规定了操作的顺序既在什么条件下用什么规则进行操作，什么条件下停止操作，即它规定了问题的搜索策略和路线。一般的，控制策略分为两大类: 3.1不可撤回方式(IRREVOCABLE) 3.2试探法(TENTATIVE): 3.2.1回溯法(BACKTRACKING) 3.2.2图搜索法(GRAPH-SEARCH) 4、搜索策略: 搜索策略有两种基本方式:一种是不考虑给定问题的特有性质，按事先规定好的顺序依次运用规则，这是一种盲目搜索的方法，或称为无信息引导的搜索。另一种是考虑问题的特有性质，优先选用较合适的数据和规则，这称为启发式搜索，或有信息引导的搜索。目前，从这两种基本方式出发，已创造出多种具体的搜索方法。归纳起来有以下几种: 深度优先搜索和广度优先搜索——产生式系统 ?2 (一)求任一路径的搜索策略:回朔法(Backtracking)、爬山法(Hill climbing)、深度优先搜索法(Depth-first)、广度优先搜索法(Breadth-first)、限定范围搜索法(Beam search)、最优策略(Best first) (二)求最优路径的搜索策略:大英博物馆法(British Museum)、分支定界法(Branch and Bound)、动态规划法(Dynamic Programming)、最佳图搜索法(A*) (三)与或图搜索法:一般与或图搜索法(AO*)、极大极小法(Minimax)、a-b剪枝法(Alpha-beta Pruning)、启发式剪枝法(Heuristic Purning) 产生式系统的应用 [例题4—2] 有N枚硬币(N为偶数)正面朝上排成一排，每次将N—1枚硬币翻过来放在原位置上，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把翻币的最简过程及翻币次数打印出来(用x代表正面，O代表反面)。 [分析] 状态表示:显然可以用一个数组a描述当前的状态，当元素a[i]=“*”时，第i枚硬币朝上，a[i]=“o” 时，第i枚硬币朝下。 移动规则:根据题意每次翻动N—1枚硬币，相当于固定一枚硬币，把其他各枚硬币翻个。所以每次有n种操作 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 :固定第i{i?1((n}枚硬币，使其他硬币翻面。 搜索策略:把初始状态(即每一枚硬币正面朝上)作为当前状态; (1)从当前状态出发，运用移动规则，产生新的状态; (2)判断新的状态是否达到目标状态(即每一枚硬币反面朝上)，如果是，转(4); (3)把新的状态记录下来，取出下一个中间状态作为当前状态，返回(2); (4)输出从初始状态到目标状态的路径，结束。 上面的方法只是一种盲目的枚举，而没有考虑到题目的特殊性。题目只要求一组最优解，而一枚硬币不是正面朝上就是反面朝上，所以一组硬币的状态只取决于它有几枚硬币正面朝上、有几枚硬币反面朝上，而与硬币的排列无关，故很容易推出求解此题的简易算法。请大家自己思考。 [例题4—3] 从一整版正方形的邮票上可以撕成各种形状的四联票。下图是几种不同形状的四联票。编程由计算机寻找并画出可撕成所有形状的四联票。 [分析] 该题的一种解法是，先从一张邮票出发，在它的上、下、左、右分别联接上一张邮票，删去其中重复的。然后在剩下的二联票的基础上，在它们的上下左右再分别联上一张邮票，删去重复的，依此类推就可以得到问题的19个解。 (1)综合数据库:可以用二位数组来表示各种N联票，如果数组元素为1，表示该处有邮票，0表示该处没有邮票。比如图中的5种三联票，可以表示为: 111 010 110 110 100 000 110 100 010 110 000 000 000 000 000 开始时，数据库中仅有一个元素，即1张一联票。 (2)产生规则:4条 左联:if (a[i,j]=1) and (a[i,j-1]=0) then a[i,j-1]:=1 又联:if (a[i,j]=1) and (a[i,j+1]=0) then a[i,j+1]:=1 上联:if (a[i,j]=1) and (a[i-1,j]=0) then a[i-1,j]:=1 下联:if (a[i,j]=1) and (a[i+1,j]=0) then a[i+1,j]:=1 (3)控制策略可分为6步骤: S1:设I=1; S2:对所有I联票运用规则产生I+1联票; S3:对新产生的I+1联票判断是否重复，删去重复的，然后存入数据库; S4:检查所有I联票扩展完否,如果还有返回S2; S5:I增1，如果I<=4;返回S2执行; 深度优先搜索和广度优先搜索——产生式系统 ?3 S6:输出数据库所有四联票。 深度优先搜索和广度优先搜索——深度优先搜索 ?4 二、深度优先搜索 [例题4-4] 学校放寒假时，信息学竞赛辅导教师有A、B、C、D、E共5本书，要分给参加培训的张、王、刘、孙、李5位学生，每人只能选1本书。教师事先让每个人将自己喜爱的书填写在如下的表中。然后根据他们填写的表来分配书本，希望 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一个程序帮助教师求出所有可能的分书方案，使每个学生都满意。 书本 A B C D E 学生 Y Y 张同学 Y Y Y 王同学 Y Y 刘同学 Y 孙同学 Y x Y 李同学 [分析] 这个问题中因为每个人喜爱的书是随机的，没有什么规律，所以用穷举法解较合适。按穷举法的算法，应先不考虑一些条件。本题可以先不考虑“让每人都满意”这个条件，这样，只剩“每人选一本且只能选一本”这一个条件。在这个条件下，可行解就是5本书的所有全排列，一共有5!=120种。然后在这120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。 ，2，3，4，5分别表示这5本书。这五个数的一种全排列就是5本书的一种分为编程方便，设1 法。例如54321就表示第5本书(即E)分给张，第4本书(即D)分给王，„„，第一本书(即A)分给李。 “喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。排列的产生可以用穷举法，也可以用专门算法。 算法设计为:这个问题中因为每个人喜爱的书是随机的，没有什么规律，所以用穷举法借较合适。按穷举法的算法，应先不考虑一些条件。 S1:产生5个数字的一个全排列; S2:检查是否符合“喜爱书表”的条件，如果符合就打印出来; S3:检查是否所有排列都产生了，如果没有产生完，则返回S1; S4:结束。 上面算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，选第一本书即给张同学的书，1是不可能的，因为张只喜欢第三、四本书。这就是说，1X X X X一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不必选了，这样就可以减少运算量。换句话说，第一个数字只在3和4中选择，这样就可以减少3,5的运算量。同理，选定了第一个数字后，也不应该把其他四个数字一次选定，而是选择了第二个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。这样就把34X X X一类的分法在产生前就删去了，又减少了一部分运算量。 综上所述，改进后的算法应该是:在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第本书到第I+1本书的寻找过程是相同的，所以可以用递归方法。 算法设计如下: Procedure TRY(i); Begin For i:=1 to 5 do If 第i个同学分给第j本书符合条件then Begin 记录第i个数 If i=5 then 打印一个解 E1se TRY(i+1); 删去第i个数字 End End [源程序] program ex4_4; 深度优先搜索和广度优先搜索——深度优先搜索 ?5 Type five=1..5; Const Like:array [five,five] of 0..1=((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0), (0,0,0,1,0),(0,1,0,0,1)); name:array [five] of string [6]=('zhang','wang','liu','sun','li'); Var Book:array [1..5] of 0..5; Flag:set of five; C:integer; Procedure print;{打印结果} Var i: integer; Begin inc(c);writeln('Answer', c,':'); For i:=1 to 5 do Writeln(name[i]:10,':',chr(64+book[i])); End; Procedure calc(i:integer);{递归方法} Var j:integer; Begin for j:=1 to 5 do if not(j in flag) and (like[i,j]>0) then Begin {if 第j本书没有分下去 and 第i个同学也喜欢这本书 then} Flag:=flag+[j];book[i]:=j; {把第j本书分出去，把书给第i个同学} if i=5 then print { if 第五个同学已经有书了 then 打印结果} Else calc(i+1); { 否则给第i个同学分书} Flag:=flag-[j];book[i]:=0; End End; Begin{主程序} Flag:=[ ];c:=0;calc(1); Readln end. 状态搜索图(搜索过程): C(1) D(10) CA(2) CB(6) CE(7) DA(11) DB(14) DE(16) CAB(3) CEB(8) DAB(12) DAC(13) DBC(15) DEB(17) DEC(18) CEBD(9) CABD(4) CABDE(5) 注:(N)中的N代表结点产生的顺序。 从产生的顺序可以看出，深度越大的结点越先进行扩展，即先产生它的子结点。例如，有了结点(C)和(CA)后，并不是继续产生(C)的子结点，而是先产生(CA)的子结点(CAB)。这是由于(CA)的深度是2，(C)的深度是1，(CA)的深度大，所以先扩展。 这种在搜索过程中，深度大的结点先进行扩展的算法，我们就称它为深度优先搜索法。英语称之为Depth—First—Search，简称为DFS法。 上述算法实际是一个产生式系统。综合数据库就是一维数组book;产生规则是:在1至5中选择与前面已选定的数不相同的数;控制策略就是深度大的结点先扩展，深度达到5即是目标结点。 深度优先搜索基本算法(一) 深度优先搜索和广度优先搜索——深度优先搜索 ?6 从[例题4—4]可以看出，深度优先搜索法有两个显著特点: (1)对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点; (2)深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点。深度优先搜索的基本算法如下: 对于递归算法，递归过程为: Procedure DFSTRY(i); For i=1 to maxr do if子结点mr符合条件then产生的子结点mr压人栈; if子结点mr是目标结点then输出 Else DFSTRY(i+1); 栈顶元素出栈(删去Mr) Endif Enddo; 主程序为: ProgramDFS 初始状态入栈; DFSTRY(1); 对于非递归算法为: ProgramDFS(dcp); dep:=0; Repeat Dep: = dep+ 1; J: =0; p: =false; Repeat J: =j+l; If mr 符合条件then 产生子结点 mr 并将其记录; If 子结点是目标结点 then 印输出并出栈; Else p: = true; Else If j> =maxi then 回溯 else p: =false; Endif; Until p= true; Until dep = 0; 其中回溯过程如下: Procedure backtracking; Dep: = dep-1; If dep>0 then 取回栈顶元素 EIse p: =true; 不同问题的深度优先搜索基本算法是一样的，但在具体处理方法上和编程的技巧上，不尽相同，甚至会有很大的差别。 例如对于[例题4—4]的解法还可以这样来设计:从表中看出，孙同学只喜爱D一本书，无其他选择余地，因此可以在搜索前确定下来，这样程序就只需对剩下的四位同学进行搜索。另外，发现“喜爱书”的数组有多个0，为减少不必要的试探，该用链表来表示。例如第三位同学的链表是:Link(3，0)=2，表示他喜爱的第一本书的编号是2;Link(3，2)=3，即表示喜爱的书2后面是3，最后Link(3，3)=0，表示3是最后一本喜爱的书。根据上面的改进，基本算法不变，程序改进如下，读者可以比较两个程序的运行时间。 [源程序] Program ex4_4_1; Const Like:array [1..5,0..5] of byte=((3,0,0,4,0,0),(1,2,5,0,0,0),(2,0,3,0,0,0), (4,0,0,0,0,0),(2,0,5,0,0,0)); name: array [1..5] of string [6] = ('zhang','wang','liu','sun','li'); Var Book: array [1..5] of 0..5; Flag: set of 1..5; 深度优先搜索和广度优先搜索——深度优先搜索 ?7 C:integer; Procedure print; Var I: integer; Begin while j<>0 do begin Inc(c);writeln('Answer',c,':'); if not (j in flag) then Begin For i:=1 to 5 do Flag:=Flag+[j];book[I]:=j; Writeln(name[i]:10,':',chr(64+book[i])); If i=5 then print Else calc(i+1); End; Flag:=Flag-[j];book[i]:=0; End; Procedure calc(i: integer); j:=like[i, j] Var end j:integer; end Begin End; if book[i]>0 then if i=5 then print Else calc(i+1) BEGIN else begin Flag:=[4];book[4]:=4;c:=0; calc(1);Readln j:=like[i,0]; END. 深度优先搜索的应用 [例题4—5] 设有一个4X4的棋盘(即每行每列有四个正方形格的棋盘)，用四个棋子布到格子中，要求满足以下条件:任意两个棋子不在同一行或同一列或同一对角线上。试问有多少种棋局?编程把它们找到并打印出来。 [分析] 问题要求输出所有解，所以只能采用穷举的算法。因为每一行只有一颗棋子，所以只要枚举每一行的棋子所在的列数即可。 状态表示:用一个一维数组来描述这个4X4的棋盘，A[i](i?1..4)表示第i行的棋子摆在第A[i]列。题目要求任意两个棋子不在同一行、列、对角线，所以还需要几个数组记录某一行或列或是对角线是否已有棋子。 行:因为枚举是按行的，一行只有一颗棋子，所以不必判断。 列:可以用一个b [1..4]的布尔数组记录，当b[i]=true时表示第i列还没有棋子，否则已有棋子。 对角线:每个格子所在的对角线有两条，4 X 4的棋盘分别有7条斜向上和斜向下的对角线，可用两个布尔数组c，d [1..7]判断。 算法分析:首先我们枚举第一行的棋子的列坐标i，选定一个后，把a[i]赋值为i,把它所在的列(i)、所在的两条对角线(i,i+3)的数组元素赋值为false，再搜索第二行，如此递归搜索直到第四行棋子的列坐标确定，输出。 [源程序] program ex4_5; var var j:integer; t:integer; begin a:array [1..4] of 1..4; for j:=1 to 4 do b:array [1..4] of boolean; if b[j] and c[i+j-1] and d[j-i+4] then begin c,d:array [1..7] of boolean; a[i]:=j; if i=4 then procedure print; print var else begin i,j:integer; b[j]:=false; begin c[i+j-1]:=false; inc(t);writeln('Answer (', t,'):'); d[j-i+4]:=false; for i:=1 to 4 do calc(i+1); for j:=1 to 4 do begin b[j]:=true; if j=a[i] then write('*') else c[i+j-1]:=true; write('o'); d[j-i+4]:=true if j=4 then writeln end end {打印一组解} end end; end; procedure calc(i:integer); begin 深度优先搜索和广度优先搜索——深度优先搜索 ?8 fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); fillchar(d,sizeof(d),true); t:=0;calc(1);readln end. 深度优先搜索和广度优先搜索——深度优先搜索 ?9 [例题4—6覆盖问题] 右边长为N(偶数)的正方形，用NXN/2个长为2宽为1的长方形将它全部覆盖。编程打印所有覆盖方法。当N=4时几种覆盖方法及打印 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 举例如下: 2 1224 1 4 3 1334 5668 6 5 8 5778 7 [分析] 状态表示: 把这个编长为N的正方形划分为一个NXN的网格，用一个NXN的数组A来描述这个正方形，当A[i，j]>0时，表示这个小方格已被编号为A[i,j] 1X2的长方形覆盖，当A[i，j]=0时，表示这个小方格未被覆盖。 搜索策略为: S1:按行优先，列优先的原则找到一个A[i，j]=0的格子(i，j); S2:如果(i(1，2)->(2，4)->(4，begin calc(2) end. 3)->(5，1)->(6，3)->(8，4) program ex4_6; var [分析] n:integer; 状态表示: t:longint; 题目要求输出路径，而从棋盘的左下角走到 a:array [1..10,1..10] of integer; 右上角的步数不能确定，但每一步都只能往右走， 所以最多不会超过9。因此可以用一个一维数组 procedure print; A[1((9]记录每一步跳到的位置(X，Y)。 var i, j: integer; 移动规则: begin 马最多有4个方向，若原来的横坐标为i、 inc(t);writeln('Answer (',t,'):'); 纵坐标为j，则四个方向的移动可表示为: for i:=1 to n do begin 1:(i，j)->(i+1，j+2)(i<4，j<7); for j:=1 to n do write(a[i,j]:5); 2:(i，j)->(i+2，j+1)(i<3，j<8); writeln 3:(i，j)->(i-1，j+2)(i>0，j<7); end end; 4:(i，j)->(i-2，j+1)(i>1，j<8)。 搜索策略为 procedure calc(i: integer); S1:A[1]:=(0，0); var S2:从A[1]出发，按移动规则依次选定某个 j,k:integer; 方向，如果到达的是(8，4)则转S3，否则继续搜 begin 索下一个到达的顶点; j:=0; repeat S3:打印路径。 j:=j+1;k:=1; while (k<=n) and (a[j,k]>0) do inc(k); [源程序] until k<=n; program ex4_7; {找到第一个a[j,k]=0的格子(j,k)} const a[j,k]:=i; x:array [1..4,1..2] of if (i'); a[j,k+1]:=0 writeln ('(8,4)',t:5);readln end; end; a[J,k]:=0 end; procedure calc(i:integer); var begin j:integer; write(' Input n:');readln(n); begin if odd(n) or (n<0) then writeln(' Input data for j:=1 to 4 do error!') if (a[i-1,1]+x[j,1]>=0) and else calc(1); (a[i-1,1]+x[j,1]<=4) and (a[i-1,2]+x[j,2]>=0) and readln (a[i-1,2]+x[j,2]<=8) then end. begin a[i,1]:=a[i-1,1]+x[j,1];a[i,2]:=a[i-1,2]+x[j,2]; if(a[i,1]=4) and (a[i,2]=8) then print(i) 深度优先搜索和广度优先搜索——深度优先搜索 ?11 深度优先搜索基本算法(二) 前面用深度优先搜索算法求解问题的过程中，用堆栈来存放产生的结点，因此只保留了与当前结点有关的父辈结点，这样可以节省大量的存储空间。但如果求解的问题要求保留在搜索过程中产生的全部结点，算法需要如何设计呢? 可以用原综合数据库存放产生的结点，每个结点包括结点数据和父结点指针两项。再设置两个索引表:OPEN表和CLOSED表，OPEN表放还未扩展完其子结点的结点编号，CLOSED表放已扩展完的结点编号。为实现最新产生的结点先扩展的深度优先原则，OPEN表设计成堆栈形式。 算法设计如下: S1:初始化数据库，根结点放人数据库; S2:CLOSED表为空，根结点编号压入OPEN表; S3:如OPEN表为空，则转S7; S4:弹出OPEN表顶的结点为当前结点，扩展它的新子结点Mj存人数据库，并把编号压入OPEN表中; S5:如Mj是目标结点，则输出或记录; S6:返回S3; S7:结束处理。 [例题4—8] 六个城市之间道路联系如邻接矩阵所示。数字不为0表示两城市间有道路相通，数字表示路程。请编写程序，由计算机找到从C1城到C6城的所有不同路径(一个城市只去一次)，按照路程总长度的大小从小到大地打印出这些路径。 1 2 3 4 5 6 1 0 4 8 0 0 0 2 4 0 3 4 6 0 3 8 3 0 2 0 2 4 0 4 2 0 4 9 5 0 6 2 4 0 4 6 0 0 0 9 4 0 [分析] 道路之间的联系可以用一个6X6的“邻接矩阵”(及二维数组)LINK来表示，LINK(I，J)的值表示CI和CJ城之间的路程，如果值等于零表示没有通路; 建立产生式系统: 数据库:用数组OPEN作索引表，用NODE(字符串数组)记录路径，LONG记录路径长度; 产生式规则:R为下一个城市编号，2?R?6，K是当前路径，则有规则: IF LINK(K[LENGTH(K)]，R)>0且CR没有到过THEN 增加一个NODE元素，把新增元素赋值为:K+R; 增加一个OPEN元素，记录下NODE元素的位置。 [源程序] program ex4_8; const max=maxint; link:array [1..5, 1..6] of integer=((0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0), (0,4,2,0,4,9),(0,6,2,4,0,4)); {邻接表最后一行可以省略，因为到达c6后不能在到其他城市去} type path=string[6];{字符串记录路径} var open:array [1..6] of integer;{索引表} node: array [1..100] of path;{记录所有路径} count, i, n: integer; procedure calc(k,dep:integer); var r,len:byte; temp:path; 深度优先搜索和广度优先搜索——深度优先搜索 ?12 begin temp:=node[open[dep]];{取出 node表中最后一个元素} len:=length(temp);{不能再到其他城市} if pos('6',temp)>0 then exit else for r:=2 to 6 do if (link[k, r]>0) and (pos(chr(48+r),temp)=0) then begin{到达下一个城市} inc(n);node[n]:=temp+chr(48+r); open[dep+1]:=n;calc(r,dep+1) {搜索下一个城市} end end; procedure print; var f,i,j,k,l:integer; bool:array [1..100] of boolean; {记录路径是否打印} long:array [1..100] of integer; {记录路径总长} begin count:=0; for i:=1 to n do if node[i,length(node[i])]<>'6' then bool[i]:=false else begin bool[i]:=true;inc(count);long[i]:=0; for j:=2 to length(node[i]) do long[i]:=long[i]+link[ord(node[i, j-1])-48,ord(node[i,j])-48]; end; for i:=1 to count do begin k:=maxint; for j:=1 to n do if (bool[j]) and (long[j]',node[l, j]);{输出路径} writeln (' cost=', k){输出总长度} end; readln end; begin n:=1;node[1]:='1';open[1]:=1{赋初值};calc(1,1);print end. 1 1-->2-->3-->5-->6 cost=13 2 1-->2-->5-->6 cost=14 3 1-->3-->5-->6 cost=14 4 1-->2-->4-->3-->5-->6 cost=16 5 1-->2-->4-->5-->6 cost=16 6 1-->2-->3-->4-->5-->6 cost=17 7 1—>2-->4-->6 ccst=17 8 1-->2-->3-->4-->6 oost=18 9 1-->3-->4-->5-->6 cost=18 10 1-->3-->4-->6 cost=19 11 1-->3-->2-->5-->6 cost=21 12 1-->2-->3-->5-->4-->6 cost=22 13 1-->2-->5-->3-->4-->6 cost=23 14 1-->2-->5-->4-->6 cost=23 15 1-->3-->2-->4-->5-->6 cost=23 16 1-->3-->5-->4-->6 cost=23 17 1-->3-->2-->4-->6 cost=24 18 1-->3-->4-->2-->5-->6 cost=24 深度优先搜索和广度优先搜索——深度优先搜索 ?13 19 1-->3-->5-->2-->4-->6 cost=29 20 1-->3-->2-->5-->4-->6 cost=30 深度优先搜索和广度优先搜索——广度优先搜索 ?14 三、广度优先搜索 在深度优先搜索算法中，深度越大的结点越先得到扩展。若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法，下面通过一个具体实例来讨论广度优先算法的一般规律。 [例题4-1八数码难题] 在3X3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是:找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。 例如输入:(代表从前一布局到后一布局) 2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5 [分析] 由于题目要找到的解是达到目标最少步骤，因此解题的方法为:从初始状态出发，先把移动一步后的布局全部找到，检查是否达到目标布局;如果没有，再从这些移动一步的布局出发，找到移动两步后的所有布局，再判断是否有达到目标的;如此继续，一直达到目标状态为止，输出结果。由于是按移动步数从少到多产生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。 建立产生式系统。其中:综合数据库显然用3X3的二维数组来表示布局比较直观。用ch(i,j)表示第i行第j列格子上放的棋子数字，空格则用0表示。为了方便编程，还需存储该布局的空格位置:(s,s);ij初始布局到该布局的步数，即深度dep;该布局的上一布局，即父结点的位置。这样数据库每一个元素应该是由上述几个数据组成的记录。 因为新产生的结点深度(也即从初始布局到该结点的步数)一般要比数据库原有结点大(或相等)，按步数大的后扩展的要求，应该放在数据库的后面。而当前扩展的结点从数据库前面选取，即符合先产生的先扩展，后产生的后扩展规律。所以数据库的结构用队列的结构形式较合适。用上述记录为元素的数组data来表示数据库，并设置两个指针:closed为队列的首指针，open为队列的尾指针。 产生规则:原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看做空格向四周移动。这样处理更便于编程。如果空格位置在(s,s)，则有四条规则: ij (1)空格向上移动: If s-1>=1 then ch(s,s):=ch(s-1,s);ch(s-1,s):=0 iijijij (2)空格向下移动: If s+1<=3 then ch(s,s):=ch(s+1,s);ch(s+1,s):=0 iijijij (3)空格向左移动: If s-1>=1 then ch(s,s):=ch(s,s-1);ch(s,s-1):=0 jijijij (4)空格向右移动: If s+1<=3 then ch(s,s):=ch(s,s+1);ch(s,s+1):=0 jijijij 用数组D和H来表示移动的行列增量，则有: ij R 1 2 3 4 方向 左 上 右 下 D 0 -1 0 1 i H -1 0 1 0 j 算法设计: program ex4_1_2; 初始化;把初始布局存入数据库data 设首指针closed:=1;尾指针open:=0 repeat open增1，取出队列首纪录为当前被扩展节点; for r:=1 to 4 do {r是规则编号} begin if 新空格位置合法 then begin closed 增1，把新布局存入队尾 深度优先搜索和广度优先搜索——广度优先搜索 ?15 if 新布局与队列中原有纪录重复 then 删除新产生的布局 else if 达到目标 then 输出并退出 end end until open>=closed{队列空} [源程序] {$M 65521,0,655360} if b[j,k]<>c[closed]^[j,k] then l:=1; if l=0 then begin program ex4_1_1; const assign(f,fn2);rewrite(f); fn1='ex4_1.in'; j:=0; fn2='ex4_1.out'; repeat type inc(j);e[j]:=closed; xtype=array [1..3,1..3] of 0..8; closed:=father^[closed]; ctype=array [1..10000] of ^xtype; until closed=0; dtype=array [1..10000] of integer; for k:=j downto 1 do begin var for i:=1 to 3 do begin a,b:xtype; for j:=1 to 3 do c:ctype; write(f,c[e[k]]^[i,j]:3); dep,father:^dtype; writeln(f) x0:array[1..10000,1..2] of byte; end; writeln(f) procedure init; end; var close(f);halt f:text; end; i,j:integer; end; begin new(dep);new(father); procedure cheakup; for i:=1 to 10000 do new(c[i]); var assign(f,fn1);reset(f); i,j,k,l:integer; for i:=1 to 3 do begin begin for j:=1 to 3 do read(f,a[i,j]); for i:=1 to closed-1 do begin readln(f); l:=0; end; for j:=1 to 3 do for k:=1 to 3 do readln(f); if c[i]^[j,k]<>c[closed]^[j,k] then l:=1; for i:=1 to 3 do begin if l=0 then begin dec(closed);exit end for j:=1 to 3 do read(f,b[i,j]); end; readln(f) bool; end; end; close(f); end; begin open:=0;closed:=1; procedure calc; c[closed]^:=a;dep^[closed]:=0; var father^[closed]:=0;bool; i,j,k:integer; for i:=1 to 3 do for j:=1 to 3 do open,closed:integer; if a[i,j]=0 then begin d:xtype; x0[1,1]:=i;x0[1,2]:=j end; repeat procedure bool; inc(open); var d:=c[open]^; i,j,k,l:integer; i:=x0[open,1];j:=x0[open,2];k:=dep^[open]; f:text; if i>1 then begin e:dtype; inc(closed);c[closed]^:=d; begin c[closed]^[i,j]:=c[closed]^[i-1,j]; l:=0; c[closed]^[i-1,j]:=0; for j:=1 to 3 do for k:=1 to 3 do dep^[closed]:=k+1;father^[closed]:=open; 深度优先搜索和广度优先搜索——广度优先搜索 ?16 x0[closed,1]:=i-1;x0[closed,2]:=j; c[closed]^[i,j]:=c[closed]^[i,j+1]; cheakup c[closed]^[i,j+1]:=0; end; dep^[closed]:=k+1;father^[closed]:=open; if i<3 then begin x0[closed,1]:=i;x0[closed,2]:=j+1; cheakup inc(closed);c[closed]^:=d; c[closed]^[i,j]:=c[closed]^[i+1,j]; end; c[closed]^[i+1,j]:=0; until (open>=closed) or (closed>=10000); dep^[closed]:=k+1;father^[closed]:=open; end; x0[closed,1]:=i+1;x0[closed,2]:=j; cheakup procedure print; end; var if j>1 then begin f:text; begin inc(closed);c[closed]^:=d; c[closed]^[i,j]:=c[closed]^[i,j-1]; assign(f,fn2);rewrite(f); c[closed]^[i,j-1]:=0; writeln(f,'No solution!');close(f) dep^[closed]:=k+1;father^[closed]:=open; end; x0[closed,1]:=i;x0[closed,2]:=j-1; cheakup begin end; init;calc;print if j<3 then begin end. inc(closed);c[closed]^:=d; 程序运行结果为: 第一步 第二步 第三步 第四步 第五步 第六步 283 283 203 023 123 123 164 104 184 184 084 804 705 765 765 765 765 765 程序先产生深度为1结点，在产生深度为2的结点，最后产生目标深度为5的结点。先横向扩展，再纵向深入。由此，我们可以得到广度优先的基本算法: program BFS; 初始化;把初始布局存入数据库data 设首指针closed:=1;尾指针open:=0 repeat open增1，取出open所指结点进行扩展; for r:=1 to max do {r为产生规则编号} begin if 子结点符合条件 then begin closed 增1，把新接点存入数据库队尾 if 新结点与原结点重复 then 删除新结点(closed减1) else if 新结点即目标 then 输出并退出 end end until open>=closed{队列空}。 不同的问题，用广度优先搜索的基本算法是一样的。但数据库的表示方法、产生的结点是否符合条件和重复的判断上可以有不同的编程技巧，程序的运行效率也大不一样。 如8数码问题，用字符串表示布局，则初始布局为“283164705”，目标布局为“123804765”产生规则为: 空格上移:空格位置减3，即交换S和S-3的字符; ii 空格左移:空格位置减1，即交换S和S-1的字符; ii 空格右移:空格位置加1，即交换S和S+1的字符; ii 空格下移:空格位置加3，即交换S和S+3的字符。 ii 即:如空格编号为K，则交换S和S+(2*k-5)的字符。 ii 大家可以自己编写程序，比较一下效率。(请大家找一下用二维数组表示布局的优缺点，答案见key)。 深度优先搜索和广度优先搜索——广度优先搜索 ?17 [例题4-9翻币问题] [问题描述] 有N个硬币(N?6)正面朝上排成一排，每次将5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。 1、用计算机求最少需要翻几次。 2、找出部数最少的翻币方法，把翻币过程及次数打印出来(用O表示正面，,表示反面)。 [分析] 由于问题要求找出最少步骤，用广度优先搜索法来求解。 表面看，翻币的过程与正反面硬币的排列位置有关，但只要经过仔细分析会发现:实际上翻币过程仅与硬币正反面的个数有关，与它们的位置是无关的。例如下面两种状态: O , , , , , , ,和, , , , , , 都只要把5个正面朝上的硬币翻过来就达到了目标。因此在搜索过程中只需考虑当前状态正面朝上的个数。 又如，如果当前状态是: , , , , , , , , 翻第1，2，4，6，8个得到: O O , , O O , O 而翻第3，5，6，7，8个得到:, , , , , , , , 这两种翻法虽翻的硬币不同，但都是把原状态中4个反面朝上、1个正面朝上的硬币翻过来。结果状态不同，但都有5个硬币正面朝上，再翻一次就都可以达到目标。所以产生规则也只需考虑翻正面朝上的硬币的个数不同就可以了。 建立产生式系统。其中:综合数据库。综合数据库中每个记录设计为三项:父结点位置，当前状态中硬币正面朝上的个数，由父结点翻了几个正面朝上的硬币得到当前状态。数据库本身用队列形式。 产生规则如下: M:正面朝上的硬币个数 R:翻R个正面朝上的硬币: IF当前结点正面朝上的硬币个数M?R且反面朝上的个数?5—R THEN 子节点正面朝上的硬币的个数=(M-R)+(5-R) [源程序] {$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-} else begin { $ M 65521, 0, 655360} if l>0 then begin dec(l); st[h]:='o' end program ex4_9; end; var write('step',j-i:4,':');for h:=1 to n do n: integer; write(st[h]); a: array [1..8000,1..3] of integer; writeln; b: array [0..8000] of boolean; end; exit; procedure calc; end; var begin r, m: integer; fillchar(b,sizeof(b),true);b[n]:=false; open, closed: integer; open:=0;closed:=1;a[1,1]:=0;a[1,2]:=n;a[1,3]:=0; repeat procedure print; inc(open); m:=a[open, 2]; var for r:=0 to 5 do i, j, k,l, h: integer; if (m>=r) and (n-m>=5-r) and (b[m-r+5-r])then d : array [ 1..5000] of integer; begin st: array [ 1..5000] of char; inc(closed);b[m-r+5-r]:=false; begin a[closed,1]:=open; write ('step 0:');for i:=1 to n do write ('o'); a[closed, 2]:=m-r+5-r; writeln; a[closed,3]:=r; for i:=1 to n do st[i]:='o';j:=0; i:=closed; if a[closed,2]=0 then begin print;exit;end; repeat end; j:=j+1; d[j]:=i;i:=a [i,1]; until open>=closed; until i=0; writeln (' No answer!'); for i:=j-1 downto 1 do begin end; k:=a[d[i],3];l:=5-k; for h:=1 to n do begin if st[h]='o' then begin write('Input n(n>=6):'); readln(n); if k>0 then begin dec(k);st[h]:='*' end while n>=6 do begin end if n<6 then writeln ('Input error!' ) else calc; 深度优先搜索和广度优先搜索——广度优先搜索 ?18 write('Input n(n>=6):'); readln(n); end. end; 深度优先搜索和广度优先搜索——广度优先搜索 ?19 [例题4-10] [问题描述] 有两个无刻度标志的水壶，分别可装x升和y升(x、y为整数，x、y<-100)的水。设另有一水缸， 可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知x升壶为满壶，y升壶为空壶。问如 何通过倒水或灌水操作，用最少步数能在y升壶中量出z(z<-100)升的水来。 [分析] 本题要求最少步数，显然应采用广度优先搜索。 设A水壶内有a升水，B水壶内有b升水，则最多会有六种产生规则: (1)当a>0且b0且a0时，可以从水壶A倒a升水给水缸。这时水壶A内有0升水。 (4)当a0时，可以从水壶B倒b升水给水缸，水壶B内有0升水。 (6)当b0) and (j0) and (i0) and (bool^[0,j]) then evaluate (0,j); procedure print; if (j>0) and (bool^[i,0]) then evaluate (i,0); var if (i=closed; begin writeln('No answer !');readln j:=0;i:=closed; end; repeat j:=j+1;d[j]:=i;i:=data[i].father until i=0; for i:=j downto 1 do begin writeln('setp ',j-i:3,':',data[d[i]].a:5,data[d[i]].b:5); writeln('Input x, y, z:');readln(x, y, z);calc readln;halt; end. 深度优先搜索和广度优先搜索——广度优先搜索 ?20 [例题4-11房间问题] [问题描述] N 1 2 3 4 5 6 7 本图示意了一张建筑平面图，请根据输入数 据编程计算:该建筑中有多少个房间;最大的房 间有多大，拆除建筑中的某一堵墙，以形成一个W E 尽可能大的房间，指出该墙。该建筑分成m~n个 方块(m?50，n?50)，每个方块可有0,4堵墙(0S 表示无墙)。 输人数据:平面图以数字形式存储，用一个数字表示一个方块。 (1)文件开始是南北方向的方块数，其次是东西方向的方块数。 (2)后面的行中，每个方块中墙的特征由数字p来描述(0?p?15)。数字p是下面的可能取的数字之和:1(西墙west)2(北墙north)4(东墙east)8(南墙south)。 (3)建筑中至少有两个房间。例: 输入: 2 3 图示: 15 3 14 11 12 15 输出: 3 {该建筑有3个房间} 4 {最大的房间有4个方块} (1,1)(1,2) {拆除方块(1,1)(1,2)之间的墙可使房间尽可能的大} [分析] 该题要求根据建筑平面图中每个方块的墙的特征字得出:房间分布情况和求最佳拆墙方案。其中问题l的解是问题2的解的基础。因为只有计算出各房间拥有的方块数以及房间之间的隔墙情况，才能明确拆除那堵墙后可形成尽可能大的房间。 (1)明确每个方块中的设墙情况。程序从文件中输入m*n个0..15的数，每个数字描述了一个方块中墙的特征，即下面的可能取的数字之和:1(西墙west) 2(北墙north) 4(东墙east) 8(南墙muth) 将方块中墙的特征字转换成一个四位二进制数，每一位对应一个方向的墙。若DI位为l，表示该方块的I方向上有一堵墙;若DI位为0，表示该方块的I方向上无墙，该方块与I方向上的相邻块同属一个房间(0?I?3)。例如:(2，1)方块的墙的特征字为13，(11)=(1011)。即:(2，1)方块的墙的南面、102 北面、西面各有一堵墙。 DI位: D3位 D2位 D1位 D0位 1 0 1 1 方块号(2,1)的特征字为:(11) 10 方向: 南墙muth 东墙east 北墙north 西墙west 3 2 1 0 方向数(I): (2)求房间的分布。虽然求出了每个方块中的设墙情况，但由于除周边外的中间方块中，每堵墙被位于墙两面的方块各定义一次，因此还不能得出有多少个房间，每个房间拥有哪些方块。接下来的问题是将建筑平面划分为若干连通的闭区域，这种区域亦称面。面由墙围成，两两面之间无公共方块。对每一面着一种序号的颜色，这个颜色序号对应该面内方块所在的房间序号。对建筑平面图的着色方案勾勒出建筑中房间的分布情况，其颜色数即为房间总数。 从(1，1)方块出发，由上而下、从左至右搜索一个目前未着色的块(x，y)。运用广度优先搜索的方法求(x，y)所在的面，对该面着一种新颜色。运用一次广度优先搜索，可以确定一个面的所有方块，完成一个面着色。反复搜索，直到所有方块被着色时就求出了所有面。 (3)求最佳拆墙方案。有了房间的分布情况，求最佳拆墙方案便不难了，搜索最佳拆墙方案的算法如下: 设best为目前最大房间的面积，搜索前初始化为0。 按由上而下，由左至右搜索每一方块的相邻格;若此方块(i,j)与它在k(0?k?1)方向的相邻格(x,y)分属两个房间，且两个房间的面积和大于best。则best:= (i,j)所属房间面积+(x,y)所属房间面积。记下两个方块(i,j)和(x,y)。 (本例使用广度优先搜索，也可使用深度优先搜索但深度过大会造成堆栈溢处) [源程序] 主程序变量说明:n:平面图南北方向长度;m:平面图东西方向长度;total:房间总数;max:最大房间包含的方块数;x1,x2,x3,x4:拆除(x1,x2)与(x3,x4)之间的那堵墙;a(x,y,k):表示方块(x,y)在 深度优先搜索和广度优先搜索——广度优先搜索 ?21 k(0?k?3)方向上是否有墙，为true时为无墙。B(x,y):表示方块(x,y)所属房间号，0表示该方块没有被检查过;area(I):第I个房间的面积; program ex4_11; if j>m then begin const j:=1;inc(i) fn1='ex4_11.in'; end fn2='ex4_11.out'; until (i>n) or (b[i,j]=0); dig:array [0..3] of integer=(1,2,4,8); if i>n then exit; way:array[0..3,1..2]of integer=((0,-1),(-1,0),(0,1),(1,0)); fillchar(list,sizeof(list),0); var list[1,1]:=i; n,m:integer; list[1,2]:=j; total,max:integer; b[i,j]:=total; x1,x2,x3,x4:integer; area[total]:=1; a:array [1..50,1..50,0..3] of boolean; open:=0; b:array [1..50,1..50] of integer; closed:=1; area:array [1..2500] of integer; repeat list:array [1..2500,1..2] of integer; inc(open); x:=list[open,1]; procedure init; y:=list[open,2]; var for k:=0 to 3 do f:text; if a[x,y,k] and (b[x+way[k,1],y+way[k,2]]=0) then i,j,k,p:integer; begin begin inc(closed);inc(area[total]); assign(f,fn1);reset(f); list[closed,1]:=x+way[k,1]; readln(f,n,m); list[closed,2]:=y+way[k,2]; fillchar(a,sizeof(a),true); b[list[closed,1],list[closed,2]]:=total for i:=1 to n do end for j:=1 to m do begin until open>=closed read(f,p); until false for k:=3 downto 0 do end; if p>=dig[k] then begin a[i,j,k]:=false; procedure calc2; dec(p,dig[k]) var end i,j:integer; end; newmax:integer; close(f) end; procedure evaluate(k,l:integer); begin procedure print; if(b[i,j]<>b[k,1])and(area[b[i,j]]+area[b[k,1]]>newmax)then var begin f:text; newmax:=area[b[i,j]]+area[b[k,l]]; begin x1:=i;x2:=j;x3:=k;x4:=1 assign(f,fn2); end rewrite(f); end; writeln(f,total); writeln(f,max); begin dec(total);max:=0;newmax:=0; writeln(f,'(',x1,',',x2,')','(',x3,',',x4,')'); for i:=1 to total do close(f) if area[i]>max then max:=area[i]; end; for i:=1 to n-1 do for j:=1 to m do evaluate(i+1,j); procedure calc1; for i:=1 to n do var for j:=1 to m-1 do evaluate(i,j+1); i,j,k,x,y:integer; end; open,closed:integer; begin procedure main; fillchar(b,sizeof(b),0); begin fillchar(area,sizeof(area),0); calc1; total:=0;i:=1;j:=0; calc2 repeat end; inc(total); repeat begin inc(j); init; 深度优先搜索和广度优先搜索——广度优先搜索 ?22 main; print end. 深度优先搜索和广度优先搜索——深度优先搜索和广度优先搜索的对比 ?23 四、深度优先搜索和广度优先搜索的对比 深度优先搜索法的特点是: (1)从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题4—4、4—5、4—6;有的是未知的，如例题4—7、例题4—8，有的搜索深度是有限制的，但达到目标的深度是不定的。但也看到，无论问题的内容和性质以及求解要求如何不同， 一)和深度优先算法(二)中描述的算法结构，不但它们的程序结构都是相同的，即都是深度优先算法( 相同的仅仅是存储节点数据结构和产生规则以及输出要求。 (2)深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归形式较明显时，用递归方法设计的较好，它可以使得程序结构更简捷易懂。但当搜索深度较大时，如例题4—5、4—6，当数据量较大时，由于系统堆栈容量的限制，递归易产生溢出，用非递归方法设计比较好。 (3)深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的节点(即深度最大的节点)先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的节点的两种情况。而狭义的理解是，仅仅只保留全部产生节点的算法。本书取前一种广义的理解。不保留全部节点的算法属于一般的回溯算法范畴。保留全部节点的算法，实际上是在数据库中产生一个节点之间的搜索树，因此也属于图搜索算法的范畴。 (4)不保留全部节点的深度优先搜索法，由于把扩展完的节点从数据库中弹出删除，这样，?一般在数据库中存储的节点数就是深度值，因此它占用的空间较少。 所以，当搜索树的节点较多，用其他方法易产生内存溢出时，深度优先搜索法不失为一种有效的算法。 (5)从输出结果可看出，深度优先找到的第一个解并不一定是最优解。例如例题4—8得最优解COST=13，但第一个解却是COST=17。 如果要求出最优解的话，一种方法将是后面要介绍到的动态规划法，另一种方法是修改原算法:把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 广度优先搜索法的显著特点是: (1)在产生新的子节点时，深度越小的节点越先得到扩展，即先产生它的子节点。为使算法便于实现，存放节点的数据库一般用队列的结构。 (2)无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的。但数据库中每一节点内容、产生式规则，根据不同的问题，有不同的内容和结构。就是同一问题也可以有不同的表示方法。 (3)当节点到根节点的费用(有的数称为耗散值)和节点的深度成正比时，特别是当每一节点到根节点的费用等于深度时，用广度优先法得到的解是最优解。但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度(或广度)优先搜索方法:找到一个目标后，不是立即退出，而是记录下目标节点路径和费用。如果有多个目标节点，就加以比较，留下较优的节点。把所有可能的路径都搜索完后，才输出记录的最有路径。 (4)广度优先搜索算法，一般需存储产生的所有节点，占的存储空间要比深度优先大的多。因此程序设计中，必须考虑溢出和节省内存空间的问题。 (5)比较深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯操作，即人栈和出栈的操作，所以运行速度比深度优先搜索法要快些。 总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索法占内存较多但速度较快，在距离与深度成正比的情况下能较快地求出最优解。因此在选择用那种算法时，要综合考虑，决定取舍。