搜索与回朔算法 搜索与回朔是计算机解题中常用的算法，很多无法根据某种确定的计算法则来求解的问题，可以利用搜索与回朔方法求解。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索的过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后再继续向前探索，如此反复进行，直到得到解或证明无解为止。

Presentation on theme: "搜索与回朔算法 搜索与回朔是计算机解题中常用的算法，很多无法根据某种确定的计算法则来求解的问题，可以利用搜索与回朔方法求解。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索的过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后再继续向前探索，如此反复进行，直到得到解或证明无解为止。"— Presentation transcript:

1 搜索与回朔算法 搜索与回朔是计算机解题中常用的算法，很多无法根据某种确定的计算法则来求解的问题，可以利用搜索与回朔方法求解。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索的过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后再继续向前探索，如此反复进行，直到得到解或证明无解为止。 如迷宫问题，先可以随意选择一个前进方向，一步步向前探索，如果遇到死路了，先看看还有没有其它路可以走；如果没有，则返回一步，再看其它方向是否还有路可走。如果有路可走，就按原则不断往前探索，直到找到新的出路或返回原来入口处为止。这就是典型的边搜索边回朔的方法。

2 递归回朔算法框架 Procedure search(k:integer,参数表)； begin if 到目的地 then 输出解
else for i:=1 to 算符种数 do if 满足条件 then 保存结果； search(k+1,参数表); {向前继续探索} 回朔； end;

3 例1 素数环问题 素数环：把1-20这20个数摆成一个环，要求相邻两个数的和是一个素数。 【算法分析】
procedure search(t:integer); var i:integer; begin if t>20 then if pd(a[20],a[1]) then print; exit; end; for i:=1 to 20 do if pd(a[t-1],i) and b[i] then a[t]:=i; b[i]:=false; search(t+1); b[i]:=true; fillchar(b,sizeof(b),true);total:=0; search(1); write(total); end. 素数环：把1-20这20个数摆成一个环，要求相邻两个数的和是一个素数。 【算法分析】 这是一道回朔的题目。从1开始，每个空位有20种可能，只要填进去的数合法，即与前面数不同、与前面相邻数和为一个素数。注意最后还要判定第20个数和第一个数的和是否为素数。 【算法程序】 program sushuhuan; var a:array[0..20] of integer; b:array[0..20] of boolean; total:integer; function pd(x,y:integer):boolean; begin i:=x+y; pd:=true; for j:=2 to trunc((sqrt(i) ) do if I mod j=0 then pd:=false; end;

4 例2 n个整数从中任意取r个数的排列 【参考程序】 Procedure search(k:integer); Program pailie;
type se=set of ; var s:se; n,r,num:integer; a:array[1..100] of integer; procedure print; var i:integer; begin inc(num); for i:=1 to r do write(a[i],’ ‘); writeln; end; Procedure search(k:integer); var i:integer; begin if k>r then begin print;exit;end; for i:=1 to n do if i in s then a[k]:=i; s:=s-[i]; search(k+1); s:=s+[i]; end; readln(n,r); s:=[1..n];num:=0; search(1); writeln(num);

5 1、任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。如n=7，共有14种拆分方法。
上机练习 【参考程序】 Procedure search(s,t:integer); var i:integer; begin if s<=0 then begin print(t-1);exit;end; for i:=1 to s do if (a[t-1]<=i) and(i<n) then a[t]:=i; s:=s-i; search(s,t+1); s:=s+a[t]; end; 1、任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。如n=7，共有14种拆分方法。 7= 7= 7= 7= 7= 7= 7=1+1+5 7= 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 Total=14

6 【问题描述】要在国际象棋棋牌中放八个皇后，使任意两个 皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子）
2、八皇后问题： 【问题描述】要在国际象棋棋牌中放八个皇后，使任意两个 皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子） 放置第i个皇后的算法为： Procedure search（i:integer）； Begin if i>8 then begin 输出； exit； end； for 第i行皇后的位置 =1 to 8 do if 满足条件 begin 放置第i个皇后； 对放置皇后的位置进行标记； search（i+1）； 对放置的皇后的位置释放标记，尝试下一个位置是否可行； end； End；

7 【算法分析】 显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后，可以从矩阵的特点上找到规律。从图可验证：如果在同一行，则行号相同；如果再同一列，则列号；如果同在/斜线上，则行列值之和相同；如果同在\斜线上，则行列值之差相同。 ★建立标志数组b[1..8]控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等。 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

8 End. 【参考程序】 Procedure search(t:integer); Program ex5_4; var j:integer;
var a:array[1..8] of integer; b:array[ ] of boolean; c:array[ ] of boolean; d:array[ ] of boolean; sum:integer; Procedure print; var i:integer; Begin inc(sum); write(‘sum=’,sum); for i:=1 to 8 do write(a[i]:4); end; Procedure search(t:integer); var j:integer; Begin if t>8 then begin print; exit;end; for j:=1 to 8 do if b[j] and c[t+j] and d[t-j] then begin a[t]:=j; b[j]:=false; c[t+j]:=false; d[t-j]:=false; search(t+1); b[j]:=true; c[t+j]:=true; d[t-j]:=true; end; end; Begin fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); fillchar(d,sizeof(d),true); sum:=0; search(1); writeln(‘the total:’,sum); End.

9 3、马的遍历问题； 【问题描述】有一个半张中国象棋棋盘。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。编程将所经过路线打印出来。 【输出】 0，02，13，31，43，52，74，8 1 2 3 4 5 6 7 8 马

10 4、分配工作； 【问题描述】设有A、B、C、D、E五人从事五项工作，每人只能从事一项，他们的效益如图。每人选择五项工作中一项，在各种选择的组合中，找到效益最高的一种组合输出。 【 输出】A 5 B 3…… Job1 job2 job3 job4 job5 A B C D E

11 5、选书； 【问题描述】设有A、B、C、D、E五本书，分给参加信息奥赛的张、王、刘、孙、李五位同学。老师事先先让每人把自己喜好的书填写表格如下。编程输出让每一个同学都满意的结果。 【输出】zhang 3 wang …… A B C D E 张 王 刘 孙 李 Y Y Y Y Y Y Y Y Y Y

12 6、跳马问题； 【问题描述】在5*5的棋盘上，有一只马从（1，1）点出发，按日字跳马，它可以朝8个方向跳，但不允许出界或跳过已经跳过的格子，要求跳遍整个棋盘。 【输出】输出前5个方案及总方案数。 方案格式示例：

13 7、集装箱问题 【问题描述】有n个集装箱要装上一艘载重量为C的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在不受装载体积的情况下，将尽可能重的集装箱装上船。 【输入】 【输出】

14 【输入】 7 10 {n,m居民数和仇敌对数} 【输出】
8、部落卫队 【问题描述】 原始部落中的居民为了争夺有限资源，经常发生冲突哦，几乎每个居民都有仇敌。部落族长为了组织一支卫队，希望从部落居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。题目给出仇敌关系，编程输出组成卫队的最佳方案。 【输入】 {n,m居民数和仇敌对数} 【输出】 {1表示居民在卫队中}

15 9、最佳调度问题 【问题描述】 假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。对任意给定的整数n和k，以及完成任务i需要的时间ti，i=1---n，试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间按最早。 【输入】 {n和k，整数} 【输出】 17

16 10、图的m着色问题 【问题描述】 给定无向连通图G和m种不同颜色。用这些颜色为图G各顶点着色，每个顶点着一种色，如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。 【输入】 {n，k，m表示图G有n个顶点、k条边、m种颜色} 1 2 【输出】 48 1 4 2 3 2 4 2 5 3 4 4 5