算法第5章课件.ppt

2021/2/21 * 连续邮资问题 假设国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。 例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。 2021/2/21 * 连续邮资问题 解向量:用n元组x[1:n]表示n种不同的邮票面值,并约定它们从小到大排列。x[1]=1是唯一的选择。 可行性约束函数:已选定x[1:i-1],最大连续邮资区间是[1:r],接下来x[i]的可取值范围是[x[i-1]+1:r+1]。 如何确定r的值? 计算X[1:i]的最大连续邮资区间在本算法中被频繁使用到,因此势必要找到一个高效的方法。考虑到直接递归的求解复杂度太高,我们不妨尝试计算用不超过m张面值为x[1:i]的邮票贴出邮资k所需的最少邮票数y[k]。通过y[k]可以很快推出r的值。事实上,y[k]可以通过递推在O(n)时间内解决: for (int j=0; j= x[i-2]*(m-1);j++) if (y[j]m) for (int k=1;k=m-y[j];k++) if (y[j]+ky[j+x[i-1]*k]) y[j+x[i-1]*k]=y[j]+k; while (y[r]maxint) r++; 2021/2/21 * 连续邮资问题 子树: for(int j=x[i-1]+1;j=r;j++){ x[i]=j; Backtrack(i+1,r); for(int k=1;k=maxl;k++) y[k]=z[k]; } 2021/2/21 * 回溯法效率分析 通过前面具体实例的讨论容易看出,回溯算法的效率在很大程度上依赖于以下因素: (1)产生x[k]的时间; (2)满足显约束的x[k]值的个数; (3)计算约束函数constraint的时间; (4)计算上界函数bound的时间; (5)满足约束函数和上界函数约束的所有x[k]的个数。 好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此,在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。 2021/2/21 * 重排原理 对于许多问题而言,在有哪些信誉好的足球投注网站试探时选取x[i]的值顺序是任意的。在其它条件相当的前提下,让可取值最少的x[i]优先。从图中关于同一问题的2棵不同解空间树,可以体会到这种策略的潜力。 图(a)中,从第1层剪去1棵子树,则从所有应当考虑的3元组中一次消去12个3元组。对于图(b),虽然同样从第1层剪去1棵子树,却只从应当考虑的3元组中消去8个3元组。前者的效果明显比后者好。 (a) (b) 2021/2/21 * 2021/2/21 * 学习要点 理解回溯法的深度优先有哪些信誉好的足球投注网站策略。 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架 2021/2/21 * 通过应用范例学习回溯法的设计策略。 （1）装载问题; （2）批处理作业调度; （3）符号三角形问题 （4）n后问题; （5）0-1背包问题; （6）最大团问题; （7）图的m着色问题 （8）旅行售货员问题 （9）圆排列问题 （10）电路板排列问题 （11）连续邮资问题 2021/2/21 * 有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。 回溯法 回溯法的基本做法是有哪些信誉好的足球投注网站,或是一种组织得井井有条的,能避免不必要有哪些信誉好的足球投注网站的穷举式有哪些信誉好的足球投注网站法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中,按深度优先策略,从根结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的有哪些信誉好的足球投注网站,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略有哪些信誉好的足球投注网站。 2021/2/21 * 问题的解空间 问题的解向量:回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 注意:同一个问题可以有多种表示,有些表示方法更简单,所需表示的状态空间更小（存储量少,有哪些信誉好的足球投注网站方法简单）。 n=3时的0-1背包问题用完全二叉树表示的解空间,其解空间为 {(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)} 定义了问题的解空间后,还应将解空间很好地组织起来,使得能用回溯法方便地有哪些信誉好的足球投注网站整个解空间,通常将解空间组织成树或图