算法合集之《参数搜索的应用》.pdf

参数搜索的应用

芜湖市第一中学汪汀
引言

参数搜索是解决最优解问题的一种常见
的方法。其本质就是对问题加入参数，先
解决有参数的问题，再不断调整参数，最
终求得最优解。下面通过几个例子来说明
这一点。
问题一分石子问题
有N个石子，每个石子重量Qi；
按顺序将它们装进K个筐中；
求一种方案，使最重的筐尽量轻。
问题一分石子问题
N=9,K=3
97|568|4327
161916
最大为19

975|684|327
211812
最大为21
问题一分石子问题——分析
本题可采用动态规划
时间复杂度O(N2)太高了

能否找到实现更简单，更优秀的算法呢？
问题一分石子问题——分析

９６５８８５?
问题一分石子问题——分析

引入参数P，求一个判定可行解问题:

判断是否存在最大重量不超过P的方案
问题一分石子问题——分析

可以用贪心法解决，具体方法如下：
按顺序把石子放入筐，若一个筐中石
子总重量不足P，我们就继续对这个
筐加入新的石子；如果超过P，则我们
将石子放入新的筐中。

问题一分石子问题——分析

N=5,K=3,P=12

９６５８3
问题一分石子问题——分析
回到最初的问题：
从小到大枚举P，找到第一个可行解，
该解即为问题所求

令T=∑Qi，则这个算法的时间复杂度为O(TN)

需要进一步优化!
问题一分石子问题——分析

若我们能找到一个最大重量不超过P的方案，
则我们可以找出一个最大重量不超过P+1的方案

二分法！

问题一分石子问题——分析
1MT

尝试区间[1,M-1]尝试区间[M+1,T]

不断重复以上步骤即可找到问题的最优解。
时间复杂度O(NlogT)
特别地，由于答案必定为某一段连续石子的重量和
所以可以得到一个时间复杂度为O(Nlog3N)的算法

小结

首先引入参数P，解决带参数的问题；

用贪心法可以判断是否存在最大重量和不超过p的方案；

枚举P求出问题的最优解；

二分法降低了算法的时间复杂度，最终解决了问题。

小结

Ⅰ首先引入参数P，解决带参数的问题；
判断是否存在结果优于P的方案

Ⅱ调整P得到最优解。
通过二分法或迭代法减少调整次数，降低算法时间复杂度。

问题二最大比率问题
有N道题目，每道题目有不同的分值和难

度，分别为Ai，Bi（分值及难度均为正数）；
要求从某一题开始，连续选至少K道题目，
满足分值和与难度和的比最大。
问题二最大比率问题
例如
N=7,K=3
A43989921
B22112113
选择第3题到第6题，比为(9+8+9+9)/(1+1+2+1)=7
这是上例的最优解
问题二最大比率问题

先来解决一个与之类似的简化版问题：

在一个数列中找连续多个数（至少K个），总和最大。

建立一个队列Q，开始时队列只有K个元素，按顺序往

队列中添加新的元素，添加后计算Q1+Q2..+QL-K的

和，记为S。若S<0，则将Q1,Q2..QL-K从队列中删
除，否则暂时保留这些数。并不断更新最大值。
问题二最大比率问题——分析

-12-364-13
扫描一遍的复杂度是线性的
这就是最优解

和为-１和为２和为-1和为12
问题二最大比率问题——分析
现在我们已经能在O(N)的时间内解决简化后的问题了。

这个方法能不能应用于原题？
很遗憾，由于原题中每个数据有两个参数，故它们对
最终结果产生的影响是不确定的，因此对于原题我们
不能直接套用这个算法。

现在必须消除这个不确定因素。
问题二最大比率问题——分析

为此，我们必须引入参数p，求一个判定可行解问题：

判断是否存在一个比大于p的方案
问题二最大比率问题——分析

新的问题可以这样描述：
求两个下标i’,j’，满足

j’-i’+1≥k①

(Ai’+Ai’+1....+Aj’)/(Bi’+Bi’+1…+Bj’)>p②

②Ai’+Ai’+1....+Aj’>p(Bi’+Bi’+1…+Bj’)

(Ai’-pBi’)+(Ai’+1-pBi’+1)…+(Aj’-pBj’)>0

问题二最大比率问题——分析

(Ai’-pBi’)+(Ai’+1-pBi’+1)…+(Aj’-pBj’)>0

令Ci=Ai-pBi，Ci’+Ci’+1…+Cj’>0可以借用刚才的结
论

在数列C中找一段连续的数（至少K个），和为正数。

我们能在O(N)的时间内找到中和最大的一段，记为S：
若S＞0则找到了一个可行方案
若S≤0，则问题无解
问题二最大比率问题——分析

O(N)的时间判断出是否存在比不小于P的方案。
通过二分法，调整参数P的大小，不断逼近最优解。

时间复杂度O(NlogT)
小结

上例的难点在于每道题有难度和分值两个数