最大加权区间调度问题详解.docx

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.10M 资料格式：docx 举报版权申诉

9083af74-529d-4272-95ed-54d316b43320.docx.pdf-第1页.png

第1页 / 共6页

9083af74-529d-4272-95ed-54d316b43320.docx.pdf-第2页.png

第2页 / 共6页

9083af74-529d-4272-95ed-54d316b43320.docx.pdf-第3页.png

第3页 / 共6页

9083af74-529d-4272-95ed-54d316b43320.docx.pdf-第4页.png

第4页 / 共6页

9083af74-529d-4272-95ed-54d316b43320.docx.pdf-第5页.png

第5页 / 共6页

9083af74-529d-4272-95ed-54d316b43320.docx.pdf-第6页.png

第6页 / 共6页

文本预览

高级程序设计动态规划部分论文班级：2015 级软件工程 6 班姓名：孙吉鹏 ID：201500301155 最大加权独立集问题题目要求：求区间图的最大加权独立集。（选择一部分互不重叠的区间，使得被选出来的区间权重之和最大）题目分析：图一这类问题可以归结为区间调度问题，这是其中最普通的一类，即加权最大区间调度问题，其求解思路可以通过求最多区间调度（贪婪算法 dp[i-1] = dp[i]），无权最大区间（权值为 1 的动态规划）依次发展过来，其具体思路分析详见 http://blog.csdn.net/yutianzuijin/article/details/45116705#。我也从博客中转载了这篇文章，http://blog.csdn.net/lukas_sun/article/details/53770959。向原作者致敬！

题目求解：求解最大权值区间的必要条件就是各最优区间互不冲突，这是这类调度问题共同的影子，只不过它的目标是让各区间的权值和最大。和所有这种规划问题相同，我们需要对所有区间进行排序，排序原则为结束时间的先后，因为用开始时间排序无法得到各区间明确界限。首先规定几个记号 O（j）：需求区间{ 1……j }的最优解集 p ( n ): 最大的满足不与第 n 个区间冲突的区间号 OPT( j ): O ( j )的最优解值。由此定义可以分析得到第 p(n)+1, p(n)+2 ,p(n)+3…………n-1 个区间都与第 n 个区间冲突，所以 O 一定包含对需求区间{1，……p(n)}的最优解（否则可以将其替换成最优解而不影响需求区间 n），由于 p(n) <= n-1，所以如果 n 不包含在 O 里，则其可以转化为对需求区间 {1……n-1}的求解。则我们的递推模型可以以是否选择第 j 个区间为构造依据。 OPTj = 0 按照此递推公式可知求解过程： + ,(−1) (=0) (>0) OPT（3）= 3 （2，3） OPT（5）= 5+OPT（0）= 5 （1，5） OPT（8）= 6+OPT（4）= 6 +OPT（3）= 9 （2，3）、（4，8） OPT（10）= 1+OPT（9） = 1+OPT（8）=10 （2，3）、（4，8）、（9，10） OPT（12）= 10+OPT（6）= 10+OPT（5）>10 = 15 OPT（14）= 0+OPT（13）= OPT（12）= 15

OPT（15）= 7+OPT（11）= 7+OPT（10）= 17>OPT( 14 ) OPT（17）= OPT（15）> = 12+OPT (7) = 17 OPT（18）= 4+OPT（16）= 4+OPT（15）= 21>OPT(17) 综上，该图最大权和为 21，在其递归算法中的 “if+ >(−1) ” 判断条件后将所选的边加入到边的数组中，调用结束后输出这个数组可以得到所选边集： {（2，3）（4，8）（9，10）（11，15）（16，18）} 若 Max（）函数和递归判断中的”>”换为“>=”虽然使最大权值不变但可使所选边集发生变化，如此例中 OPT（17）= 17，但所选边集为 {（1，5）（7，17）} 不同于改动前的边集： {（2，3）（4，8）（9，10）（11，15）} 题目扩展：这个问题可以转化为求最大加权独立集的问题，这种图论问题广泛应用于 DNA 测序等方面，且为 NP 问题，求解困难。即将每条线段转化为图中的一个顶点，将有重叠部分的线段设置为相邻的顶点，每条线段的权值在顶点数据中体现，则上述问题转换为选择图中不相邻的最大权值顶点集。转换后的图如图二所示。

16,18 4 13,14 0 2,3 3 1,5 5 4,8 6 7,17 12 6,12 10 图二 11,15 7 9,10 1 参考文献《算法设计》第 6 章动态规划 Jon Kleinberg ,Eva Tardos 清华大学出版社《动态规划》ppt 姜海涛附录求最大权值部分实现代码参考姚光超博主的代码实现 const int MAX_N=100000; //输入 int N,S[MAX_N],T[MAX_N]; //用于对工作排序的 pair 数组 pair itv[MAX_N];

void solve() { //对 pair 进行的是字典序比较，为了让结束时间早的工作排在前面，把 T 存入 first，// 把 S 存入 second for(int i=0;i

int nonOverlap = lower_bound(itv, itv[i].second)-1; if (nonOverlap >= 0) max = dp[nonOverlap] + (itv[i].first-itv[i].second)*V[i]; else max = (itv[i].first-itv[i].second)*V[i]; //do not select the ith interval dp[i] = max>dp[i-1]?max:dp[i-1]; } printf(“%d\n”,dp[N-1]); }

分享到：

赞收藏

资料库

最大加权区间调度问题详解.docx

相关推荐

课程资源

热门标签

最新资料