专栏首页爬蜥的学习之旅约束条件变更对算法运行时间所带来的影响

约束条件变更对算法运行时间所带来的影响

以区间调度为例

区间调度

有1,...,n次请求,去获取单个资源,每个请求的开始时间是s(i),结束时间是f(i), 对于请求i和j,如果二者的区间不重合,即f(i)<=s(j) 或者 f(j)<=s(i),那么这两次请求认为是兼容的。比如下面的两个区间是兼容的

而下面存在不兼容的区间

区间调度的问题是,如何才能获取请求的兼容的区间最大的个数呢?

比如上图是3个

如何才能获取请求的兼容的区间最大的个数?

可以使用贪心算法。

贪心算法的大致思路是:每次获取问题的一小部分,决定对这小部分数据如何做处理,解决了这部分,再去处理其它的。

  • 使用某种规则去获取一个请求i
  • 排除所有与i不兼容的请求
  • 重复第一步直到所有请求都处理完毕

关键在于如何选取请求。可以想象有一些方式

  1. 按照顺序来,从这种情况看,只能拿到第一个请求,不是最大的,不行

  1. 获取时间区间最短的,有如下反例
  1. 计算每个请求的不兼容的请求的数量,然后获取最小的不兼容数量的,有如下反例,最少的不兼容的是红色的区间

可以选择最早结束的请求作为选择的规则,这样能获得最大的兼容区间的个数

选择最早结束的请求作为选择的规则,能获得最大的兼容区间的个数

最优的子集也是最优的

加权的区间调度

可以举出一个例子,证明使用上述贪心算法的策略不再生效

优先最先完成的贪心算法必定会选择权重为w=1的两个,但是它得到的最终权重是小于w=3的区间。

使用动态规划可以解决。 我不知道该从那个请求开始,那么就去选择所有可能作为第一个请求的地方,然后获取他们的最大值,即得结果。 选取好开始的节点之后,剩下的问题是什么呢?如果选取了第一个请求之后,那么应该排斥掉那些与它不兼容的区间,才能获取兼容区间,那么发生在这个请求之前的请求是否应该考虑?由于选取的规则是认为它是第一个请求,如果有之前的发生,实际上在整个的遍历过程中肯定会经历,所以只需要选取在它之后发生的即可,那么剩下的问题也就是

获取最大的权重的兼容空间也就是考虑,所有子问题中加上当前问题的最大数即可:

时间花销:可以看到一共有O(n)个子问题,因为选取第一个区间之后,其它的所有子问题要做一个max,需要遍历所有的情况,然后记下来,供后续使用。总共的遍历为从1,..,n,所以时间花销为

运行时间可以优化到nlgn;

如果增加条件实在一批机器上运行,要去获取一个最大的兼容区间个数,则是一个NP-hard问题

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 文本获取和搜索引擎之推荐系统

    推荐系统即把恰当的内容推送给用户,类似于在一系列文档中过滤出用户想要的。一般有两种方式:

    爬蜥
  • 常见动态规划的解决思路

    给定一个词的集合words,使用badness(i,j)表示使用的单词是words[i,j]

    爬蜥
  • 使用贪心算法解决最小生成树

    生成树的定义:对于一个图G,获取G的边使得所有的顶点都连接到。最小生成树(MST Minimun spanning tree):给定图G(V,E),以及对应的边...

    爬蜥
  • 带着网关去旅行--smarGate使用手记

    或许你用过花生壳、frp、ngrok、teamviewer等穿透工具,今天要给大家介绍的是smarGate(https://github.com/lazy-lu...

    用户2103032
  • 【学习】七天搞定SAS(三):基本模块调用(格式、计数、概要统计、排序等)(下)

    SAS里面总结数据:MEANS SAS当然还有类似于excel的数据透视表和R的data.table的模块,就是MEANS。可以输出的summary stat...

    小莹莹
  • 【学习】七天搞定SAS(一):数据的导入、数据结构

    SAS的数据类型 ? 首先,sas的编程大概就两块:Data和PROC,这个倒是蛮清晰的划分。然后目前关注data部分。 SAS的数据类型还真的只有两种:数字和...

    小莹莹
  • 线性代数——(3)矩阵

    羊羽shine
  • 商品综合评价排名

    店内有很多产品,而且包含但不局限于以下指标:浏览量、访客数、平均停留时长、详情页跳出率、下单转化率、下单支付转化率、支付转化率、下单金额、下单商品件数、下单买家...

    机器学习和大数据挖掘
  • cpu频繁有序的忽高忽低

    今天有空给大家分享一个我刚刚遇到的小问题,标题就是今天的问题。上图: image.png CPU 忽高忽低的发现了吧,对于我这个纠结者,必须得弄清楚是怎么回...

    老七Linux
  • 关于汽车场景识别的接口

    体验地址:https://cloud.tencent.com/act/event/ocrdemo

    算法发

扫码关注云+社区

领取腾讯云代金券