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; {如...
