《回溯法习题》PPT课件.ppt

1,课程安排,第5章 回溯法习题课,3,第5章 回溯法习题,子集和问题 最小长度电路板排列问题 最小重量机器设计问题 运动员最佳匹配问题 无分隔符字典问题 无和集问题 n色方柱问题 整数变换问题 拉丁矩阵问题 排列宝石问题 重复拉丁矩阵问题 罗密欧与朱丽叶的迷宫问题 工作分配问题 独立钻石跳棋问题 智力拼图问题 布线问题 最佳调度问题 无优先级运算问题,世界名画陈列馆问题 世界名画陈列馆问题（不重复监视） 魔方问题 魔方(Rubiks Cube)问题 算24点问题 算m点问题 双轨车皮编序问题 多轨车皮编序问题 部落卫队问题 虫蚀算式问题 完备环序列问题 离散01串问题 喷漆机器人问题 子集树问题 0-1背包问题 排列树问题 一般解空间搜索问题 最短加法链问题 n2-1谜问题,4,第5章 回溯法习题,子集和问题 运动员最佳匹配问题 最佳调度问题 离散01串问题,5,子集和问题的一个实例为S,t。其中，S= x1,x2,xn 是一个正整数的集合，c是一个正整数。 子集和问题判定是否存在S 的一个子集S1，使得 试设计一个解子集和问题的回溯法。 编程任务： 对于给定的正整数的集合S= x1,x2,xn和正整数c，编程计算S 的一个子集S1，使得,5-1 子集和问题,6,子集和问题,数据输入： 第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S 中的元素。 结果输出： 输出子集和问题的解。当问题无解时，输出“No solution! ”。 输入示例 5 10 2 2 6 5 4 输出示例 2 2 6,7,子集和问题算法,类似于装载问题 bool Subsum:backtrack(int i) /从1开始调用 if (in) /计算完毕 for (int j=1; j=n; j+) bestxj = xj; /记录最优解 bestw = cw; if (bestw=c) return true; /满足条件(找到了) else return false; ,8,子集和问题算法,r -= wi; /剩余大小 if (cw+wibestw) /上界函数 xi = 0; /右子树 if (backtrack(i+1) return true; r += wi; /右子树无最优解 return false; ,9,5-4 运动员最佳匹配问题,问题描述： 羽毛球队有男女运动员各n 人。 给定2 个nn 矩阵P 和Q。Pij 是男运动员i 和女运动员j 配对组成混合双打的男运动员竞赛优势；Qij 是女运动员i 和男运动员j 配合的女运动员竞赛优势。 由于技术配合和心理状态等各种因素影响，Pij 不一定等于Qji 。 男运动员i 和女运动员j 配对组成混合双打的男女双方竞赛优势为Pij*Qji 。 设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。,10,运动员最佳匹配问题,编程任务： 设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 数据输入： 第一行有1 个正整数n (1n20)。接下来的2n 行，每行n 个数。前n 行是p，后n 行是q。 结果输出: 男女双方竞赛优势的总和的最大值。,输入示例： 3 10 2 3 2 3 4 3 4 5 2 2 2 3 5 3 4 5 1,输出示例： 52,p,q,11,运动员最佳匹配问题,结果输出: 男女双方竞赛优势的总和的最大值。 样例分析,输入示例： 3 10 2 3 2 3 4 3 4 5 2 2 2 3 5 3 4 5 1,输出示例： 52,p,q,r,10*2+4*5+4*3=52,只有一个下标是变化的,12,运动员最佳匹配问题算法,解空间是一棵排列树 void pref:Backtrack(int t) /从1开始回溯 if (tn) Compute(); /构成1次全排列 else for (int j=t; j=n; j+) /从结点t到叶结点 swap(rt, rj); /将结点j作为当前结点 Backtrack(t+1); swap(rt, rj); /将结点还回去 ,13,运动员最佳匹配问题算法,void pref:Compute(void) /计算当前排列的竞赛优势 for (int i=1,temp=0;ibest) /是更好的值？ best = temp; for (int i=1; i=n; i+) /构造最优解 bestri = ri; ,14,运动员最佳匹配问题算法,15,运动员最佳匹配问题算法,main()中的前半部分：,16,5-17 最佳调度问题,假设有n 个任务由k 个可并行工作的机器完成。完成任务i 需要的时间为ti。试设计一个算法找出完成这n 个任务的最佳调度，使得完成全部任务的时间最早。 编程任务： 对任意给定的整数n 和k，以及完成任务i 需要的时间为ti，i=1n 。编程计算完成这n个任务的最佳调度。,17,最佳调度问题,数据输入： 第一行有2 个正整数n 和k。第2 行的n 个正整数是完成n 个任务需要的时间。 结果输出: 完成全部任务的最早时间。 输入示例 7 3 2 14 4 16 6 5 3 输出示例 17,18,4.7 多机调度问题,按算法greedy产生的作业调度如下图所示，所需的加工时间为17。 最长处理时间作业优先, 机器空闲时间最长优先安排,19,最佳调度问题算法,void search(int dep) /初值为1 if (dep=n) /形成一种调度方案 int temp = comp(); /计算完成任务的时间 if (tmpbest) best = tmp; /更新最优解 return; for (int i=0; ik; i+) /对每台机器回溯 leni += tdep; /安排任务dep(左子树) if (lenibest) search(dep+1); leni -= tdep; /右子树 ,20,最佳调度问题算法,计算完成任务的时间 int comp() int tmp = 0; /在k台机器中查找最大值 for (int i=0; itmp) tmp = leni; return tmp; ,21,5-30 离散01串问题,(n,k)01 串定义为：长度为n 的01 串，其中不含k 个连续的相同子串。对于给定的正整数n 和k，计算(n,k)01 串的个数。 编程任务： 对于给定的正整数n 和k，计算(n,k)01 串的个数。 数据输入： 第一行有2 个正整数n 和k，1k，n40。 结果输出: (n,k)01 串的个数。 输入示例 2 3 输出示例 4,3 3 6 3 10 3 16,22,5-30 离散01串问题,具有对称性，只要考察首字符为0的情况，将找到的符合条件的0-1串的个数加倍。 void backtrack(int lev) /lev从2开始 if (levn) /一种情况构造完毕 tot += 2; /个数加倍 return ; for (int i=0; i2; i+) bstrlev = i; / 0，1 /满足条件就回溯 if ( bstrok(lev) ) backtrack(lev+1); ,23,5-30 离散01串问题,bool bstrok(int lev) /第lev位 for (int i=0; i0) /下标必须大于0 if (same() return false; /是相同的 for (int i=0; ik; i+) xi -= i+1; /每隔i个位置 return true; ,24,5-30 离散01串问题,/判断是否相同 bool same() int len = x0 - x1; /计算位置差 for (int i=0; ilen; i+) /搜索每一位 for (int j=1; jk; j+) /每次搜索k位 if (bstrxj+i!=bstrxj-1+i)