搜索与剪枝--ACM

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,推荐书籍,算法艺术与信息学竞赛,作者：刘汝佳 黄亮,清华大学出版社,2,一引言,搜索被称为通用解题法，在算法和人工智能中占有重要地位。搜索是ACM竞赛中的常见算法，本次讲座的主要内容就是分析它的 特点,以及在实际问题中如何合理的选择搜索方法，提高效率。首先介绍各种基本的搜索及其各自的特点。在基本搜索方法的基础上学习一些更高级的搜索，提高搜索的效率。然后探讨运用搜索算法高效地解决实际问题的方法，体现搜索的广泛应用性。,3,状态空间,状态state,状态转移state transition,智能体 agent,简单的多智能体系统,状态空间:搜索的过程实际上是在遍历一个隐式图，遍历结果为解答树。,4,二 常用搜索算法,（1）盲目搜索,纯随机搜索,广度优先搜索（BFS）,深度优先搜索（DFS）走迷宫,重复式搜索,迭代加深搜索,迭代加宽搜索,柱型搜索,（2）启发式搜索,贪心搜索,A*搜索,5,深度搜索与广度搜索,深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构.,广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。,6,双向广度搜索,广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。,分支定界,分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。,7,周界搜索。,初始状态和目标状态都已经确定。由于在每个测试数据中，目标结点都是一样的，反向搜索一次就够了。先反向搜索一次，把结点都保存起来再正向搜索的方法叫周界搜索（perimeter search）。,一般来说，周界中的结点不再变更，只需对它进行检索，而不进行插入和删除，所以采用Hash表或Trie都可以。,反向搜索的深度对于程序的效率影响比较大，一般深度为7时，效率较高。,8,深度优先遍历的思想（DFS）,在图中从任意一个顶点（设为v0）开始，进行遍历,接着找v0的第一邻接点，若该邻接点未被遍历，则遍历之，再找该邻接点的第一邻接点，若该第一邻接点已被遍历，则找其下一邻接点。若下一邻接点未被遍历，则遍历，再找它的第一邻接点，就这样递归向下进行。若遇到第一邻接点不存在，或下一邻接点也不存在时，则退回到调用的上一层。如此下去，若不能遍历完所有顶点（说明不是连通图），则再选一个未遍历的顶点，重新开始以上过程，直至所有顶点遍历完毕。,9,深度优先遍历的算法,int visitedMAX+1 /*辅助数组，是算法中需用到的全局变量 */,void dfs(g,v) /* 从图g的第v号顶点出发深度优先遍历 */,AdGraph gMAX+1,int v;, EdgeNode *p;,printf(“6d”,gv.vexdata) /* 首先访问该顶点，假设其数据为整数 */,visitedv=1;,p=gv.link;,while(p), if(visitedp-adjnum!=l) dfs(g,p-adjnum);,/* 若该顶点末被访问过，则递归调用 */,p=p-next; /* p指向下一个与第v个顶点链接的表结点 */,10,void dfstravel(g,n) /* 深度优先遍历顶点个数为n的图g */,AdGraph gMAX+l;,int n;, int v;,for (v=1;v=n;v+) visitedv=0;,/*初始化辅助数组，表示所有顶点均末被访问过 */,for (v=1;v=n;v+) /*对图中所有未被访问过的顶点进行深度优先搜索*/,if (visitedv!=1) dfs(g,v),11,一个搜索实例,这就是古老而又经典的15数码难题：在4*4的棋盘上，摆有15个棋子，每个棋子分别标有1-15的某一个数字。棋盘中有一个空格，空格周围的棋子可以移到空格中。现给出初始状态和目标状态，要求找到一种移动步骤最少的方法。 看到这个题目，会发觉几乎每个搜索算法都可以解这个问题。而事实确实如此。,理解状态，算符，状态转移，状态空间，搜索策略,12,宽度优先搜索, 从结点v开始，给v标上已到达（或访问）标记此时称结点v还没有被检测，而当算法访问了邻接于某结点的所有结点时，称该结点被检测了。, 访问邻接于v且尚未被访问的所有结点这些结点是新的未被检测的结点。将这些结点依次放置到一未检测结点表(队列Q)中（末端插入） 。, 标记v已被检测。, 若未检测结点表为空，则算法终止；否则, 从未检测结点表的表头取一结点作为下一个待检测结点，,重复上述过程。,13,宽度优先检索算法,procedure BFS(v),/宽度优先检索G，它从结点v开始。所有已访问结点被标记为VISITED(i)=1。,VISITED(v)1;uv,/VISITED(n)是一个标示数组，初始值,VISITED(i)=0, 1,in,/,将Q初始化为空,/Q是未检测结点的队列/,loop,for 邻接于u的所有结点w do,if VISITED(w)=0 then,/w未被检测/,call ADDQ(w,Q),/ADDQ将w加入到队列Q的末端/,VISITED(w)1,/同时标示w已被访问/,endif,repeat,if Q 为空 then return endif,call DELETEQ(u,Q),/DELETEQ取出队列Q的表头，并赋给变量u/,repeat,end BFS,14,BFS、DFS、D_Search算法比较,BFS,：使用,队列,保存未被检测的结点。结点按照,宽度优先,的次序被访问和进、出队列。,DFS,：使用,栈,保存未被检测的结点，结点按照,深度优先,的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。,D_Search,：使用,栈,保存未被检测的结点，结点按照,宽度优先,的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。,1,2,3,4,5,6,7,8,无向图G,BFS检测序列：,1 2 3 4 5 6 7 8,DFS检测序列：,1 2 4 8 5 6 3 7,D_Search检测序列：,1 3 7 8 5 4 6 2,15,ACM实战三角形大战,题目描述,在如下图所示的棋盘上进行一场游戏。游戏有A、B两人参加。A先走，每人每次任选一条虚线填成实线。而如果某人填完一条线段与另两条实线组成了一个单位三角形，该三角形被标记为该游戏者所有，且该游戏得到一次奖励的机会，其中一步游戏如图所示。当18条线段被填充完毕后，拥有三角形多的玩家获胜。编程求出当两个人都采用最好的对策时最后取胜的玩家。,这是一个典型的博弈搜索题目。,16,分析,局面估价函数 给每个局面State规定一个估价函数值f，评价它对于己方的有利程度。胜利者的估价函数值为正无穷，而失败者的估价函数值为负无穷。假设没有和局。如何计算每一个局面的估价函数？,Max局面,Min局面,终结局面 如果双方都不能走，显然胜负已分。这就是最单纯的极大极小算法,对于一个局面，递归计算它所有子局面的估价函数值。,17,Function minmax(State,Player:integer):integer;,Begin,if WeWon then minmax:=正无穷；,else if WeLost then minmax:=负无穷；,else begin,min:=正无穷；,max:=负无穷；,for Move:=1 to MoveCount do,begin,NewState:= DoMove(state, move);,Value:=minmax(NewState,Next(Player);,if Valuemax then max:=value;,end;,If Player=MyProgram then minmax:=max;,If Player=Opponent then minmax:=min;,End;,End;,18,主观估价值,所有的f值不是正无穷就是负无穷。如果双方都采用最优策略，任意局面都是必胜的或必败的。但是在实际比赛中，完整地计算出一个局面的f值计算量太大，通常规定计算的最大递归深度maxDepth，如果达到了该深度，f值就是按照某种主观方法得出的估价值。只需要在过程参数里加上一个depth，当depth比较大的时候直接把局面估价函数作为minmax的返回值。,19,Alpha-Beta剪枝,举一个例子 对于一个max局面S，已经计算出了它的第一个子局面S1（min局面）的f值为5，而现在正在计算S的第二个子局面S2（min局面）的值。假设我们已经得知了S2的某个子局面的f值为2，那么S2的f值至多是2，比S1的f值要小。因此选择S1肯定比S2好，因马上停止计算S2。,20,优化方法,题目要求当两人都采用最好的策略时的获胜者，意味着搜索必须完全，但这样很慢。,方法1：如果一方已经拿到了5个三角形，实际上他已经肯定胜利了。,方法2：如果存在一些条填充以后可以获得三角形的线，就只考虑填充他们的情况。此法不可行。但可以大幅度地提高剪枝效果。如果以下一步能得到的三角形数作为权值，用前面提到的节点排序方法可以提高剪枝效果。,21,搜索方法中的剪枝优化,搜索的进程可以看作是从树根出发，遍历一棵倒置的树搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。,22,剪枝的原则,原则之一：正确性。,剪枝方法之所以能够优化程序的执行效率，正如前所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就都失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。,为了满足这个原则，我们就应当利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。当然，由必要条件的定义，我们知道，没有被剪枝不意味着一定可以得到正解（否则，也就不必搜索了）。,23,剪枝的原则-总结,原则之二,：,准确性。,在保证了正确性的基础上，对剪枝判断的第二个要求就是准确性，即能够尽可能多的剪去不能通向正解的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。因此，准确性可以说是剪枝优化的生命。,当然，为了提高剪枝判断的准确性，我们就必须对题目的特点进行全面而细致的分析，力求发现题目的本质，从而设计出优秀的剪枝判断方案。,24,剪枝的原则,原则之三：高效性。,一般说来，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的效率的提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性外，经常还需要提高判断操作本身的时间效率。,然而这就带来了一个矛盾：我们为了加强优化的效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能减小、甚至完全抵消提高判断准确性所能带来的优化效果，这恐怕也是得不偿失。很多情况下，能否较好的解决这个矛盾，往往成为搜索算法优化的关键。,25,方法,当然，我们在应用剪枝优化的时候，仅有上述的原则是不够的，还需要具体研究一些设计剪枝判断方法的思路。我们可以把常用的剪枝判断大致分成以下两类：,可行性剪枝。,最优性剪枝（上下界剪枝）。,26,剪枝方法,极端法 通过对当前节点进行理想式扩展，通过否定这样的理想情况来避免对当前节点的扩展。,调整法 基本思想是通过对子树的比较剪掉重复子树和明显不是最有前途的子树。,数学方法 利用专门知识剪枝，如在图论中借助连通分量，数论中借助模方程的分析等。,27,极端法剪枝例子-带宽,A,F,B,G,H,E,D,C,一个网格的例子,题目：给出一个n个节点的图和一个节点的排列，用节点带宽来表示某个节点和所有相邻节点在排列中的最远距离。用整个图的带宽来表示图中所有节点的节点带宽的最大值。编程求出任一个带宽最小的节点排列方案。,28,分析,比如ABCDEHFG（各个节点带宽分别为6，6，1，4，1，1，6，6）,比如ABCDGFHE（各个节点带宽分别为5，3，1，4，3，5，1，4）,本题最简单的做法是年历回溯法，即从左至右依次确定排列中的每个位置的节点。由于n个节点的排列的个数是n的阶乘，枚举量太大，应当剪枝。,29,如果在搜索到节点u的时候，u节点还有m个邻接点没有确定位置，那么对于节点u来说，最理想的情况就是这m个节点紧跟在u后面，这样的节点带宽为m，而其他任何非理想的带宽至少为m+1。如果m=k，即连理想情况都不能得到当前最优解的答案，显然应当剪枝。,30,调整法的剪枝例子小木棍,乔治有一些同样长的小木棍，他把这些木棍随意地砍成几段，直到每段的长都不超过50，现在，他想把小木棍拼接成原来的样子，但是却忘记了自己最开始有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他们找出原始木棍的最小可能长度。,31,分析,本题的数学模型是：给出n个数a1，a2，an，求出最小数k，使得这n个数分成若干组，每组的和都为k。显然，k必须为n个数之和m的约数，只需要从小到大枚举m的每个约数t（当然，t不能小于n个数中的任何一个），判断t是否可能为初始木棍长度就可以了。,32,使用深度优先搜索的办法来完成这一步工作。依次搜索每根原始木棍的组成，在每根木棍中依次搜索每一段的长度，规定必须按照木棍的第一段长度递增的顺序搜索每根木棍，在每根木棍中按照长度递减的顺序考虑每个可能的长度。,一旦发现某个木棍能够填满该原始木棍，就没有必要考虑其他木棍了。,33,数学方法的例子生日蛋糕,题目：7月17日是Mr.W的生日，ACMTHU为此要制作一个体积为Npi的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i（1iM）层蛋糕是半径为R,i,，高度为H,i,的圆柱。当iM时，要求R,i,R,i1,且H,i,H,i1,。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面的面积最小。令QSpi。请编程对给出的N和M，找出蛋糕的制作方案，使S最小。除Q外，其它所有数据都为正整数，N10000，M20）,34,分析,这是一道静态规划问题。可考虑使用搜索算法。由于深度M已定，可考虑使用深度优先算法。,当前体积大于N，或者当前面积已大于目前最优解面积的情况下，剪枝。,假设前i层的体积为Tpi，如果剩下的几层都取最小可能值，总体积仍然比N大，说明前i层的方案不可行。同理，如果剩下几层都取最大可能值，总体积仍然比N小，也应该剪枝。,35,ACM实战,Betsy旅行可行性剪枝的一个例子,一个正方形的小镇被分成N,2,个小方格，Betsy要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N，计算出Betsy能采用的所有的旅行路线的数目。,2=N=9,36,思路,我们用深度优先的回溯方法来解决这个问题：Betsy从左上角出发，每一步可以从一个格子移动到相邻的没有到过的格子中，遇到死胡同则回溯，当移动了N,2,-1步并达到左下角时，即得到了一条新的路径，继续回溯搜索，直至遍历完所有道路。,37,仅仅依照上述算法框架编程，时间效率极低，对N=6的情况无法很好的解决，所以，优化势在必行。对本题优化的关键就在于当搜索到某一个步骤时，能够提前判断出在后面的搜索过程中是否一定会遇到死胡同，而可行性剪枝正可以在这里派上用场。,38,剪枝方法,对于一条合法的路径，除出发点和目标格子外，每一个中间格子都必然有“一进一出”的过程。所以在搜索过程中，必须保证每个尚未经过的格子都与至少两个尚未经过的格子相邻（除非当时Betsy就在它旁边）。这里，我们是从微观的角度分析问题。,在第一个条件的基础上，我们还可以从宏观的角度分析，进一步提高剪枝判断的准确性。显然，在一个合法的移动方案的任何时刻，都不可能有孤立的区域存在。虽然孤立区域中的每一个格子也可能都有至少两个相邻的空的格子，但它们作为一个整体，Betsy已经不能达到。我们也应当及时判断出这种情况，并避免之。,39,40,“Betsy的旅行”的测试情况：（单位：秒）,N值,路径数,程序运行时间,无剪枝,第一种剪枝,第二种剪枝,两种剪枝,2,1,0.01,0.01,0.01,0.01,3,2,0.01,0.01,0.01,0.01,4,8,0.01,0.01,0.01,0.01,5,86,0.17,0.01,0.01,0.01,6,1770,41.25,0.44,0.33,0.11,7,88418,Very long,28.06,26.86,8.51,41,“Betsy的旅行”的程序（使用两种剪枝）,$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-,$M 65520,0,655360,program Betsy;,Betsy的旅行,说明:,1.为了便于测试计时，本程序采用命令行输入的方式。,2.为了处理的方便，程序中在地图的最外层补了一圈标志格。,3.程序中，将逻辑上相对独立的程序段用空行分开。,const,max=7;,本程序所能处理的最大的数据规模,delta:array1.4,1.2of shortint=(-1,0),(0,1),(1,0),(0,-1);,方向增量,42,var,map:array0.max+1,0.max+1of integer;,用于标记Betsy的移动路线的地图：,没有到过的位置标记-1，,最外层的标志格标记0，,其它格子标记Betsy到达该格子时的移动步数,left:array0.max+1,0.max+1of shortint;,标志数组：记录每个格子相邻的四个格子中尚未被Betsy经过的格子的数目,n:1.max;,地图边长,n2:integer;,N*N,s:longint;,累加器,记录Betsy的移动路线的总数,procedure init;,读入数据，初始化,var,i:integer;,循环变量,temp:integer;,临时变量,begin,val(paramstr(1),n,temp);,从命令行读入n,n2:=n*n;,fillchar(map,sizeof(map),255);,for i:=0 to n+1 do begin,map0,i:=0;,mapi,0:=0;,mapn+1,i:=0;,mapi,n+1:=0;,end;,map1,1:=1;,以上程序段为对地图的初始化,43,fillchar(left,sizeof(left),4);,for i:=2 to n-1 do begin,left1,i:=3;leftn,i:=3;,lefti,1:=3;lefti,n:=3;,end;,left1,1:=2;left1,n:=2;leftn,1:=3;leftn,n:=2;,dec(left1,2);dec(left2,1);,以上程序段是对标志数组的初始化,s:=0;,累加器清零,end;,procedure change(x,y,dt:integer);,给(x,y)相邻的四个格子的left标志值加上dt,设标志时，dt取-1；回溯时，dt取1,var,k:integer;,循环变量,a,b:integer;,临时坐标变量,begin,for k:=1 to 4 do begin,a:=x+deltak,1;b:=y+deltak,2;,inc(lefta,b,dt);,end;,end;,44,procedure expand(step,x,y:integer);,搜索主过程：搜索第step步，扩展出发位置(x,y),var,nx,ny:integer;,Betsy的新位置,dir:byte;,Betsy的移动方向,function able(x,y:integer):boolean;,判断Betsy是否可以进入(x,y),begin,able:=not(mapx,y-1)or(stepn2)and(x=n)and(y=1);,end;,function cut1:boolean;,剪枝判断1,var,i:integer;,循环变量,a,b:integer;,临时坐标变量,begin,for i:=1 to 4 do begin,a:=x+deltai,1;b:=y+deltai,2;,if (mapa,b=-1)and(anx)or(bny)and(lefta,bn2)and(x=n)and(y=1) then begin,搜索到最底层,累加器加1,inc(s);,exit;,end;,46,for dir:=1 to 4 do begin,循环尝试4个移动方向,nx:=x+deltadir,1;ny:=y+deltadir,2;,if able(nx,ny) then begin,if cut1 then continue;,调用剪枝判断1,if cut2 then continue;,调用剪枝判断2,change(nx,ny,-1);,mapnx,ny:=step;,expand(step+1,nx,ny);,递归调用下一层搜索,mapnx,ny:=-1;,change(nx,ny,1);,end;,end;,end;,begin,主程序,init;,初始化,expand(2,1,1);,调用搜索过程,writeln(The number of tours is ,s);,输出结果,end.,47,ACM实战-,最优性剪枝的一个例子-最少乘法次数,48,49,优化,50,优化之二：着眼于估价函数的“生命”准确性。我们可以利用加法在奇偶性上的特点的推广，使估价函数在某些情况下的准确性得到一定的提高。,优化之三：我们新建立的这个估价函数虽然准确性稍有提高，但时间复杂度也相应提高。为了提高剪枝的效率，我们可以使用一种“逐步细化”的技巧，即先使用一次原先的估价函数（快而不准）进行“过滤”，再使用新的估价函数（稍准但较慢）减少“漏网之鱼”，以求准确性和运行效率的平衡。,51,优化之四：我们可以在搜索之前将分解质因数，对每个质因数先使用上述搜索方法求解（如某个质因数仍太大，还可以将其减1，再分解），即相当于将构造数列的过程，划分成若干阶段处理。这样得到的结果虽然不一定是全局的最优解，却可以作为初始设定的优度下界，使后面的全局搜索少走很多弯路。事实上，该估计方法相当准确，在很多情况下都能直接得到最优解，使程序效率得到极大提高。,52,53,部分测试数据的运行时间：（单位：秒）,N值,乘法次数,运行时间,程序1,程序2,程序3,程序4,程序5,程序6,程序7,127,10,0.22,0.22,0.05,0.06,0.06,0.01,0.16,191,11,3.52,3.90,0.83,0.55,0.55,0.27,1.75,382,11,13.02,13.29,1.05,0.94,0.66,0.33,2.69,511,12,Very long,Very long,0.82,5.66,0.33,0.27,1.81,635,13,46.96,40.37,20.65,19.61,10.06,8.13,Overflow,719,13,45.59,39.11,45.64,13.45,39.11,6.64,27.35,1002,13,11.81,10.65,2.74,3.46,1.10,0.99,6.26,1023,13,Very long,Very long,2.66,Very long,1.04,0.88,6.15,1357,13,9.51,6.98,5.93,5.44,3.40,2.74,13.35,1894,14,44.87,37.24,13.89,15.49,6.37,4.61,23.68,（测试环境：Pentium Pro 233MHz/64MB）,54,“最少乘法次数”的程序,$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-,$M 65520,0,655360,program LeastMultiply;,最少乘法次数,说明:,1.为了测试计时的方便,本程序从命令行读入n值。,2.程序结束后，在output.txt中给出执行乘法的方式，并给出总的乘法次数。,3.在搜索过程中，由于与动态规划结合，所以在没有搜索到底层的时候，就可以得到最优解的数列长度(但此时没有得到完整的最优幂次数列)，所以在搜索结束后，程序中调用formkeep过程在keep中生成完整的构造数列。,4.由于程序中的搜索过程生成的是最优幂次数列，而没有直接给出乘法的进行方式，所以在输出结果的过程output中，对其进行了转换。,5.为了尽可能的提高程序的时间效率，程序中有几处细节上的优化，请参见程序内的注释。,6.程序中，逻辑上相对独立的程序段用空行分开。,55,const,max=20;,数列最大长度,maxr=2000;,动态规划计数数组的最大长度(输入的n不能超过maxr的2倍),mp=100;,预处理估价时,可以直接搜索处理的数的范围上限,power2:array0.12of integer= (1,2,4,8,16,32,64,128,256,512,1024,2048,4096); ,2的方幂,type,atype=array0.maxof integer;,用于记录构造的幂次数列的数组类型，0号元素记录数列长度,var,n:integer;,读入的目标数字,time:array0.maxrof integer;,动态规划计数数组，timei表示在当前构造数列的基础上，组成数i至少需要的加数个数,range:integer;,使用动态规划处理的范围：range=n/2,a:atype;,搜索中记录数列,kp:atype;,预处理估界时，记录结果数列的临时数组,keep:atype;,记录最优结果数列的数组,best:integer;,当前最优解,f:text;,输出文件,56,procedure init;,初始化,var,temp:integer;,临时变量,begin,val(paramstr(1),n,temp);,从命令行读入n,keep0:=1;,keep1:=1;,best:=maxint;,最优数列长度的初值,assign(f,output.txt);,连接输出文件,end;,57,procedure search(n:integer;var best:integer;var keep:atype);,搜索主过程,搜索之前，给出的搜索目标为n；,在best中存放搜索前已经给出的优度下界；,在keep中存放初始优度下界对应的最优幂次数列。,搜索结束之后，在best中给出的是构造的最优幂次数列的长度,即最少乘法次数加1；,在keep中给出所构造的最优幂次数列。,var,kn:integer;,n所含的2的方幂的次数,i:integer;,循环变量,function getk(num:integer):integer;,求num所含的2的方幂次数,即论文中所设的k(num),var,i:integer;,循环变量,begin,i:=0;,while not odd(num) do begin,num:=num shr 1;,inc(i);,end;,getk:=i-1;,end;,58,procedure find(step:integer);,递归搜索过程,var,i:integer;,循环变量,k:integer;,本层搜索的循环范围上限,function ok(num:integer):boolean;,判断数num能否在当前被构造出来,为了提高程序的效率，这里利用了动态规划的结果,var,i,j:integer;,循环变量,begin,if num=range then begin,待判断数num在n/2以内,ok:=(timenum=2);,直接利用最少需要的加数是否为2来判断,exit;,end;,for i:=step-1 downto 1 do begin,if ai+airange then p:=range;,for i:=astep-1+1 to p do begin,timei:=timei-astep-1+1;,目标函数赋初值,for j:=step-2 downto 2 do,决策枚举,if timei-aj+1timei then timei:=timei-aj+1;,end;,end;,function h(num:integer):byte;,最初的简单估价函数h,var,i:integer;,循环计数变量,begin,i:=0;,while num=best then cut1:=true else cut1:=false;,end;,function cut2:boolean;,使用改进的估价函数的剪枝判断,var,pt:integer;,k(astep)的值，即astep中所含的2的幂的次数,rest:integer;,新构造的数列中，满足k(rest)=k(n)的数,i:integer;,循环计数变量,begin,if h(astep+astep-1)+step+1kn then rest:=astep-1,else,if pt=kn then rest:=astep,else rest:=maxint;,给rest赋初值，以防新构造的数列中的所有数的k值都小于k(n),i:=0;,repeat,astep+i+1:=astep+i shl 1;,inc(i);,if pt+i=kn then rest:=astep+i;,until astep+in;,dec(i);,以上程序段为构造数列的过程,if (n-astep+irest)and(step+i+2=best) then cut2:=true else cut2:=false;剪枝判断,end;,62,begin,Find,if astep-1+astep-1=n then begin,数列中的当前最大数已经超过n/2，则直接引用动态规划的结果,if timen-astep-1+step-1best then begin,判断出解,best:=timen-astep-1+step-1;,keep:=a;,end;,exit;,end;,k:=astep-1+astep-1;,计算astep的可选范围的上限,evltime;,调用动态规划子过程,inc(a0);,for i:=k downto astep-1+1 do,if ok(i) then begin,if in/2则直接引用动态规划的结果，所以最优结果数列的最后一,部分实际上并未得到，所以需要在本过程中将其补充完整。,这里还需要使用递归和回溯（实际上就是一个小规模的搜索），不过，由于动态规划给出的结,果表示的是从已有数列中，选出最少的数求和而得到n，所以对这些数是可以定序的。,var,found:boolean;,找到最优数列的标志,procedure check(from,left:integer);,回溯法生成最优数列的最后一部分,from表示当前层内循环的上界(用于定序)，left表示剩余的需要通过求和而得到的数,var,i:integer;,循环变量,begin,if keep0=best then begin,if left=0 then found:=true;,找到最优数列,exit;,end;,64,inc(keep0);,for i:=from downto 1 do,循环枚举数列中的数,if keepi=left then begin,keepkeep0:=keepkeep0-1+keepi;,check(i,left-keepi);,调用下一层搜索，但所使用的数不能再超过keepi(定序),if found then exit;,end;,dec(keep0);,end;,begin,FromKeep,found:=false;,check(keep0,n-keepkeep0);,调用搜索过程,end;,begin,Search,kn:=getk(n);,计算k(n),time0:=0;,time1:=1;,a0:=1;,a1:=1;,range:=n div 2;,以上程序段为搜索前的初始化,find(2);,调用搜索过程,formkeep;,搜索结束后，在keep中生成完整的构造数列,end;,65,function guess(n:integer):integer;,递归方式实现的预处理估界,说明：,1.子程序guess运行结束后，返回的值即为对n估价的结果；同时，在keep数组中得到对应的数列。,2.为了能够使估价尽可能准确，guess中同时考虑了两种分解策略，即使用了回溯结构。,3.由于每次递归调用guess，其最终结果都必须记入keep数组，所以每次guess运行都只操作keep数组的一部分，同时还要借助于kp,kpt等临时数组。,var,num:integer;,将n中的所有2的因子都提出后剩下的数,pfact:integer;,表示num的素因子的变量,best:integer;向下调用时记录返回的估价值,b2:integer;,记录num中的2的因子的数目,s:integer;,对n的估价步数,i:integer;,循环变量,sq:integer;,num的平方根的整数部分，分解素因子时作为上界,s1,k2,k:integer;,临时变量,kpt:atype;,临时记录最优结果数列,66,begin,num:=n;,b2:=0;,while not odd(num) do begin,num:=num div 2;,inc(b2);,inc(keep0);,keepkeep0:=power2b2;,end;,s:=b2+1;,k2:=keep0;,以上程序段的作用是将n中所含的2的因子全部提出，剩下的部分即num,if num=mp then begin,如果num足够小(小于等于mp)，则直接调用搜索过程处理,best:=maxint;,search(num,best,kp);,对n调用搜索过程，得到的数列存放在kp中,inc(s,best-1);,for i:=2 to best do keepi+keep0-1:=kpi;,inc(keep0,best-1);,end,else begin,使用估价方法处理,k:=keep0;,best:=guess(num-1);,递归调用guess,keepkeep0+1:=keepkeep0+1;,inc(keep0);,inc(s,best);,以上程序段为估价的第一种策略：将num减1后，对num-1进行估价,67,sq:=trunc(sqrt(num);,pfact:=3;,while (pfact0) do inc(pfact,2);,if pfact=sq then begin,kpt:=keep;,keep0:=k2;,s1:=b2+1;,以上程序段为使用第二种策略前的初始化,k:=keep0;,best:=guess(pfact);,inc(s1,best-1);,以上程序段中递归调用guess，对质因数pfact进行估价,k:=keep0;,best:=guess(num div pfact);,for i:=k+1 to keep0 do keepi:=pfact*keepi;,inc(s1,best-1);,以上程序段对num/pfact进行估价,if s1s then s:=s1 else keep:=kpt;,比较两种策略结果的优劣,end;,以上程序段是估价的第二种策略：将num分解出一个较小的质因数后再处理。,估价的结果存放在s1中，使用kpt临时存放第一种策略所构造的数列。,end;,68,for i:=k2+1 to keep0 do keepi:=keepi*power2b2;,guess:=s;,返回估价结果,end;,procedure output;,输出结果,var,i,j,k:integer;,循环变量,begin,rewrite(f);,writeln(f,X1);,for i:=2 to best do begin,for j:=1 to i-1 do begin,for k:=j to i-1 do,if keepj+keepk=keepi then break;,if keepj+keepk=keepi then break;,end;,writeln(f,X,i,=X,j,*X,k);,end;,writeln(f,Times of multiplies=,best-1);,close(f);,end;,begin,主程序,init;,读入数据，初始化,best:=guess(n);,调用预处理估界,search(n,best,keep);,调用搜索主过程,output;,输出结果,end.,69,