第五章回溯法-四川农业大学.ppt

5.9 旅行售货员问题 曾记否？前面已经说过了。 解空间 排列树 复杂度分析 算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)。 整个算法的计算时间复杂性为O(n!)。 5.10 圆排列问题 5.10.1 问题描述 给定n个大小不等的圆c1,c2,…,cn，要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。 圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。 例如，当n=3，且所给的3个圆的半径分别为1,1,2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+4√2。 回溯法效率分析 回溯算法效率在很大程度上依赖于以下因素 (1)产生x[k]的时间； (2)满足显约束的x[k]值的个数； (3)计算约束函数constraint的时间； (4)计算上界函数bound的时间； (5)满足约束函数和上界函数的所有x[k]的个数。 约束 好的约束函数能显著地减少所生成的结点数，但往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。 回溯法效率分析 重排原理 对于许多问题而言，在有哪些信誉好的足球投注网站试探时选取x[i]的值顺序是任意的。在其他条件相当的前提下，让可取值最少的x[i]优先。 从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。 回溯法效率分析 从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。 从第1层剪去1棵子树，却只消去8个3元组。 前者的效果明显比后者好。 没有了 5.12 连续邮资问题 连续邮资问题描述 假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。 连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。 例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。 70=32+32+3+3 69=32+22+15 …… 5.12 连续邮资问题 问题分析 解向量 用n元组x[1:n]表示n种不同的邮票面值，并约定它们从小到大排列。x[1]=1是惟一的选择，此时最大连续邮资空间为[1:m]；x[2]的可取值范围是[2:m+1]。 可行性约束函数 一般情况下，已选定x[1:i-1]，最大连续邮资区间是[1:r]，接下来x[i]的可取值范围是[x[i-1]+1:r+1]。 5.12 连续邮资问题 如何确定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++; * void Triangle::Backtrack(int t) { if ((counthalf)||(t*(t-1)/2-counthalf)) return; if (tn) sum++; else for (int i=0;i2;i++) { p[1][t]=i; count+=i; for (int j=2;j=t;j++) { p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; count+=p[j][t-j+1]; } Backtrack(t+1); for (int j=2;j=t;j++) count-=p[j][t-j+1]; count-=i; } } * bool Queen::Place(int k) { for (int j=1;jk;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) { if (tn) sum++; else for