几近万能的算法

1、几近万能的算法1知识准备1、分阶段决策2、状态3、方案4、决策2了解深度优先搜索法1、degree first serch2、在每个阶段的决策时，采取能深则深的原则试探所有可行的方案，一旦深入一层则保存当前操作引起的状态3、一旦试探失败，为了摆脱当前失败状态，采取回到上一阶段尝试下一方案的策略（回溯策略）；或者在求解所有解时，求得一个解后，回溯到上一阶段尝试下一方案，以求解下一个解4、在各个阶段尝试方案时，采取的是穷举的思想3引题1 【例1】采摘果子。有如下图所示的一棵果树，图中的结点表示树上的果子，结点左边的数字表示结点的编号，里面的权值就是果子的重量，现在果农想把某条树枝的果子全部采摘下来

2、，并保证被采摘果子的总重量是所有树枝中最大的。问，这条树枝上所有果子的总重量是多少？45 输入文件fruit.in共包含了n2行，其中n表示图中果子的个数，第一行的一个整数表示果树中果子的数量，第2n行表示各果子之间的连接关系（用邻接表表示），最后一行依次表示了各个果子自身的重量，用n个用空格隔开的整数。输出文件fruit.out只包含一个整数，表示某条树枝上所有果子的重量（是所有树枝中果子总重量最大的那根树枝）。6fruit.in181 2 3 4 02 5 6 03 7 8 04 9 10 05 11 12 06 13 07 14 15 08 09 010 16 011 17 012 01

3、3 014 015 016 017 18 018 02 5 30 6 3 22 29 28 10 11 4 9 24 33 8 21 7 1fruit.out9471、分析样例数据2、样例数据如何来求解3、穷举什么？4、穷举实现的方式81、A1,3=3表示1号结点的第2个儿子是3号结点，AI,1表示结点本身。用一维数组W表示每个结点的重量信息。 2、状态保存及继续深入。tot:=tot+waI,j，继续往下搜索，用语句fruit(aI,j)来实现3、回溯处理。tot:=tot-wai,j；为下一次搜索作准备，就是inc(j)。 9数据输入for i:=1 to n do begin j:=0;

4、 repeat inc(j);read(fin,ai,j); until ai,j=0; readln(fin); end; for i:=1 to n do read(fin,wi);close(fin);10tot:=tot+w1;fruit(1);Procedure fruit(i:byte); j:=2; if ai,j=0 then begin if maxtottot then maxtot:=tot;exit;end else begin while ai,j0 do begin tot:=tot+wai,j;fruit(ai,j);tot:=tot-wai,j; j:=j+1;

5、 end; end;11Dfs算法小结1、dfs的算法思想2、状态改变及现场保存3、回溯处理及现场恢复4、什么时候须进行回溯处理？5、各个阶段当前须尝试的方案选择（第一个方案开始？还是接着原来方案的下一个方案？）6、递归程序结构12递归结构框架Procedure try(i:integer);Var k:integer;Begin If 所有阶段都已求解 then Begin 比较最优解并保存；回溯；endelse begin 穷举当前阶段所有可能的决策（方案、结点）k if k方案可行 then begin 记录状态变化；try(i+1);状态恢复（回溯）； end end;End;13承上

6、启下1【例2】【题目描述】 列出所有从数字1到数字n的连续自然数的排列，要求所产生的任一数字序列中不允许出现重复的数字。【输入格式】只有一个整数n(1n9)【输出格式】由1n组成的所有不重复的数字序列，每行一个序列，数字之间用空格隔开。【输入样例】3【输出样例】1 2 31 3 22 1 32 3 13 1 23 2 114算法分析1、不能再用原来的穷举法2、本题算法思考（1）每个阶段指什么？各个阶段须完成什么任务？（2）各个阶段试探的方案是什么？15主程序结构var n:integer; a:array1.9 of integer; f:array1.9 of boolean; 用于记录是否

7、重复begin fillchar(f,sizeof(f),false); readln(n); try(1);end.16输出子过程procedure print; var i:integer; begin for i:=1 to n do if in then write(ai, ) else writeln(an); end;17深度搜索子过程procedure try(i:integer); var j:integer; begin if in then print else for j:=1 to n do if not fj 如果j没有被使用,则继续 then begin ai:=j

8、; 放入一个数j fj:=true; 标记该数已经使用 try(i+1); 继续放下一个数 fj:=false; 回溯时重置使用标记 end; end;18引题2 【例4】选择最短路径。有如下所示的交通路线图，边上数值表示该道路的长度，编程求从1号地点到达7号地点的最短的路径长度是多少，并输出这个长度。19与“引题1”不同的地方？201、是一个显式图2、权值是边权3、需要判重处理21数据结构1、邻接矩阵表示图的连接和权值。AI,j=x,或者aI,j=maxint。Bi表示结点i是否已经遍历过2、用变量min来保存最优解，而用tot变量保存求解过程中临时解（当前路径总长度）。3、状态。Tot的值

9、和结点的遍历标志值22程序结构1、递归结构2、主程序中用try(1)调用递归子程序 3、子程序结构23procedure try(I:integer);var k:integer;begin if 到达了终点 then begin 保存较优解；返回上一点继续求解（回溯）；end else begin 穷举从I出发当前可以直接到达的点k； if I到k点有直接联边 并且 k点没有遍历过 then then begin 把AI,K累加入路径长度tot;k标记为已遍历；try(k); 现场恢复； end; end;24关键环节的分析1、递归结束的判断2、保存较优解的处理3、各个阶段可试探方案的穷举和

10、可行性判断25主程序数据输入 readln(fi,n); for i:=1 to n do begin for j:=1 to n do read(fi,ai,j); readln(fi); end; close(fi);26主程序预处理和调用子程序tot:=0;min:=maxint;b1:=1;try(1);writeln(tot=,min);27procedure try(i:integer);var k:integer;begin if i=n then begin if totmin then min:=tot;exit;end else begin for k:=1 to n do

11、 if (bk=0) and (ik) and (ai,k32700) then begin bk:=1;tot:=tot+ai,k;try(k);bk:=0; tot:=tot-ai,k; end; end;end;28递归子程序结构if i=n+1 then begin 输出解；返回；endelsefor c:=A to chr(64+m) dobegin if c 可以放置 then begin 把c放置到位置1上;try(i+1)；状态恢复；end end;29承上启下2 【例4】邮票问题2。邮局发行一套有n种不同面值的邮票，如果限制每封信所贴的邮票张数不能超过m枚。存在整数R，使得用

12、不超过m枚的邮票可以贴出一下连续序列：1，2，3，4，5，.,R。 编程求出可以得到尽可能大的R值以及对应的n种邮票面值。 30求同思维想想原来邮票问题1是如何求解的？311、穷举所有邮票可能的面值组合2、进一步穷举每种邮票可能贴的数量3、根据1、2的穷举计算当前方案可能的最大连续r值4、每产生一个r值后和原来rmax比较，保存较优解32主程序s1:=1;rmax:=0;f:=0;writeln;write(n,m=);readln(n,m);try(1); 首次调用过程，开始穷举邮票面值for o:=1 to n do write(go:4); 输出每种邮票的面值writeln;writel

13、n(rmax=,rmax);33procedure try(i:integer);varj,temp,l:integer;beginfor j:=si-1+1 to m*si-1+1 do beginsi:=j; if i=n then begin f:=0;stamp:=;work_out_r(1,m);temp:=1; while temp in stamp do temp:=temp+1;if rmaxtemp-1 thenfor l:=1 to n do begin gl:=sl;rmax:=temp-1;end;endelse try(i+1); end;end;34procedur

14、e work_out_r(i1,ej:integer);vark:integer;beginfor k:=0 to ej do beginf:=f+k*si1; if i1=n then stamp:=stamp+f else work_out_r(i1+1,ej-k);f:=f-k*si1; end;end;35Dfs的应用和优化1、何时考虑用dfs？2、适用的题型3、出解的方式4、优化策略36network 多台计算机相互连接，构成计算机网络。在这个问题中，我们只考虑“线性”的网络：计算机首尾相连，构成一条计算机的链，除了首尾2台计算机外，每台计算机恰与2台计算机相连。计算机的物理位置可以

15、用直角坐标表示。在施工时，电缆将被埋在地下，因此连接网络中2台计算机所需的电缆长度等于他们之间的距离再加上额外的16米，以便从地下连接到计算机，并为施工留些余量。 出于经济、技术等方面的考虑，要求所使用的电缆总长度尽可能地短。写一个程序，帮助寻找最优的网络连接方案。 输入和输出 输入文件的第一行是一个整数，表示计算机的总数。网络中包括至少2台，至多10台的计算机。接下来的每一行将给出1台计算机的横坐标和纵坐标，中间用空格隔开。坐标值是0到150的整数。在一个坐标点上不会有2台计算机。 输出只有一行，给出你的程序所找到的最优连接方案所需电缆的总长度。结果四舍五入保留2位小数。37输入文件：65

16、1955 2838 10128 62111 8443 116输出文件：3054538主程序 readln(fin,n);min:=32650; for i:=1 to n do readln(fin,xi,yi); close(fin); for i:=1 to n do bi:=0; s:=0;j:=1; for i:=1 to 6 do begin bi:=1; try(i,j); bi:=0; s:=0; end;39子程序procedure try(i,j:byte);var k:integer;begin if j=n then begin if smin then continue

17、; s:=s+f(i,k); bk:=1; try(k,j+1); s:=s-f(i,k);bk:=0; end;end;40是否还存在优化的素材？41隐式图的dfs求解 在N*N的棋盘上(1=N=10)填入1,2,.N*N共N*N个数,使得任意两个相邻的数之和为素数. 例如,当N=2时,有 1 2 4 3 Input 输入第一行为一整数T,表示有T组测试数据. 每组测试数据一行,为一整数N(1=N=10) Output 输出满足条件的最小序列的方案。 最小序列即将每一行连接起来组成一行，然后使前面的尽可能小，当第一个数字相同时则比较下面一个，依次类推。 比如当时，序列为1 2 4 3，当无满

18、足条件的方案时输出NO。 42Sample Input1 2 Sample Output1 2 4 3 43算法整理1、总的算法考虑2、素数如何判断3、阶段表示4、各个阶段方案的枚举5、各个阶段当前方案可行的判断44筛法判断素数fillchar(d,sizeof(d),1);d1:=false;for i:=2 to 200 doif di then begin j:=i; while j200-i do begin j:=j+i; dj:=false; end;end;45主程序readln(t); for h:=1 to t do begin fillchar(f,sizeof(f),0); flag:=false; f1:=1; readln(n);m1,1:=1; solve(1,2); if flag then 判断是否有解 print 打印 else writeln(NO); end;46Dfs子程序procedure