火力网的搜索优化方案
搜索是万能算法，如果加上剪枝，它将变的更加完美，必要的剪枝可以使程序的效率成几何倍数的增长，所以可以说剪枝是搜索的生命。
问题：火力网（见附录一）
初解：由于最大节点数只有10*10=100个，因此考虑用深度优先搜索解决。在最初的棋盘上对所有的空地放上或拆除碉堡，用类似八皇后问题的回溯法很容易编出程序（见附录二）。但发现到当n>=8时，程序已经不能很快出解了，剪枝势在必行。
剪枝一：改变数据结构，使数据结构为算法服务。
原来用的是二维数组，在搜索时不免因为大量的非空节点（有墙或被控制）使找空节点的效率十分低下。方案：可以将所有的空节点放在一个数组中，记录x,y坐标。
剪枝二：避免重复的搜索，使搜索有序。（下界剪枝）
有时可能出现第I次搜索先选了A格子，后选了B格子，而又在第J次搜索先选了B格子，后选了A格子
为了避免重复的搜索，可以在每次选择一个空地放之后在编号大于它的空地中找下一个可放的位置，这样减去了大量的重复。
剪枝三：对不可能大于Max的进行剪枝。（上界剪枝）
比如现在已经放了n个碉堡，还剩m块空地，若n+m<=Max，那么就不可能大于Max了。
所以，需要对全部未扩展节点+已扩展节点仍不能大于Max的进行剪枝。
***以上只是对于搜索的最一般剪枝方法，与题目关系不大，以
下是针对题目的剪枝。
剪枝四：对横路径数&竖路径数剪枝。
对于一个题目中的图，如果可以看成由空地组成的路径，就可以计算出有多少个横路径和竖路径。比如
122
3333
44
5555
有5条横路径
156
1356
56
2456
6条竖路径。
把题目中的空地抽象成横路径和竖路径后，由于每条路径最多放一个碉堡。根据抽屉原理，碉堡数不超过横路径数或者竖路径数。如果找到方案可以达到最大，那么就输出结束。（这样比
n*n/2更加优秀）。
***以下是利用初始化大量减少空地的方法来剪枝。
剪枝五：在最优点放碉堡
墙碉堡控制范围
原始位置考虑这两点1)如果在这里放2)如果在这里放
所有最优位置（注意最底下两个位置，它们是等效的，任选其一即可）
很明显的看到情况1优于情况2。因为同样是放一个碉堡，但情况1所覆盖的空位属于情况2的一部分（相当与情况2在情况1的基础上白白多控制了一部分）。
图中由于最左上角的点在放完所有的碉堡后一定被控制，而控制它的碉堡只能是上面两种情况（碉堡放[1，1]或[2，1]），所以在左上角放碉堡一定最优，一定不会减少最多碉堡数。在搜索（或随机化之前）可以先在这种地方先放上碉堡（最优点，不影响结果）。
具体怎么找呢？有如下决策：
对于一个空地，如果在它放碉堡只能攻击到一条直线上不被控制的空地（或攻击不到其他空地），则它是最优点（放碉堡不影响结果）。
即：如果某空地放碉堡后在横&竖都可以控制到空点（空地且不被控制），则它不是最优点，否则就是。
证明：设某一空地A满足只能攻击横或竖的空点（仍可以放碉堡的空地）或不能攻击空点。
1.A不能攻击其余空点。
a.可能A周围都是墙?(那么放这里就一定了，相当于白白送一碉堡)
b.可能A周围都被其余碉堡控制?(由于不会减少其余空地的个数，相当于直接变一空地为碉堡)
c.可能A周围又有墙又被其余碉堡控制?(综上所述，放这里绝对没错)
2.A只能控制一条直线上的空点。
首先，在放完所有的碉堡后A一定被控制（如果没被控制说明A还可以放），而且控制A的点只能是A所能控制直线上的点（若A控制不了B，则B一定控制不了A；若A能控制B，则B一定能控制A）。
就是说在A和同一条直线上的其他点之中要放一个。
注意到不管是放哪一个都要控制这条直线，而A只控制这条直线。如果放其余位置则可能控制更多的地方（也有可能与A等效，但不会比A更好）。
这种情况放A绝对不错。
在最开始对地图扫描几遍，找出所有的最优点放上碉堡，这样可以使待搜索的节点大量减少，从而飞速提高程序效率，而不会漏解。（节点越多，搜索量越大）
***但如果大量的节点都是空点，最优点少之又少怎么办呢？虽
然前五个剪枝足以应付题目，但如果棋盘在大怎么办呢？对此，我们有如下初始化剪枝（矩形剪枝系列）。
注：以下矩形内部均不被事先控制。
剪枝六：在矩形中放碉堡。
如果在某一地区由墙所围成了一个m*n的矩形（设m<=n）,则矩形中最多可放m个碉堡。（证明从略）
如上图是一个3*4的矩形，很明显最多只能放短边数，既3个碉堡。
若m=n(正方形)，放对角线就可以了。
***当然，这种刚好矩形情况少之又少，说出来只是为了进一步解释以下剪枝
剪枝七：三面墙一面开口且开口边是宽（或是正方形）的矩形。
如图，注意红匡内的矩形，就是满足定义的矩形。
决策：m*n（m<=n）的矩形中放m个碉堡一定最优。
证明：
首先，在这种m*n（m<=n）的矩形中最多可以放m个碉堡
其次，注意蓝线所标出的列上的所有节点，在最后一定被控制。那么就有两种控制情况。（不可能有些被横着控制，有些被竖着控制）
1．全被竖着控制?（也就是说在这一列上必有一碉堡）
2．全被横着控制?（在矩形中如果不在这一列放碉堡，那么最多只可以放m-1个碉堡，小于长，那么就有一行不能被控制（不可能））。
综上所述，每一列都要放一碉堡。
a.如果放矩形内部，则除了控制这一列还控制矩形中的一行（事实是，m个碉堡已经把矩形控制完了），这其实不会影响什么。
b.而如果放矩形外部，则可能控制更多的节点。（不会比放内部更好）
这样，一批一批的节点被剪掉，程序效率突飞猛进，事实上还有更为优秀的策略。
剪枝八：对面开口，且开口边不大于另一边的管状矩形。
如图中的矩形（3*4），两面（对面）开口，另两面是墙。
决策：m*n（m<=n）的矩形中放m个碉堡一定最优。
证明：（改编于剪枝七的证明）
首先，在这种m*n（m<=n）的矩形中最多可以放m个碉堡
其次，矩形内任意一行的所有节点，在最后一定被控制。那么就有两种控制情况。（因为不可能有些被横着控制，有些被竖着控制）
1．全被横着控制?（也就是说在这一横行上必有一碉堡）
2．全被竖着控制?（在矩形中如果不在这一行放碉堡，那么最多只可以放m-1个碉堡，小于长，那么就有一列不能被控制（不可能））。
综上所述，每一行都要放一碉堡。
a.如果放矩形内部，则除了控制这一行还控制矩形中的一列（事实是，m个碉堡已经把矩形控制完了），这其实不会影响什么。
b.而如果放矩形外部，则可能控制更多的节点。（不会比放内部更好）
剪枝九：三面墙一面开口且开口边是长的矩形。
如图，是个2*7的矩形，最多可放2个碉堡。（图中两个碉堡只攻击矩形内部，所以最优）
决策：m*n（m<=n）的矩形中在开口一边若与墙相邻，则在这一列放碉堡一定最优，最多放m个碉堡。（我只能证明到这里了）
证明：
首先此矩形开口一边一定有墙相邻（否则就没法优化了）。
因此如果不在矩形内放m个碉堡，就会使有些空地得不到控制。（因为不能来自同一行和外界的控制）
所以一定有m个碉堡（既每一行都有碉堡，也就是矩形内全被控制）。
那么在决策的地方放碉堡就等于是白送了。
剪枝十：对面开口，且开口边大于另一边的管状矩形。
决策：m*n（m<=n）的矩形中在开口边相邻位置有对称的墙出现，则在这一行放碉堡一定最优，最多放m个碉堡。
（证明可以仿照剪枝八与剪枝九的证明）
事实上，由于所给的地图的外面一层可以看做是墙，矩形剪枝大有用武之地。
事实是，用前5个剪枝就足以解决题目。
但更为事实的是由于编码的复杂性，矩形剪枝的理论性大于实践性。写在这里仅做抛砖引玉之用而已。
除此之外，还可以搜索时对每一个格子设一个估价函数，对优秀性进行评估，选出可能是最好的格子放，进行启发式搜索，这样再大的地图也可以瞬间出界。
最后奉劝一句，不要看我写的代码（冗长啊）。
附录一：火力网(Fire)
【问题描述】在一个n*n的阵地中，有若干炮火不可摧毁的石墙，现在要在这个阵地中
的空地上布置一些碉堡。假设碉堡只能向上下左右四个方向开火，由于建筑碉堡的材料挡不住炮火，所以任意一个碉堡都不能落在其他碉堡的火力范围内，请问至多可建造几座碉堡？
输入：
输入文件名为FIRE.IN，第一行是一个整数n(n<=10)，下面n行每行为一个由n个字符构成的字符串，表示阵地的布局，包括空地（’.’），和石墙（’X’）。
输出：
输出文件名为FIRE.OUT，一个整数，即最多可建造的碉堡数。
【样例输入输出】
FIRE.IN
4
.X..
....
XX..
....
FIRE.OUT
5
附录二：不带任何优化的搜索代码
Program Fire;
Var
n,//大小
Max:Longint;//最多
x:Array[0..11,0..11]of Boolean;//地图
f:Array[1..10,1..10]of Longint;//火力覆盖
Procedure Init;{读入}
Var Q1,Q2:Longint;ch:Char;
Begin
Fillchar(x,sizeof(x),false);
Max:=0;
readln(n);
For Q1:=1To n Do
Begin
For Q2:=1To n Do
Begin
read(ch);
if ch='.'then x[Q1,Q2]:=True else x[Q1,Q2]:=False;
if ch='.'then f[Q1,Q2]:=0else f[Q1,Q2]:=1;
End;
readln;
End;
End;
Procedure Put(a,b:Longint);{在[a,b]放碉堡}
Var ww:Longint;
Begin
inc(f[a,b]);
ww:=a+1;
while x[ww,b]do Begin inc(f[ww,b]);inc(ww);End;
ww:=a-1;
while x[ww,b]do Begin inc(f[ww,b]);dec(ww);End;
ww:=b+1;
while x[a,ww]do Begin inc(f[a,ww]);inc(ww);End;
ww:=b-1;
while x[a,ww]do Begin inc(f[a,ww]);dec(ww);End; End;
Procedure Out(c,d:Longint);{去掉[c,d]的碉堡}
Var ee:Longint;
Begin
dec(f[c,d]);
ee:=c+1;
while x[ee,d]do Begin dec(f[ee,d]);inc(ee);End;
ee:=c-1;
while x[ee,d]do Begin dec(f[ee,d]);dec(ee);End;
ee:=d+1;
while x[c,ee]do Begin dec(f[c,ee]);inc(ee);End;
ee:=d-1;
while x[c,ee]do Begin dec(f[c,ee]);dec(ee);End; End;
Procedure Find(k:longint);{找第k个碉堡}
Var i,j,it:Longint;
Begin
If k-1>Max then Max:=k-1;
For it:=1to sqr(n)do
Begin
i:=(it-1)div n+1;
j:=(it-1)mod n+1;
If F[i,j]=0then
Begin
Put(i,j);
Find(k+1,(i-1)*n+j+1);
Out(i,j);
End;
End;
End;
Begin
Assign(Input,'fire.in');
Assign(Output,'fire.out');
Reset(Input);
Rewrite(Output);
Init;
Find(1);
writeln(Max);
Close(Input);
Close(Output);
End.
附录三：剪枝12345的搜索代码Program Fire;
Const
MaxN=10;
Var
n,{大小}
MinPath,{横路径数&竖路径数中最小的，也是可能放碉堡最多的数目}
Max,{最多放的碉堡数}
Npoint:Longint;{空点总数}
k:Array[0..MaxN+1,0..MaxN+1]of Boolean;{是否是空地}
f:Array[0..MaxN+1,0..MaxN+1]of Longint;{火力覆盖数}
p:array[1..MaxN*MaxN]of Record x,y:Longint;End;{空地的坐标}
Procedure Put(a,b:Longint);{在[a,b]放碉堡}
Var ww:Longint;
Begin
Inc(f[a,b]);
ww:=a+1;
While k[ww,b]Do Begin Inc(f[ww,b]);Inc(ww);End;
ww:=a-1;
While k[ww,b]Do Begin Inc(f[ww,b]);Dec(ww);End;
ww:=b+1;
While k[a,ww]Do Begin Inc(f[a,ww]);Inc(ww);End;
ww:=b-1;
While k[a,ww]Do Begin Inc(f[a,ww]);Dec(ww);End;
End;
Procedure Out(c,d:Longint);{去掉[c,d]的碉堡}
Var ee:Longint;
Begin
Dec(f[c,d]);
ee:=c+1;
While k[ee,d]Do Begin Dec(f[ee,d]);Inc(ee);End;
ee:=c-1;
While k[ee,d]Do Begin Dec(f[ee,d]);Dec(ee);End;
ee:=d+1;
While k[c,ee]Do Begin Dec(f[c,ee]);Inc(ee);End;
ee:=d-1;
While k[c,ee]Do Begin Dec(f[c,ee]);Dec(ee);End;
End;
Procedure Init;{读入}
Var
Q1,Q2:Longint;ch:Char;
Begin
Fillchar(k,Sizeof(k),False);
Readln(n);
For Q1:=1To n Do
Begin
For Q2:=1To n Do
Begin
Read(ch);
If ch='.'Then k[Q1,Q2]:=True;
End;
Readln;
End;
End;
Procedure Beginning;{主要是算横&竖路径}
Var
W1,W2,HHH,SSS:Longint;
Begin
Max:=0;
Fillchar(f,Sizeof(f),0);
For W1:=0To n+1Do
For W2:=0To n+1Do
If Not k[W1,W2]Then f[W1,W2]:=1{MaxLongint};{有墙，火力覆盖置为MaxLongint}
HHH:=0;{算横路径数}
For W1:=1To n Do{行}
Begin
W2:=1;
While W2<=n Do
Begin
While(W2<=n)And(Not k[W1,W2])Do Inc(W2);{去掉墙}
If k[W1,W2]Then Begin Inc(HHH);While k[W1,W2]Do Inc(W2);End;{算空地} End;
End;
SSS:=0;{算竖路径数}
For W2:=1To n Do
Begin
W1:=1;
while W1<=n Do
Begin
While(W1<=n)And(Not k[W1,W2])Do Inc(W1);
If k[W1,W2]then Begin Inc(SSS);While k[W1,W2]Do Inc(w1);End;
End;
End;
If SSS>HHH then MinPath:=HHH Else MinPath:=SSS;{横路径数&竖路径数中最小的赋给MinPath} End;
Procedure PutMust;{放最优点}
Var
Over,HH,SS:Boolean;
E1,E2,E3,E4:Longint;
Begin
Repeat
Over:=True;{是否找完最优点}
For E1:=1To n Do
For E2:=1To n Do
If f[E1,E2]=0Then
Begin
HH:=False;SS:=False;
E3:=E1+1;
While k[E3,E2]do{竖着往下走}
Begin
If f[E3,E2]=0Then Begin SS:=True;Break;End;
Inc(E3);
End;
If Not SS Then{竖着往上走}
Begin
E3:=E1-1;
While k[E3,E2]do
Begin
If f[E3,E2]=0Then Begin SS:=True;Break;End;
Dec(E3);
End;
End;
E4:=E2+1;
While k[E1,E4]do{横着往右走}
Begin
If f[E1,E4]=0Then Begin HH:=True;Break;End;
Inc(E4);
End;
If Not HH Then{横着往左走}
Begin
E4:=E2-1;
While k[E1,E4]do
Begin
If f[E1,E4]=0Then Begin HH:=True;Break;End;
Dec(E4);
End;
End;
If HH And SS then Continue;
Put(E1,E2);{放上}
Inc(Max);{多了一个碉堡}
Over:=False;{找到则继续找}
End;
Until Over;
If Max=MinPath Then Begin Writeln(Max);Close(Input);Close(Output);Halt;End;{运气好的话，哈哈哈~}
End;
Procedure DataSave_f_To_p;{改变数据结构，剪枝1}
Var R1,R2:Longint;
Begin
Npoint:=0;
For R1:=1To n Do
For R2:=1To n Do
If f[R1,R2]=0then
Begin
Inc(Npoint);
p[Npoint].x:=R1;
p[Npoint].y:=R2;
End;
End;
Procedure Find(T,xy:Longint);{寻找第T个格子(p中),第xy个碉堡}
Var i:Longint;
Begin
If xy-1>Max Then Begin
{横&竖路径判断 }If xy-1=MinPath Then Begin Writeln(MinPath);Close(Input); Close(Output);Halt;End;
Max:=xy-1;
End;
For i:=T To Npoint+xy-Max-1Do//剪枝2，3：上下界剪枝
If f[p[i].x,p[i].y]=0then
Begin
Put(p[i].x,p[i].y);
Find(i+1,xy+1);{递归}
Out(p[i].x,p[i].y)
End;
End;
Begin
Assign(Input,'fire.in');
Assign(Output,'fire.out');
Reset(Input);
Rewrite(Output);
Init;
Beginning;{剪枝4，算横&竖路径} PutMust;{剪枝5，放最优点} DataSave_f_To_p;{改变数据结构，剪枝1}
Find(1,Max+1);{DFS}
Writeln(Max);
Close(Input);
Close(Output);
End.
附录四：数据产生程序
{参数为空地的概率，越大表示空地越多}
Program MakeFire;
var i,j,n:longint;abc:extended;
begin
writeln('Input n');readln(n);
writeln('Input参数(大于0小于1)');readln(abc);
assign(output,'fire.in');
rewrite(output);
randomize;
writeln(n);
for i:=1to n do
begin
for j:=1to n do if random writeln; end; close(output); end. 合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。 深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。 所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s 上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班 学号：201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。 二、实验环境： Windows 8.1 Microsoft Visual c++ 6.0 二、实验内容及要求： 编写图的深度优先遍历邻接矩阵算法。建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 四、概要设计： 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图中无向图G4为例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为： V1 V2 V4 V8 V5 V3 V6 V7 五、代码 #include 一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 习题 3 1、答：深度优先搜索算法的特点是 ①一般不能保证找到最优解； ②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制； ③方法与问题无关，具有通用性； ④属于图搜索方法。 宽度优先搜索算法的特点是 ①当问题有解时，一定能找到解； ②当问题为单位耗散值，并且问题有解时，一定能找到最优解； ③效率低； ④方法与问题无关，具有通用性； ⑤属于图搜索方法。 2、答：在决定生成子状态的最优次序时，应该采用深度进行衡量，使深度大的 结点优先扩展。 3、答：（1）深度优先 （2）深度优先 （3）宽度优先 （4）宽度优先 （5）宽度优先 4、答：如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那 么给以后放皇后留下的余地就大，找到解的可能性也大；反之留下的余地就小，找到解的可能性也小。 并不是任何启发函数对搜索都是有用的。 6、讨论一个启发函数h在搜索期间可以得到改善的几种方法。 7、答：最短路径为ACEBDA，其耗散值为15。 8、解：（1）（S，O，S0，G） S：3个黑色板和3个白色板在7个空格中的任何一种布局都是一个状态。 O：①一块板移入相邻的空格； ②一块板相隔1块其他的板跳入空格； ③一块板相隔2块其他的板跳入空格。 S0： B B B W W W G： W W W B B B W W W B B B W W W B B B W W W B B B W W W B B B W W W B B B W W W B B B （2）1401231231234567333377 =???????????=?P P P （3）定义启发函数h 为每一白色板左边的黑色板数的和。 显然，)()(n h n h *≤，所以该算法具有可采纳性。 又，?? ?≤-=),()()(0)(j i i j n n c n h n h t h ，所以该启发函数h 满足单调限制条件。 9、解： ((( ),( )),( ),(( ),( ))) ((S,( )),( ),(( ),( ))) ((A,( )),( ),(( ),( ))) ((A,S),( ),(( ),( ))) ((A,A),( ),(( ),( ))) ((A),( ),(( ),( ))) (S,( ),(( ),( ))) (A,( ),(( ),( ))) (A,S,(( ),( ))) (A,A,(( ),( ))) (A,(( ),( ))) #include 华北水利水电学院数据结构实验报告 20 10 ～20 11 学年第一学期2008级计算机专业 班级：107学号：200810702姓名：王文波 实验四图的应用 一、实验目的： 1．掌握图的存储结构及其构造方法 2．掌握图的两种遍历算法及其执行过程 二、实验内容： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。 三、实验要求： 1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。 2．C/ C++完成算法设计和程序设计并上机调试通过。 3．撰写实验报告，提供实验结果和数据。 4．写出算法设计小结和心得。 四、程序源代码： #include { int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2; 2007-05-27 晴 //采用非递归深度优先遍历算法，可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 深度学习模型剪枝的评述 摘要 近年来，深度神经网络在机器视觉和自然语言处理领域都取得了巨大的成功。然而，要将这些模型部署到诸如机器人芯片、智能手机等微型嵌入式设备上仍是一个巨大的挑战。因此，对于这样的平台，模型压缩是一种降低内存消耗和计算复杂度的合理解决方案，目前处理这一问题的技术手段仍然是模型剪枝，而通道级别的模型剪枝又是最有效的手段之一。因此如何有效的实现通道级别的模型剪枝是至关重要的，并且一直是一个具有大量研究成果的主题。 本文阐述了近年来出现的通道级别模型剪枝的主要技术手段，我们主要讨论各个论文的研究成果和遇到的问题，以及根据共同的特点按类别组织的解决方案列表，并且还列出了各个实验结果之间的比较。 关键词：深度学习，模型压缩，通道剪枝 一．引言 在最近这几年中，深度学习赢得了越来越多的关注，并且促进了非常多领域的突破，这依赖于深度神经网络百万甚至千万级别的参数量，和图形处理器的高速计算能力都起着至关重要的作用。 然而，深度学习模型不管在训练还是在部署到设备上时都存在需要问题。比如，[1]在2012年的ImageNet Challenge中取得了突破性的成果，使用了包含6000万个参数的5个卷积层和3个全连接层的网络。通常需要两到三天的时间在NVIDIA K40机器来训练整个模型的ImagetNet数据集。有时在仅依赖于全连接层的架构中，参数的数量可以增长到数十亿[2]。另一方面，卷积运算消耗了大量的计算资源，而这在移动设备上是非常稀缺的，数十亿的网络参数对于嵌入式设备来说也是高存储开销。以VGG-16模型为例，它拥有超过1.38亿个参数，占用超过500MB的内存空间。同时，224×224图像的分类需要300亿次浮点运算(FLOPs)。显然，将如此大的模型直接部署到嵌入式设备中是不切实际的。 因此，在精度没有明显下降的情况下压缩深度模型是一个关键问题。在这种情况下，许多模型压缩方法也相继被提出。最近的一些压缩和加速方法，包括权值剪枝[3-5]、网络量化[6-8]、低秩近似[9,10]、高效模型设计[11-12]。神经元剪枝方法[3]通过去除一些不那么重要的连接，使权值变得稀疏。网络量化针对存储空间压缩问题，提出了一种降低参数表示精度的网络量化[7]算法。低秩近似[9]利用低秩矩阵技术将权值矩阵分解成几个存储空间较小的小矩阵。但是以上方法或多或少存在一些问题，权值剪枝与网络量化需要特殊的软硬件结合使用才能达到好的效果，低秩近似对于1*1的卷积并无效果。而高效模型设计更多关注设计一些不同的网络模型而不是优化已有的卷积运算或者网络架构来压缩加速。 通道剪枝[4,5]是另一种权值剪枝方法，不同于神经元剪枝。与去除单个神经元连接相比，修剪整个通道有两个优点。首先，它不引入原始网络结构的稀疏性，因此不需要对生成的模型进行特殊的软硬件实现。其次，推理阶段不需要庞大的磁盘存储和运行时内存。 本文综述了近年来通道剪枝在深神经网络的压缩和加速研究进展，这些研究引起了深度 题目: 图的深度优先遍历算法 一、实验题目 前序遍历二叉树 二、实验目的 ⑴掌握图的逻辑结构； ⑵掌握图的邻接矩阵存储结构； ⑶验证图的邻接矩阵存储及其深度优先遍历操作的实现。 三、实验内容与实现 ⑴建立无向图的邻接矩阵存储； ⑵对建立的无向图，进行深度优先遍历；实验实现 #include typedef struct EdgeNode { int adjvex; struct EdgeNode *next; }EdgeNode; typedef struct VertexNode { VertexType data; EdgeNode *firstedge; }VertexNode,AdjList[MaxVex]; typedef struct Graph{ AdjList adjList; int numVertexes,numEdges; }Graph,*GraphAdjList; typedef struct LoopQueue{ int data[MaxVex]; int front,rear; }LoopQueue,*Queue; void initQueue(Queue &Q){ Q->front=Q->rear=0; } Bool QueueEmpty(Queue &Q){ if(Q->front == Q->rear){ return TRUE; }else{ return FALSE; } } Bool QueueFull(Queue &Q){ if((Q->rear+1)%MaxVex == Q->front){ return TRUE; }else{ return FALSE; } } void EnQueue(Queue &Q,int e){ if(!QueueFull(Q)){ Q->data[Q->rear] = e; AlphaBeta剪枝算法 关于AlphaBeta剪枝的文章太多，这个方法是所有其它搜索方法的基础，得多花些时间认真地理解。 先把基本概念再回顾一遍： 节点：在中国象棋中就是一个棋盘的当前局面Board，当然该轮到谁走棋也是确定的。这里的圆形节点表示终止节点，在中国象棋里就是一方被将死的情况（或者到达了搜索的最大深度），后续不会再有着法产生，游戏如果走到这里就会结束。在引擎里通常给红方一个很大的评估值，如+30000，给黑方一个很小的评估值，如-30000，来方便地判断这种结束局面。（胜利局面有稍微不同的表示法，用-30000+层数ply来表示） 连线：表示一步着法Move，通过这步着法后，局面发生变化，先后手也要交换。 层：通常的术语是ply，复数形式是plies，也有称为levels，当然与depth也是对应的。这个术语是为了与比赛里常说的回合相区分，一个回合通常包含2步，这个ply就表示某一方走了一步。根节点记为0层，以下的层数递增。 深度depth：要注意是从下到上的，还是从上到下的。（1）通常的算法书中都是从下到上递增的，即根节点为最大搜索深度，走到最底部的叶子结点为0，这种算法只要记住一个depth 值就可以了。（2）而另一种记法是根部结点为0，越向下depth增加，这时在搜索时就要传递2个参数值，depth和maxDepth，稍微有点啰嗦，应该也会影响一点效率。另外在探查置换表中的结点时，用第（1）种记法也方便一些，因为要知道从当前节点迭代的深度值，否则还要在置换表中保存depth和maxDepth两个值。 AlphaBeta剪枝方法是对Minimax方法的优化，它们产生的结果是完全相同的，只不过运行效率不一样。 这种方法的前提假设与Minimax也是一样的： 1）双方都按自己认为的最佳着法行棋。 2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，红方有利时给一个正数，黑方有利时给一个负数。（如果红方有利时返回正数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回正数，这种评估方法都不适合于常规的算法描述） 3）从我们的搜索程序（通常把它称为Max）看来，分值大的数表示对己方有利，而对于对方Min来说，它会选择分值小的着法。 但要注意：用Negamax风格来描述的AlphaBeta中的评估函数，对轮到谁走棋是敏感的。 也就是说： 在Minimax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋评估值仍是100。 但在Negamax风格的AlphaBeta算法中，轮红方走棋时，评估值为100，轮黑方走棋时评估值要为-100。 谈搜索算法的剪枝优化 许晋炫 【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧。首先由回溯法解决迷宫问题展开论述，介绍了什么是剪枝；而后分析剪枝的三个原则棗正确、准确、高效，并分别就剪枝的两种思路：可行性剪枝及最优性剪枝，结合例题作进一步的阐述；最后对剪枝优化方法进行了一些总结。 【关键字】搜索、优化、剪枝、时间复杂度 引论 在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。 搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。 所以，对程序进行优化，就成为搜索算法编程中最关键的一环。 本文所要讨论的便是搜索算法中优化程序的一种基本方法棗“剪枝”。 什么是剪枝 相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的： 1、这个方向有路可走，我没走过 2、往这个方向前进 3、是死胡同，往回走，回到上一个路口 4、重复第一步，直到找着出口 这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。 我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？ 答案是：可以的。 剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。 搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。 剪枝的原则 1、正确性 正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也 *问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j]（或∑A[i,j]） j=1 i=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若 *问题描述： 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若 ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2005年第45卷第S1期 2005,V o l.45,N o.S15/39 1748-1752 最大频繁项集挖掘中搜索空间的剪枝策略 马志新, 陈晓云, 王 雪, 李龙杰 (兰州大学信息科学与工程学院,兰州730000) 收稿日期:2005-05-20 基金项目:国家自然科学基金资助项目(60473095)作者简介:马志新(1973-),男(汉),甘肃,副教授。 E-mail:mazhx@lz https://www.doczj.com/doc/9416386642.html, 摘 要:最大频繁项集挖掘可以广泛应用在多种重要的Web 挖掘工作中。为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略。这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝。应用该策略,对M A FI A 算法进行改进优化。实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原M AF IA 算法提高3～5倍。 关键词:W eb 挖掘;最大频繁项集;剪枝策略;搜索空间中图分类号:T P 311文献标识码:A 文章编号:1000-0054(2005)S 1-1748-05 Pruning strategy for mining maximal frequent itemsets MA Zhixin ,CHE N Xiaoyun ,WANG Xue ,LI Lon gjie (School of I nformation Science and Engineering ,Lanzhou University ,Lanzhou 730000,China ) Abstract :M in ing maximal frequent itemsets is a fundamental problem in man y practical w eb m ining ap plications.T his paper presen ts ESEquivPS (exten sion sup por t equivalency pruning strategy),a n ew search space p runing s trategy for mining m axim al frequent itemsets to effectively reduce the s earch s pace.ESE qu ivPS w as based on a depth-first travers al of lexicographic su bset en umer ation tree and uses equivalency of item's ex tension supports to pru ne s earch space.Furthermore,th e M AFIA (m axim al frequen t items et alg or ith m)w as improved by u sing ESEquivPS.T he ex perimental r esu lts show that ES EquivPS can efficiently redu ce the search space.E specially on s pars e dataset w ith longer items ets ,the siz e of search s pace can be trimmed off by 2/3and n ew algorithm runs around three to five times fas ter th an previou s M AFIA algorithm. Key words :w eb m ining; maximal frequent items ets ; pruning strategy;search space 频繁项集挖掘是一类重要的数据挖掘问题,可以广泛应用在客户行为模式分析、网页关联分析、日志分析和网络入侵检测等重要的Web 挖掘工作中。 该问题描述如下:给定事务数据库D ,项目集合I 和用户指定的支持度阈值 ,频繁项集挖掘是在D 中找出支持度大于或等于阈值 的所有项集。 典型的频繁项集挖掘算法是A priori 以及在此基础上的各种改进算法[1],该类算法采用自底向上广度优先的思想,依次计算出所有的频繁1项集,频繁2项集,直到找出所有的频繁项集。当出现大量长的频繁项集时,该类算法代价很高,需要多次扫描数据库并且产生大量的候选项集,对于长度为m 的频繁项集需要枚举出所有可能的2m -2个子集,出现组合问题,导致算法效率低下或无法计算。因此,最大频繁项集挖掘和封闭频繁项集挖掘方法受到该研究领域的重视,先后提出多种重要的最大频繁项集挖掘算法和封闭频繁项集挖掘算法[27]。 如何有效地进行搜索空间剪枝是最大频繁项集挖掘研究工作的一个核心[6]。本文提出了一种新的搜索空间剪枝策略:扩展支持度相等性剪枝策略ESEquivPS (ex tension support equivalency pruning strateg y ),该策略基于词典序子集枚举树,利用树中子节点与父节点的扩展集中相同项的扩展支持度相等的特性,对搜索空间进行削减。该策略可以方便的应用到各种最大频繁项集挖掘算法中,大幅度提高算法的效率。本文结合ESEquivPS 对MA FIA 算法进行了优化改进,并在不同特征的Web 数据集上进行了实验验证。实验结果表明,该剪枝策略可以有效削减搜索空间,改进后的算法效率明显优于原有的MAFIA 算法。 1 最大频繁项集挖掘与搜索空间剪枝策略 最大频繁项集挖掘问题具体描述如下。 算法设计：深度优先遍历和广度优先遍历实现 深度优先遍历过程 1、图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 以下假定遍历过程中访问顶点的操作是简单地输出顶点。 2、布尔向量visited[0．．n-1]的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。 -------------------------- 深度优先遍历(Depth-First Traversal) 1．图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的 下面我们举一个例子——Betsy 的旅行(USACO)。 题目简述：一个正方形的小镇被分成N 2个小方格，Betsy 要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N ，计算出Betsy 能采用的所有的旅行路线的数目。 实际上，由于Betsy 的每一次移动，只会影响到附近的格子，所以每次执行剪枝判断时，应当只对她附近的格子进行检查： 对于第一个剪枝条件，我们可以设一个整型标志数组，分别保存与每个格子相邻的没被经过的格子的数目，Betsy 每次移动到一个新位置，都只会使与之相邻的至多4个格子的标志值发生变化，只要检查它们的标志值即可。 而对于第二个剪枝条件，处理就稍稍麻烦一些。但我们仍然可以使用局部分析的方法，即只通过对Betsy 附近的格子进行判断，就确定是否应当剪枝，下图简要说明了剪枝的原理： 上图给出了可以剪枝的三种情况。由于Betsy 到过的所有格子都一定是四连通的，所以每种情况下的两个白色的格子之间必定是不连通的，它们当中必然至少有一个是属于某个孤立区域的，都一定可以剪枝。 一、 优性剪枝 下面举一个应用最优性剪枝的典型例题——最少乘法次数。 题目简述：由x 开始，通过最少的乘法次数得出n x ，其中n 为输入数据。（参见参考书目1） 因为两式相乘等于方幂相加，所以本题可以等效的表示为：构造一个数列{}i a ，满足 ???><<=+==)1(),1()1(1i i k j a a i a k j i 要求n a t =，并且使t 最小。 我们选择回溯法作为本程序的主体结构：当搜索到第i 层时，i a 的取值范围 搜索中的剪枝优化 在11+-i a 到2*1-i a 之间，为了尽快接近目标n ，应当从2*1-i a 开始从大到小为i a 取值，当然，选取的数都不能大于n 。当搜索到n 出现时，就得到了一个解，与当前保存的解比较取优。最终搜索结束之后，即得到最终的最优解。 如果按上述结构直接进行搜索，效率显然很低。因此，我们可以考虑使用最优性剪枝进行优化： 优化之一：当然首先要建立估价函数。由于使数列中的最大数加倍无疑是最快的增长方式，所以一种最简单的估价函数为（设数列中当前的最大者是i a ，即当前搜索深度为i ）： ????? ?=i a n h 2log 然而，这个估价函数的准确性太差，特别是当i a 大于2 n 时，h 只能等于1，根本不能发挥剪枝的作用。因此，无论是深度优先的回溯法还是宽度优先的A*搜索方法，只要还使用这个估价函数，其优化效果都比较有限。 下面，我们再讨论一些进一步的优化手段—— 优化之五：当数列中的当前最大数i a 超过2 n 后，原估价函数就难以发挥作用了。但是，此后的最优方案，实际上就等价于从1a 到i a 这i 个数中，选出尽可能少的数（可重复），使它们的和等于n 。这个问题已经可以使用动态规划方法来解决。这样得到的“估价函数”不但完全准确，甚至直接就可以代替后面的搜索过程。这里也体现出了搜索和动态规划的优势互补。 二、“最少乘法次数”的估价函数的改进： 最初的估价函数的设计思路实际上是在当前数列i a a ,,1 的基础上理想化的构造i p i i a a a 2,,4,2 ，当i p i p a n a 122+<<时，原估价方法认为只需再进行一次加法，即找一个数与i p a 2相加就够了。 然而，这只是保证了能够得到大于等于n 的数，并不一定恰好得到n 。我们可以作如下分析： 首先，任何一个自然数i 都可以表示成),()12(2___-∈+Z m k m k 的形式，我们可以设)(i k 表示一个自然数i 所对应的k 值。显然，对于任何两个自然数a 和b ，都有()()(){}b k a k b a k ,min ≥+（我们由此可以很容易的联想到“奇+奇=偶，偶+偶=偶，奇+偶=奇”的性质）。 然后，我们再研究前述估价时所构造的数列： i p i i i a a a a a a 2,,4,2,,,,21 （其中，i p i p a n a 122+<<） 在应用新的剪枝判断之前，我们应当先检验()()??p a a n i i ≥+-12/log ，这个条件可以保证只有构造上述数列才是最优的。 若存在自然数()p j j ≤≤1，使得() ()n k a k i j >2，由()()(){}b k a k b a k ,min ≥+， 则有()()()()()p t j n k a k a k a a k i j i t i p i t ≤≤>≥≥+2222 n a a i p i t ≠+∴22 （()()b k a k =是b a =的必要条件） 即i p i j a a 2,,2 中的任何一个数与i p a 2相加都不可能得到n 。 所以，如果i j i p a a n 122->-，则在得到i p a 2后，至少还需要再进行两次加法图的深度优先遍历算法课程设计报告
深度优先遍历(邻接矩阵)
图的深度优先遍历实验报告
答深度优先搜索算法的特点是
邻接矩阵的深度优先遍历
图的深度优先遍历和广度优先遍历
采用非递归深度优先遍历算法
剪枝综述
数据结构实验报告图的深度优先遍历算法
AlphaBeta剪枝算法
谈搜索算法的剪枝优化
邻接矩阵表示图深度广度优先遍历
邻接矩阵表示图_深度_广度优先遍历
最大频繁项集挖掘中搜索空间的剪枝策略
算法设计：深度优先遍历和广度优先遍历
搜索方法中的剪枝优化
相关主题
文本预览