从调度问题看贪心算法最优性证明
贪心算法最优性证明
首先我们引入一个问题Interval Scheduling(调度问题)
现在你拥有一个资源,它可能是一间教室、一台计算机等,许多人都要求使用这个资源(计算机),但是这个资源(计算机)同一时间只能被一个人使用,我们想要达成的目标是,从起始时间s开始到结束时间f,我们可以尽可能多的满足使用这个资源的要求。
我们也可以更正式的理解这个问题。
现在我们有一组请求 request = {1, 2, 3, … , n},requesti的开始时间是starti,结束时间是endi,我们的目标是从集合request中选出尽可能多的不重合的request。
贪心算法通常都是很自然的思路,我们可以想到
- 总是选择最先开始的request,这样可以使我们的资源更早的投入使用。
- 总是选择持续时间最短的request,这样可以使我们的资源更快的被释放,这样可以使更多的请求被接受。
- 总是选择冲突最少的request,这样可以使得我们拒绝更少的request。
- 总是选择最先结束的request。
对于每一个贪心策略,我们都需要证明它是否能够一步一步的到达最优解。
- 我们可以首先声明一个最优解O。
- 如果在第一步,可以证明贪心策略不比最优解差。
- 我们假设第k步,贪心策略的选择也不必最优解差。
- 那么我们只要证明第k 1步,贪心策略的选择也可以接受,那么就说明贪心策略可以达到最优解。
对于第4个思路,我们可以给出最优性证明。
我们期望证明它得到的可以接受的request数是A,最优解得到的可以接受的request数是O,如果我们可以证明A === O,那么就说明这个贪心策略将会得到最优解。
接下来,我们假设A中的第i个request的结束时间是endi,O中第i个request的结束时间是Endi,如果我们可以证明endi不迟于Endi,那么贪心策略会是最优的。
当i === 1,因为贪心策略选择的是所有request中最早结束的request,所以end1必然不迟于End1。
我们假设当i === k时,endk也不迟于Endk。
我们现在要证明当i === k 1时,endk 1不迟于Endk 1。
因为贪心策略始终选择剩下的(没有被拒绝,也没有被接受的)request中的最早完成的,又因为前一步中endk不迟于Endk,所以对于第k 1步,贪心策略也必然选择不迟于最优解的request,这样我们就证明贪心策略的最优性。
我们通常是使用数学归纳法来证明最优解的。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgehfbc
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01