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

参数搜索的应用
摘要
参数搜索法是解最优解问题中的常见的方法，它的应用十分广泛。本文通过几个例子说明了其在实际问题中的应用，并分析了它的优缺点。
关键字
参数搜索上界二分

正文：
引言
参数搜索是解决最优解问题一种很常见的方法。其本质就是对问题加入参数，先解决有参数的问题，再不断调整参数，最终求得最优解，下面就例举出它在几个不同方面的应用。
二．应用
先来看一个例子，分石子问题：有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)=minmax{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]。不断重复以上步骤即可找到问题的最优解。
分析一下采用二分法后算法总的时间复杂度：由于每次除去一半的区间，则一共只需判断log2N次，而每次判断的时间复杂度为O(N)，因此这个算法总的时间复杂度为O(NlgT)。
一般而言，这个复杂度可以令人满意的，并且实际使用中效果非常好。但该复杂度同权值有关，不完全属于多项式算法，我们可以继续求得一个多项式算法（该算法与本文核心内容无关，只作简单探讨）。
首先，此问题的答案必定为某一段连续石子的和，而段数不超过n2，因此，我们最多只要判断log2N2=2log2N次即可。现在新的问题是如何找到第m大的段。首先，以每个石子开头的所有段，例如：3212，以2开头的所有段：2；21；212，由于每个石子的重量都大于0，因此总和一定是递增的。
现在有n个递增段，如何快速的找到第k大的数呢？设各段长度为L1,L2,…,LN,中点分别为M1,M2,…,MN，我们每次询问各段中点的大小，若L1/2+L2/2+..+LN/2>k，则找到权值最大的中点，删去其后的数（下图中红色部分），否则找到权值最小的中点，删去其前面的部分（下图中黑色部分），可以证明删去的一定不是所求的数。

注：上图中每个各格子代表一个数。

由以上可知每次可以去掉某一段的1/2，因为有n段，故总共需要去O(Nlog2N)次，每次找最小最大值可以用堆实现，复杂度仅为O(lgN)，因此总的时间复杂度为O(lg2N)，而由上文我们知道找中值的操作总共有log2N次，故这个算法的时间复杂度为O(Nlg3N)。
至此我们终于得到了一个多项式级别的算法，当然这个算法实现