深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。
深度优先搜索基本算法如下{递归算法}：PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END;
宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。
宽度优先搜索基本算法如下：list:=source; {加入初始结点，list为待扩展结点的表}
head:=0;{队首指针}
foot:=1;{队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数 DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list:=nw;
list.father:=head;
IF list=目标结点 THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}
【八数码问题】
九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数。如下图
初始状态
2 8 3
1 6 4
7 5
目标状态
1 2 3
8 6 4
7 5
【算法分析】
解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化。
这个问题也可以推广到流行的拼图游戏。
【具体步骤】
一、确定问题规模（考虑搜索的时间代价）
二、确定产生式规则（如果规则太多，则时间代价会很大）
三、套用经典宽度搜索框架写程序
【参考样例】
【输入】8no.in
2 0 3
1 4 6
7 5 8
1 2 3
4 5 6
7 8 0
【输出】8no.out
5 {下面为移动步骤}
2 0 3
1 4 6
7 5 8
0 2 3
1 4 6
7 5 8
1 2 3
0 4 6
7 5 8
1 2 3
4 0 6
7 5 8
1 2 3
4 5 6
7 0 8
1 2 3
4 5 6
7 8 0
【参考程序】
[ 本帖最后由 kon3155 于 2009-2-25 11:29 编辑 ]
【n皇后问题】
一个n×n（1<=n<=100）的国际象棋棋盘上放置n个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一斜线上，试问共有多少种摆法？
【输入】nqueen.in
n
【输出】nqueen.out
方案数
【算法分析】
【参考样例】
【输入】nqueen.in
8
【输出】nqueen.out
92
【参考程序】
[ 本帖最后由 kon3155 于 2009-2-25 11:33 编辑 ]
枚举法习题
【练习1】将1~9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应这样填数。如下图所示。
【练习2】一根长29cm的尺子，只允许在上面刻七个刻度，要能用它量出1~29cm的各种长度。试问这刻度应该怎么选择？
【练习3】有4个学生，上地理课时提出我国四大淡水湖的排序如下。
甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三；
乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三；
丙：红泽湖最小，洞庭湖第三；
丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三；
对于各个湖泊应处的地位，每个人只说对了一个。
根据以上情况，编一个程序，让计算机判断各个湖泊应处在第几位。
【聪明的打字员】
阿兰是某机密部门的打字员，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用：
Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变；
Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变；
Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按Up之后，该处的数字变为3；如果该处数字为9，则按Up之后，数字不变，光标位置也不变；
Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按Down之后，数字不变，光标位置也不变；
Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动；
Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。
当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标出现随机位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。
现在，阿兰有一个6位的数字密码，请编写一个程序，求出录入一个密码需要的最少的击键次数。
【输入文件】clever.in
两行，第一行为初始密码，空格后为光标位置（1-6），第二行为要输入的密码值。
【输出文件】clever.out
仅一行，为打出密码的最少击键次数。
【样例数据】
【输入】
123456 1
623453
【输出】
3
【参考程序1（盲目搜索）】
【参考程序2（结构优化）】
[ 本帖最后由 kon3155 于 2009-2-25 11:31 编辑 ]
【量水问题】
有两个无刻度的量杯A和B，其容积分别为m升和n升(m>n)，现在允许用量杯从水缸里取水或将水倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(k<n<m)所需的最少操作步数。 (每一个取水或倒水都算一个操作步数)
【输入文件】ls.in
仅一行，三个数，分别为m,n,k。
【输出文件】ls.out
仅一行，为最少步数。
【样例数据】
【输入】
4 3 2
【输出】
6
【提示:可以利用宽度搜索求解】
【参考程序】
[ 本帖最后由 kon3155 于 2009-2-25 11:32 编辑 ]
【染色问题】
给定一张无向图，要求对图进行染色，有边相连的点不能染同一种颜色。求最少需要几种颜色可以染完。
【输入文件】color.in
第一行n,m表示图的点数和边数（n≤10）。
以下m行每行两个整数，表示一条边。
【输出文件】color.out
最少需要的颜色数。
【样例数据】
【输入】
5 5
1 2
2 3
3 4
4 5
5 1
【输出】
3
【跳马问题】
在5×5格的棋盘上,从一角出发,按日字跳马,要求不重复地跳经所有方格。求出符合要求的所有跳马方案。
【参考程序】 var
a:array of integer; {记每一步走在棋盘的哪一格}
b:array of boolean; {棋盘的每一格有没有被走过}
u,v:array of integer; {8个方向上的x,y增量}
i,j,num:integer;
procedure print; {打印方案}
var
k,kk:integer;
begin
num:=num+1; {统计总方案}
if num<=5 then {打印出前5种方案}
begin
for k:=1 to 5 do {打印本次方案}
begin
for kk:=1 to 5 do write(a:5);
writeln;
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; y:=j+v ; {走此方向，得到的新坐标}
if (x<=5) and (x>=1) and (y<=5) and (y>=1)and b then
{如果新坐标在棋盘上，并且这一格可以走}
begin
b:=false;
a:=n;
try(x,y,n+1); {从(x,y)去搜下一步该如何走}
b:=true;
a:=0;
end;
end;
end;
begin
u:=1; v:=-2; {8个方向的x,y增量}
u:=2; v:=-1;
u:=2; v:=1;
u:=1; v:=2;
u:=-1; v:=2;
u:=-2; v:=1;
u:=-2; v:=-1;
u:=-1; v:=-2;
for i:=1 to 5 do {初始化}
for j:=1 to 5 do
begin
a:=0;
b:=true;
end;
a:=1; b:=false; {从(1,1)第一步开始走}
try(1,1,2); {从(1,1)开始搜第2步该怎样走}
writeln(num); {输出总方案(304)}
end.
跳马问题与八皇后问题都属于典型的回溯法，回溯法有一种固定的思维与书写格式
[ 本帖最后由 kon3155 于 2009-2-25 11:55 编辑 ]
转自：http://blogger.org.cn/blog/more.asp?name=njucs&id=3772
计算24点问题的详细解析
文章收藏,软件技术
既瑜 发表于 2005-3-16 17:11:14
【问题描述】
80年代全世界流行一种数字游戏，在中国我们把这种游戏称为“24点”。现在我们
把这个有趣的游戏推广一下：您作为游戏者将得到6个不同的自然数作为操作数，
以及另外一个自然数作为理想目标数，而您的任务是对这6个操作数进行适当的算
术运算，要求运算结果小于或等于理想目标数，并且我们希望所得结果是最优的，
即结果要最接近理想目标数。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：
所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是
合法的，2*（2/4）是不合法的）
下面我们给出一个游戏的具体例子：
若给出的6个操作数是：1，2，3，4，7和25，理想目标数是573；
则最优结果是573：（（（4*25-1）*2）-7）*3。
【输入】：
输入文件名为game.in。输入文件仅一行，包含7个整数，前6个整数Mi,
1<=Mi<=100，表示操作数，最后一个整数T, 1<=T<=1000,表示理想目标数。
【输出】：
输出文件名为game.out。输出文件有两行，第一行仅一个整数，表示您的程序计算
得到的最优结果；第二行是一个表达式，即您得到的最优结果的运算方案。
输入输出示例：
输入文件
1 2 3 4 7 25 573
输出文件
573
((4*25-1)*2)-7)*3
【算法分析】
首先我们要对这个问题进行数学抽象。
定义1：对于有理数组成的多重集合S ， f(S) 定义如下：
如果 S 是空集或只包含一个元素，则 f(S)=S ；否则
f(S)=∪ f( ( S-{r1, r2}) ∪ {r} ) ，对于每一个 r=r1+r2 , r1-r2 , r1×r2
，r1÷r2(r2≠0)，且r1, r2取遍 S 中所有元素的组成的二元组。
定义1说明：要计算集合S中的元素通过四则混合运算所能得到的所有值，我们只需
要任取 S 中的两个元素 r1 , r2 ，分别计算 r1 , r2 的加减乘除运算，然后用
所得的结果与 S 中剩下的其他数字进行四则混合运算。只要取遍所有的 r1 ,
r2 ，最后得到的所有结果的并集就是 S 中的元素通过四则混合运算所能得到的所
有值的集合。
根据上述定义，在本问题中，集合 S 就是由输入中给定的6个正整数组成的集合，
题目所求就是找出 f(S) 中小于或等于目标数的最大数。
定义2：给定两个多重集合 S1 , S2，定义
comb( S1, S2 ) = ∪ { r1+r2 , r1-r2, r1×r2, r1÷r2(r2≠0) }
(1.1)
其中 ( r1 , r2 ) ∈ S1 × S2。
定义2实际上定义了两个集合中的元素两两进行加减乘除运算所能得到的结果集合
。
定理1：对于有理数组成的多重集合 S ，如果 S 至少有两个元素，则
f(S)=∪ comb( f(S1), f(S - S1) ) (1.2)
其中 S1 取遍 S 的所有非空真子集。
定理1的含义是：要计算 S 中的元素通过四则混合运算所能得到的所有值，可以先
将 S 分解为两个子集 S1 和 S- S1 ，分别计算 S1 和 S-S1 中的元素进行四则混
合运算所能得到的结果集合，即 f(S1) 和 f(S-S1) ，然后对这两个集合中的元素
进行加减乘除运算，即 comb( f(S1), f(S-S1) ) ，最后得到的所有集合的并集就
是 f(S) 。限于篇幅，定理1的正确性易用数学归纳法证明。
定义1和定理1实际上分别给出了计算f(S)的两种不同的方法。根据定义1，可以递
归地计算f(S) ，其算法伪代码如下：
算法1
function f(S)
begin
1.if |S| < 2
2. then return S
3. else begin
4. T ← Φ
5. for each (r1, r2) in S do
6. begin
7. r ← r1 + r2;
8. T ← T + f(S – {r1, r2} + {r});
9. r ← r1 - r2;
10. T ← T + f(S – {r1, r2} + {r});
11. r ← r1 * r2;
12. T ← T + f(S – {r1, r2} + {r});
13. if (r2 <> 0) and (r1 mod r2 = 0) then
14. begin
15. r ← r1 / r2;
16. T ← T + f(S – {r1, r2} + {r});
17. end
18. end
19. return T;
20. end
end
上述伪代码中使用了+, - 来分别表示集合的并和差运算。算法1每次选择两个数字
进行某种运算，然后将结果与剩下的数字递归地进行运算，最后求得所有数字进行
四则混合运算的结果。当然，在具体实现该算法的过程中有很多可以优化的地方，
比如根据加法交换律， a+b+c=a+c+b ，因此我们可以规定：如果上一层递归作了
加法运算，这一层仅当满足当前的操作数大于上一层的两个操作数的时候才进行加
法运算，以确保 a+b+c 这样的式子中的操作数总是从小到大排列，这样就可以避
免重复进行等价的加法计算。类似地我们可以对乘法也作此规定。在进行减法的时
候，我们可以规定只能计算大数减小数，因为最后所需计算得到的目标数是一个正
数，如果计算过程中出现负数，肯定有另外一个较大的正数与其作加法或者有另外
一个负数与其做乘除法以消除负号。因此我们总可以调整运算次序使得四则混合运
算的每一步的中间结果都是正数。在作除法的时候，因为题目规定中间结果只能是
整数，所以也只需要用大数除小数，且仅当能除尽的时候才进行除法。对于本题而
言，初始的集合 S 中一共有6个操作数，每次递归都可以合并两个操作数，所以递
归到第5层的时候集合 S 中只剩下一个数，这个数就是原先的6个操作数进行四则
混合运算所能得到的结果。本题只要求最接近目标值的结果，所以实现上述算法的
时候可以只记录当前最优的结果。对于本题也可以利用递归回溯构造出所有的四则
混合运算的语法树，但本质上与算法1是没有区别的。
定理1则给出了另一种计算f(S)的方法。我们当然也可以根据(1.2)式直接地递归计
算f(S)，但那样的话会有很多冗余计算。例如对于S={1,2,3,4}，
f(S) = comb( f({ 1 }), f({ 2,3,4}) )∪ ... ∪ comb( f({ 1,2 }), f({
3,4 }) ) ∪ ...;
计算f(S)的时候需要计算 f({ 2,3,4 })和f({ 3,4 }) ，又因为
f({2,3,4}) = comb(f({ 2 }), f({3,4})) ∪ ...;
在计算 f({ 2,3,4}) 的时候又要重复地计算 f({ 3,4 }) ，这就产生了冗余的计
算。这种情况下直接地递归就不适用。必须按照一定的顺序，递推地进行计算。这
种将递归改为递推，以解决冗余的算法设计策略，就叫做动态规划。
下面我们具体阐述一下该算法的步骤。设初始时集合 S 中的 n 个数字分别为
x, x,...,x ，我们可以用一个二进制数k来表示S 的子集 S ，x ∈S
当且仅当二进制数k的第i位为1。于是我们用一个数组 F
就可以保存函数f对于S的所有子集的函数值（注意，函数f的函数值是一个集合）
，且 F=f(S) 就是所求。
算法2
1.for i ← 0 to 2^n-1
2. do F←Φ;
3.for i ← 0 to n-1
4. do F← {x};
5.for x ← 1 to 2^n-1 do
6.begin
7. for i ← 1to x-1 do
8. begin
9. if x∧i=i then
10. begin
11. j ← x – i;
12. if i < j
13. then F ← F + comp(F,F);
14. end;
15. end;
16. end;
17. return F[ 2 n ?1] ;
上述伪代码中使用了+表示集合的并运算。算法2的第1～2行将F中所有的集合初始
化为空；第3～4行中 2^i 即表示只包含元素 x的子集（因为 2^i 只有第 i 位
上是1），根据定义1我们知道当集合中只有一个元素的时候函数 f 的函数值就是
那唯一的元素组成的集合，所以3～4行计算出了函数 f 对于所有只有一个元素的
子集的函数值；第5～17行按照一定的顺序计算函数 f 对于 S 的所有子集的函数
值。对于 S 的两个子集 S 和 S ， S真包含于S的充要条件是 x∧
i=i ，这里 ∧ 是按位进行与操作，而 x∧i=i 的必要条件是 i<x 。因而第7~15
行的循环将S拆成两个子集S和S，并在第13行根据(1.2)式计算所有的
comp( f(S),f(S) ) 的并。第12行的判断语句是为了优化算法的效率，因为
将 S拆成两个子集 S和 S的过程是对称的，所以我们对于 comp(
f(S),f(S) ) 和 comp( f(S),f(S) ) 两者只取一个进行计算。下面
是函数comp的伪代码：
算法3
function comp(S1, S2)
1.T ← Φ ;
2.for each x in S1 do
3.begin
4. for each y in S2 do
5. begin
6. T ← T + {(x + y)};
7. T ← T + {(x * y)};
8. if x > y then
9. begin
10. T ← T + {(x – y)};
11. if (y <> 0) and (x mod y = 0)
12. then T ← T + {(x / y)};
13. end
14. else begin
15. T ← T + {(y – x)};
16. if (x <> 0) and (y mod x = 0)
17. then T ← T + {(y / x)};
18. end;
19. end;
20. end;
21. return T;
comp在进行计算的时候不考虑参数集合S1和S2的顺序，进行减法的时候始终用大
数减小数，这样保证运算过程中不出现负数（这样做的理由前文已经阐明）。
因为我们只关心最后的f(S)中最接近目标值的数字，并且题目只要求求出任何一组
最优解，所以算法2中的集合不需要是多重集合，只要是一般的集合即可。换句话
说，集合F中所有的元素互不相同，重复出现元素的我们只保留其中一个。这样
可以大大减少计算中的冗余。做了这样的处理后，算法2的效率至少不会比算法1差
，因为算法1中所能采用的主要剪枝手段是排除等价的表达式，但因为等价的两个
表达式计算出的结果也一定相同，而算法2排除了所有结果相同的表达式，所以算
法2的效率至少不会比算法1差，算法2中所进行的计算基本上都是得到最优解所必
需的计算。
在实现算法2的过程中，集合可以用一个链表加上一个哈希表来实现。链表中保存
每个表达式及其值，哈希表用来记录该集合中是否存在某个特定值的表达式。当向
集合中插入一个新的表达式的时候，首先检查哈希表，看看该集合是否已经有和新
表达式值相同的表达式，如果有的话就不插入，否则将新的表达式追加到链表末尾
。采用这种数据结构，可以在常数时间内完成集合的插入和删除操作。利用链表，
集合的并操作也很容易高效地实现。
在实现算法2的过程中，可以不必保存表达式的字符串，只需要记录下当前的值是
由哪两个集合中的元素通过哪种运算得到的，最后再根据最优解递归地计算出最优
解的表达式。这样只在最后构造最优解的表达式时才进行字符串操作，程序运行效
率能提高7～8倍左右。另外，在comb函数中进行乘法运算的时候要注意考虑运算结
果超出整数范围的情况。
经过以上优化，利用算法2实现的程序对于100个随机生成的测试数据总共只需要5
秒左右就可以出解，平均每个数据只需要50毫秒即可出解（测试用的CPU为赛扬
1GB）。这样的效率已经非常令人满意了。
【参考程序】见楼下