pascal 深搜
以树的搜索为例,深度优先搜索法是优先扩展尚未扩展的且具有最大深度的节点,广度优先搜索法是在扩展完第K层的节点以后才扩展K+1层的节点。
深度优先搜索法与前面讲的回溯法差不多。其主要的区别是,回溯法在求解过程中不保留完整的树结构,而深度优先搜索则记下完整的搜索树,搜索树起记录路径和状态判断的作用。为了减少存储空间,在深度优先搜索中,用标志的方法记录访问过的状态,这种处理方法使得深度优先搜索法与回溯法没什么区别了。在回溯法中,我们已分析了非递归的实现过程,在这里就只讨论深度优先的递归实现方法。
深度优先搜索的递归实现过程:
procedure dfs(i);
for i:=1 to r do
if 子节点 mr符合条件 then 产生的子节点mr入栈;
if 子节点mr是目标节点 then 输出
else dfs(i+1);
栈顶元素出栈(即删去mr);
endif;
endfor;
在讲解递推法时,我们讨论了用递推法解骑士游历问题,在这里我们看看如何用深度优先搜索法求解此题。
例1:骑士游历问题;
设有一个n*m的棋盘,在棋盘上任一点有一个中国象棋马,马走的规则为:1.马走日字 2.马只能向右走。当n,m输入之后,找出一条从左下到右上角的路径。例如:输入n=4,m=4,输出:路径的格式:(1,1)—>(2,3)- >(4,4),若不存在路径,则输出“NO”。
算法分析:我们以4*4的棋盘为例进行分析,用树形结构表示马走的所有过程,求从起点到终点的路径,实际上就是从根节点开始深度优先搜索这棵树。
马从(1,1)开始,按深度优先搜索法,走一步到达(2,3),判断是否到达终点,若没有,则继续向前走,在走一步到达(4,4),然后判断是否到达终点,若到达则退出,搜索过程结束。为了减少搜索次数,在马走的过程中,判断下一步所走的位置是否在棋盘上,如果不在棋盘上,则选择另一条路径再走。
程序如下:
const dx:array[1..4] of integer=(2,2,1,1);
dy:array[1..4] of integer=(1,-1,2,-2);
type map=record
x,y:integer;
end;
var I,n,m:integer; a:array[0..50] of map;
procedure dfs(i:integer);
var j:integer;
begin
for j:=1 to 4 do
if (a[i-1].x+dx[j]>0) and (a[i-1].x+dx[j]0) and (a[i-1].y+dy[j]<=m) then {判断是否在棋盘上}
begin a.x:=a[i-1].x+dx[j];
a.y:=a[i-1].y+dy[j];{入栈}
if (a.x=n) and (a.y=m) then
begin write(‘(‘,1,’,’,1,’)’);
for j:=2 to I do write(‘->(’,a[j].x,’,’,a[j].y,’)’);
halt;{输出结果并退出程序}
end;
dfs(i+1);{搜索下一步}
a.x:=0;a.j:=0; {出栈}
end;
end;
begin
a[1].x:=1;a[1].y:=1;
readln(n,m);
dfs(2);
writeln(‘no’);
end.
从上面的例子我们可以看出,深度优先搜索算法有两个特点:
1. 已产生的节点按深度排序,深度大的节点先得到扩展,即先产生它的子节点。
2. 深度大的节点是后产生的,但先得到扩展,即“后产生先扩展”,与栈的工作原理相同,因此用堆栈作为该算法的主要数据结构,存储产生的节点。
对于不同的问题,深度优先搜索算法基本上是一样的,但在具体处理方法和编程技巧上有都不相同,甚至有很大的差别。我们再看看另一个例子。
例题2:选数(NOIP2002pj)
问题描述:已知n个整数x1,x2,…xn,以及一个整数k(k<n)。从n个整数中任选k个整数相加, 可分别得到一系列的和。例如当n=4,k=3,4个整数分别为3,7,12,19时,可得全部的组合与他们的和为:3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。现在,要求求出你计算出和为素数共有多少种。例如上例,只有一种的和为素数:3+7+19=29。
[输入]:键盘输入格式为: n,k(1<=n<=20,k<n)
X1,x2,x3,…,xn (1<=xi<=5000000)
[输出]:屏幕输出格式为:一个整数(满足条件的种数)
[输入输出样例]:输入:4 3
3 7 12 19
输出:1
算法分析:本题是求从n个数中选k个数的组合,并使其和为素数。求解此题时,先用深度优先搜索法生成k个数的组合,再判断k个数的和是否为素数,若为素数则总数加1。
在程序实现过程中,用数组a存放输入a个数,用s表示k个数的和,ans表示和为素数的个数。为了避免不必要的搜索,程序对搜索过程进行了优化,限制搜索范围,在搜索过程dfs(i,m)中,参数m为第i个数的上限,下限为n-k+i。
源程序:
Var n,k,i:byte; ans,s:longint; a:array[1..20] of longint;
Procedure prime(s:longint);{判断k个数的和是否为素数}
Var i:integer;
Begin i:=2;
While (sqr(i)0) do inc(i);
If sqr(i)>s then inc(ans){若为素数则总数加1} end;
Procedure dfs(I,m:byte);{搜索第i个数}
Var j:byte;{j表示第i个数的位置}
Begin for j:=m to n-k+I do {枚举第i个数}
Begin inc(s,a[j]);{入栈}
If i=k then prime(s)
Else dfs(i+1,j+1);{继续搜索第i+1个数}
Dec(s,a[j]){出栈}
End
End;
Begin
Readln(n,k);
For i:=1 to n do read(a[j]);
Ans:=0;s:=0;
Dfs(1,1);
Writeln(ans);
End.
从上面的两个例子我们可以看出,用递归实现深度优化搜索比非递归更加方便。
在使用深度搜索法解题时,搜索的效率并不高,所以要重视对算法的优化,尽可能地减少搜索范围,提高程序的速度。
深搜和广搜的不同之处是在于搜索顺序的不同。深搜的实现类似于栈,每次选择栈顶元素去扩展,广搜则是利用了队列,先被扩展的的节点优先拿去扩展。搜索树的形态:深搜层数很多,广搜则是很宽。深搜适合找出所有方案,广搜则用来找出最佳方案。如果一道题你想不到怎么做,就可以考虑搜索。
深度搜索是数据结构中 树形结构的一种遍历方法 所谓遍历 就是一个一个查找 搜索就是遍历所有结点并且检查关键字是否匹配 树的深度搜索和广度搜索区别就是 深度搜索是按照深度优先原则 先笔直往下找子结点 找到那个结点后 又找这个结点的子结点。
与深搜对应的就是广度搜索,是按照以层为优先进行搜索 树都是一层一层的 找到一个结点后 又找这个结点的兄弟结点。
深度搜索与广度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复的节点,从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的一个,而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构.
[深度搜索]
<Var>
Open:Array[1..Max] of Node;(待扩展节点表)
Close:Array[1..Max] of Node;(已扩展节点表)
openL,closeL:Integer;(表的长度)
New-S:Tsituation;(新状态)
<Init>
Open<-0; Close<-0;
OpenL<-1;CloseL<-0;
Open[1].Situation<- 初始状态;
Open[1].Level<-1;
Open[1].Last<-0;
<Main Program>
While (openL>0) and (closeL<Max) and (openL<Max) do
Begin
closeL:=closeL+1;
Close[closeL]:=Open[openL];
openL:=openL-1;
For I:=1 to TotalExpendMethod do(扩展一层子节点)
Begin
New-S:=ExpendNode(Close[closeL].Situation,I);
If Not (New-S in List) then
(扩展出的节点从未出现过)
Begin
openL:=openL+1;
Open[openL].Situation:=New-S;
Open[openL].Level:=Close[closeL].Level+1;
Open[openL].Last:=closeL;
End-If
End-For;
End;
范例:迷宫问题,求解最短路径和可通路径。
评价:深度搜索多用于只要求解,并且解答树中的重复节点较多并且重复较难判断时使用,但往往可以用分支定界或回溯算法代替。
希望这个回答对你有帮助!~
一、深度优先搜索的过程
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,就沿此边继续搜索下去。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被发现为止。
这种在搜索过程中,深度大的结点先进行扩展的算法,我们就称它为深度优先搜索法。英语称之为Depth-First-Search,简称为DFS法。
二、深度优先搜索法有两个显著特点
(1)对已产生的结点按深度排序存储,深度大的先得到扩展,即先产生它的子结点;
(2)深度大的结点是后产生的,但先得到扩展,即“后产生先扩展”。因此该算法应该用堆栈作为的主要数据结构存储产生的结点:先把产生的数入栈,然后产生栈顶(即深度最大的结点)的子结点。子结点产生完后,出栈(pop)再产生栈顶的子结点。
三、深度优先搜索算法描述
程序实现有两种方式--递归与非递归。
递归
递归过程为:
Procedure DEF-GO(step)
for i:=1 to max do
if 子结点符合条件 then
产生新的子结点入栈;
if 子结点是目标结点 then 输出
else DEF-GO(step+1);
栈顶结点出栈;
endif;
enddo;
主程序为:
Program DFS;
初始状态入栈;
DEF-GO(1);
非递归
Program DEF(step);
step:=0;
repeat
step:=step+1;
j:=0;p:=false
repeat
j:=j+1;
if 结点符合条件 then
产生子结点入栈;
if 子结点是目标结点 then 输出
else p:=true;
else
if j>=max then 回溯 p:=false;
endif;
until p=true;
until step=0;
回溯过程如下:
Procedure BACK;
step:=step-1;
if step>0 then 栈顶结点出栈
else p:=true;
两种方式本质上是等价,但两者也时有区别的。
1. 递归方式实现简单,非递归方式较之比较复杂;
2. 递归方式需要利用栈空间,如果搜索量过大的话,可能造成栈溢出,所以在栈空间无法满足的情况下,选用非递归实现方式较好。
深搜就是深度优先搜索,从名字上可以看出,深度——由浅入深,为标准进行的搜索,就像是你从你爷爷辈开始点人头,每次都要数到辈数最小,数到后又像上辈数,如果一个上辈有下辈的话,就又数到辈数最小的。
至于深搜 额....
就是 用递归调用加回溯
基本格式大概是这样的
procedure dfs(x:longint);
begin
if 这里写跳出这个递归的条件 满足就是搜到了要找的
if 这里写你的程序的应满足条件
then ...
dfs(); 从这里开始继续向下搜索
上个if里 你对某些变量做了修改 但他不一定正确 所以你应在这里写一个回溯
即把then里的东西弄回去 可以理解成返回上一种情况(dfs最重要的部分)
end;
不大好解释..
但说白了就是有点特殊的枚举 枚举方向与别的枚举不大一样
建议楼主去翻翻竞赛书 上网上找个ppt看看
田侵乐泡: 深度优先搜索一、概念深度优先搜索是在图运算中最常用的一种算法.它遵循的搜索策略是尽可能“深”地搜索图,即沿纵深方向搜索图.在深度优先搜索中,对于最新发...
番禺区14788422287: pascal 深搜 - ?
田侵乐泡: 深度搜索是数据结构中 树形结构的一种遍历方法 所谓遍历 就是一个一个查找 搜索就是遍历所有结点并且检查关键字是否匹配 树的深度搜索和广度搜索区别就是 深度搜索是按照深度优先原则 先笔直往下找子结点 找到那个结点后 又找这个结点的子结点.与深搜对应的就是广度搜索,是按照以层为优先进行搜索 树都是一层一层的 找到一个结点后 又找这个结点的兄弟结点.
番禺区14788422287: pascal深搜 - ?
田侵乐泡: 深度优先搜索我也是深有其感啊,当年也是就结了很久 以下是我的看法和我的框架,你看看能不能帮到你 深度优先搜索法有两个显著特点 (1)对已产生的结点按深度排序存储,深度大的先得到扩展,即先产生它的子结点; (2)深度大的结点...
番禺区14788422287: 不知道怎么学好pascal 搜刮?
田侵乐泡: 1楼上说得好,记住格局:深搜:procedure dfs(k:type); varbegin if 是目标 then 记录并回溯 else for i:=1 to maxr{上界} do if 相符前提 then begin 处理; dfs(下一结点); end; end;例子:八皇后问题; i:type;{轮回变量不克不及是全局变量!}...
番禺区14788422287: 一个关于广搜和深搜的问题(pascal) - ?
田侵乐泡: 广搜得到的往往是最优值,因为它是按照节点深度递增的次序访问的.但由于需要记录当前深度的所有节点,因而需要的空间开销大. 深搜只需要记录当前路径上的节点,因而开销较小,但没有广搜“递增”的次序,无法高效地求出最优解,因此一般用作求所有解. 只需要遍历所有点或所有情况的时候,两者都可以. 有种折中的方法 叫做迭代加深. 它限制每次搜索的深度,如果无解再增加允许搜索的深度,逐步逼近最优解,不会占用广搜那样太大空间,也不至于像深搜那样一路走到死胡同.加: 如果选用广搜,则节点数最多有20!≈2*10^18个节点,则很难存储状态,而且本题只要求求出任意解,并非最优解,因此选用深搜
番禺区14788422287: 求pascal迷宫路径广搜和深搜程序!(详细问题请看10.153.3.180的problem)这是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒... - ?
田侵乐泡:[答案] const dx:array[1..8] of integer=(0,1,1,1,0,-1,-1,-1);// 行坐标增量 dy:array[1..8] of integer=(1,1,0,-1,-1,-1,0,1);// 列坐标增量var n,m:integer;// 迷宫长和宽 maze:array[1..100,1..100] of integer;//...
番禺区14788422287: pascal 输出组合 - ?
田侵乐泡: 就是深搜 主要代码 procedure search(k:longint)://第一次从1开始 begin if k>m then begin print; exit; end; for i:=1 to n doif i in s then //s表示的是集合,你首先要把数字1..n加入集合中 begin s:=s-[i];//搜索过了就不能在搜索这个了 a[k]:=i;//记录方案,最后输出直接从1循环到m输出a就好了 search(k+1); s:=s+[i];//回溯 end; end;
番禺区14788422287: pascal马拦过河卒 - ?
田侵乐泡: 老题目了 程序我就不自己写了,我自己写解释 program E1_1; {knight} const dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2); dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1); 这个就是传说中的增量矩阵.其实也没那么神秘,就是一张表,有8种变化状态...
番禺区14788422287: 谁有素数环PASCAL程序 - ?
田侵乐泡: 这是一个搜索问题,层数为20,在深搜可以接受的范围之内 思路是,先确定第一个元素为1 然后依次往后推,每个元素都要满足和前一个的和为素数 关于这个你可以先做一个初始化 f[i,j] of boolean 表示i后面能不能接j(这个在下面那个程序里没...
番禺区14788422287: 记忆化搜索程序pascal框架 - ?
田侵乐泡: 1. 记忆化深度优先搜索 const nonsense=-1; {这个值可以随意定义,表示一个状态的最优值未知} var …… {全局变量定义} function work(s:statetype):longint; var …… {局部变量定义} begin if opt[s]nonsense then begin work:=opt[s]; exit; end; {如...