文档介绍:参数搜索的应用
摘要
参数搜索法是解最优解问题中的常见的方法,它的应用十分广泛。本文通过几个例子说明了其在实际问题中的应用,并分析了它的优缺点。
关键字
参数搜索上界二分
正文:
引言
参数搜索是解决最优解问题一种很常见的方法。其本质就是对问题加入参数,先解决有参数的问题,再不断调整参数,最终求得最优解,下面就例举出它在几个不同方面的应用。
先来看一个例子,分石子问题:有N个石子,每个石子重量Qi;按顺序将它们装进K个筐中;求一种方案,使得最重的筐最轻。
分析:本题乍一看很容易想到动态规划。事实上的确可以用动态规划解决,稍加分析我们很快得到一个简单的算法。用状态f(i,k)表示将前i个石子装入k个筐最优方案,g(i,j)表示i-j中最重的石子,则可以写出状态转移方程:
g(i,j)=max {g(i,j-1),Qj}
f(i,j)=min max {f(k,j-1),g(k+1,i)} | 1<=j<=k
边界条件:g(i,i)=Qi,f(1,1)=g(1,1)
很明显,这个算法的时间复杂度为O(N3),空间复杂度为O(N2),并不十分理想。经过一些优化可以将复杂度降为O(N2),不过这样思维复杂度骤然加大,且算法本身仍不够高效。
现在已经很难在原动态规划模型上做文章了,我们必须换一个思路。按一般的想法,顺序将石子装入筐,即先把石子放入第一筐,放到一定时候再改放第二个筐,第三个筐……但由于筐的重量没有上限,我们无法知道放到什么时候可以停止,转而将石子放入下一个筐。此时,问题的难点已经显露出来,是不是有方法可以化解呢?
我们不妨针对上面的难点,加入一个参数P,改求一个判定可行解问题:每个筐石子重量和不能超过P,是否可以用K个筐装下所有石子。
首先经过分析不难发现,如果当前筐的石子总重量为T1,即将处理的石子重量为T2,若T1+T2 ≤P,则我们仍将该石子放入当前框,这是显而易见的。由此可以得出贪心算法,按顺序把石子放进筐,若将石子放入当前筐后,筐的总重量不超过P,则继续处理下一个石子;若重量和超过P,则将该石子放入下一个筐,若此时筐的数目超过K,则问题无解,否则处理完所有石子后就找到了一个可行解。
以上算法时间复杂度O(N),空间复杂度O(N),这都是理论的下界。
现在我们已经解决了可行解问题,再回到原问题。是不是可以利用刚才的简化过的问题呢?答案是肯定的。一个最简单的想法是从小到大枚举P,不断尝试找最优解为P的方案(这就是刚才的可行解问题),直到找到此方案。这就是题目的最优解。
估算一下上面算法的时间复杂度。令T=∑Qi,则最坏情况下需要枚举T次才能找到解,而每次判断的时间复杂度为O(N),因此总的时间复杂度为O(TN),故需要做进一步优化。
下面考虑答案所在的区间。很明显,若我们可以找到一个总重量不超过P’的解,则我们一定能找到一个总重量不超过P’+1的解,也就是说,可行答案必定可以位于区间[q,+∞](其中q为本题最优解)。因此,我们自然而然的联想到了二分,具体方法为:在区间[1,T]内取中值m,若可以找到不超过m的方案,则尝试区间[1,m-1];若不能,尝试区间[m+1,T]。不断重复以上步骤即可找到问题的最优解。
分析一下采用二分法后算法总的时间复杂度:由于每次除去一半的区间,则一共只需