<style type="text/css">
<!--
@page
{margin:2cm}
p
{margin-bottom:0.21cm;
direction:ltr;
color:#000000;
text-align:justify;
widows:0;
orphans:0}
p.western
{font-family:"Times New Roman",serif;
font-size:10pt}
p.cjk
{font-family:"宋体","SimSun";
font-size:10pt}
p.ctl
{font-family:"Times New Roman",serif;
font-size:12pt}
-->
</style>
基于贪心算法的几类区间覆盖问题
(1)区间完全覆盖问题
问题描述:给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间),求最少使用多少条线段可以将整个区间完全覆盖
样例:
区间长度8,可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]
解题过程:
1将每一个区间按照左端点递增顺序排列,拍完序后为[1,4],[2,4],[2,6],[3,5],[3,6],[3,7],[6,8]
2设置一个变量表示已经覆盖到的区域。再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中,右端点最大的线段在加入,直到已经覆盖全部的区域
3过程:
假设第一步加入[1,4],那么下一步能够选择的有[2,6],[3,5],[3,6],[3,7],由于7最大,所以下一步选择[3,7],最后一步只能选择[6,8],这个时候刚好达到了8退出,所选区间为3
4贪心证明:
需要最少的线段进行覆盖,那么选取的线段必然要尽量长,而已经覆盖到的区域之前的地方已经无所谓了,(可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方),那么真正能够使得线段更成的是右端点,左端点没有太大的意义,所以选择右端点来覆盖
(2)最大不相交覆盖
问题描述: 给定一个长度为m的区间,再给出n条线段的起点和终点(开区间和闭区间处理的方法是不同,这里以开区间为例),问题是从中选取尽量多的线段,使得每个线段都是独立的,就是不和其它有任何线段有相交的地方
样例:
区间长度8,可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]
解题过程:
对线段的右端点进行升序排序,每加入一个线段,然后选择后面若干个(也有可能是一个)右端点相同的线段,选择左端点最大的那一条,如果加入以后不会跟之前的线段产生公共部分,那么就加入,否则就继续判断后面的线段
1 排序: 将每一个区间按右端点进行递增顺序排列,拍完序后为[1,4],[2,4],[2,6],[3,5],[3,6],[3,7],[6,8]
2 第一步选取[2,4],发现后面只能加入[6,8],所以区间的个数为2
3 贪心证明: 因为需要尽量多的独立的线段,所以每个线段都尽可能的小,对于同一右端点,左端点越大,线段长度越小。那么为什么要对右端点进行排序呢?如果左端点进行排序,那么右端点是多少并不知道,那么每一条线段都不能对之前所有的线段进行一个总结,那么这就明显不满足贪心的最有字结构了。
(3)区间选点问题
问题描述:给定一个长度为m的区间,再给出n条线段和这n条线段需要满足的要求(要求是这n条线段上至少有的被选择的点的个数),问题是整个区间内最少选择几个点,使其满足每一条线段的要求.
样例:略
解题过程:将每个线段按照终点坐标进行递增排序,相同终点的前点坐标大的在前面,一个个将其满足
贪心证明:
要想使得剩下的线段上选择的点最少,那么就应该尽量使得已经选择了的点尽量能在后面的线段中发挥作用,而我们是从左往右选择线段的,那么要使得选取的点能满足后面线段的要求,那么必须是从线段的有端点开始选点,那么问题(2)一样涉及到一个问题,如果是按照线段的左端点对线段进行排序的话,不知道右端点的话,每一条线段都不能对之前已经操作过的所有线段进行一个总结,那么这就同样不满足贪心算法的最优子结构性质了。
可以解决的实际问题:数轴上面有n个闭区间[a,b],取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)
分享到:
相关推荐
贪心法求解图的着色问题C++源代码,可直接编译运行。 greedy.
贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个...
基于贪心法求解单源最短路径问题 完整实验报告,结尾有实验代码
使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
本压缩文档包含三个文件:用贪心法解决TSP问题可执行源代码,word文档报告,实验测试数据
代码中给出了用贪心法解决活动安排问题的集中方案。。用c++实现的,希望能给您帮助。
为C语言课程设计写的基于贪心法的背包问题,包含全部4种贪心策略
算法设计实验报告,包括:贪心法求解背包问题的基本思想、动态规划法求解0/1背包问题的基本思想及各自的时间复杂度分析,两种问题的区别,C++实现代码,运行截图,实验心得。
实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0编译通过 有几个实验为C语言代码 还有...
背包问题的贪心法求解.exe
热心学姐来送福利啦哈哈哈哈哈哈哈哈哈哈哈哈哈,西北农林科技大学的算法分析实验报告,
数据结构TSP问题贪心法求解.doc
用贪心法的思想,设计算法编程解决如下现实问题:码头上有n艘船舶同时等待装卸,而码头每次只能装卸一艘船舶。船舶i需要装卸的时间为ti,1≤i≤n。应如何安排这n艘船舶的装卸次序才能使得总的等待时间达到最小?(总...
用贪心法解决背包问题的源代码,在vc++环境下也可以运行
综合运用贪心算法,求解不同数目的找零钱问题的源程序
背包问题的贪心算法实现,简答易懂 if(m>=weight[i]) { value=value+profit[i]; m-=weight[i]; s[i]=1; } else if(m!=0) { value=value+profit[i]*(1.0*m/weight[i]); s[i]=1.0*m...
这是个利用贪心法解决存储问题,希望对你们有用,嘻嘻。
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
NULL 博文链接:https://128kj.iteye.com/blog/1686101
任意输入城市数目,然后输入各城市间距离,运行显示各条旅行路线 使用贪心算法,找出次优解