PBI演算法

A. ACM題目求解題思路

有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]。不斷重復以上步驟即可找到問題的最優解。分析一下採用二分法後演算法總的時間復雜度：由於每次除去一半的區間，則一共只需判斷log2N次，而每次判斷的時間復雜度為O(N)，因此這個演算法總的時間復雜度為O(NlgT)。一般而言，這個復雜度可以令人滿意的，並且實際使用中效果非常好。但該復雜度同權值有關，不完全屬於多項式演算法，我們可以繼續求得一個多項式演算法（該演算法與本文核心內容無關，只作簡單探討）。首先，此問題的答案必定為某一段連續石子的和，而段數不超過n2，因此，我們最多隻要判斷log2N2=2log2N次即可。現在新的問題是如何找到第m大的段。首先，以每個石子開頭的所有段，例如：3 2 1 2，以2開頭的所有段：2；2 1； 2 1 2， 由於每個石子的重量都大於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)。 至此我們終於得到了一個多項式級別的演算法，當然這個演算法實現起來比較麻煩，實際效果也不甚理想，不過具有一定的理論價值，在此不做過多討論。 回顧本題解題過程，首先我們得到了一個動態規劃演算法，由於很難再提高其效率，因此我們另闢蹊徑，尋求新的演算法。在分析過程中我們發現由於筐的重量沒有上限，因此很難確定將多少石子放入同一個筐內。為了解決此難點，我們加入了參數P，改求可行解問題。參數的加入實際上就是強行給筐定了一個上界。正是由於這無形之中多出的條件，使得問題立刻簡單化，於是我們很自然的得到了貪心演算法。而最終使用二分法降低了演算法的時間復雜度，成功地解決了問題。 由上面的例子我們得到了此類解法的一般步驟，通常分為兩步：Ⅰ.首先引入參數P，解決子問題：能否找到一個不優於P的方案Ⅱ.從小到大枚舉P，判斷是否有優於P的方案，直到找出原問題的最優解 一般地，參數搜索可以通過二分法或迭代降低時間復雜度，由於迭代法證明比較復雜，所以本文更多的討論二分法。 這個方法的應用比較廣泛，通常情況下和上例一樣求最大（小）值盡量小（大）的題目都可以採用此方法，比如下面的例子。神秘的山：有n個隊員攀登n個山峰，每個隊員需要選擇一個山峰，隊員們攀登的山峰各不相同，要求最後一個登頂的隊員用的時間盡量短。 分析：本問題分為兩個部分解決：1．求出每個隊員攀登到各個山峰所需的時間；2．找一個最優分配方案。 第一部分屬於幾何問題，我們可以枚舉每個隊員攀登山峰的位置再做簡單的判斷（題目規定攀登點必須為整點，這就為枚舉提供了條件），這樣就可求得隊員們攀登上各個山峰所需的時間。下面重點討論第二部分。首先將我們的數據構圖，很明顯，我們得到的是一個二部圖，假設有3個隊員3個山峰，每個隊員攀登的時間如下 山峰1山峰2山峰3隊員1132隊員2222隊員3133 則我們可以構圖，每條邊附上相應的權值： 現在的任務就是在圖中找一個匹配，匹配中權值最大的邊盡量小。這個問題是否可以直接套用一些常見的模型呢？比如最大匹配或是最佳匹配？經過分析不難發現在這個問題中它們都是不足以勝任的，因此我們不得不做新的嘗試。 上文提到過要求極大（小）值盡量小（大）的題目往往先定出上界比較容易下手，那麼這題也採用類似的思路。引入一個參數T，先求一個判定可行解的子問題：找一個方案，要求最後登山的隊員所用時間不超過T。 改變後的題目有什麼不同之處呢？如果隊員i攀登上山峰j所需的時間超過T，則可以認為他在規定時間內不能攀登上山峰j，我們就可以把這條邊從圖中刪去。例如在上例中找一個不超過2的方案，經過一次「篩選」，保留的圖如下。 經過這次過濾保留下來的邊都是「合法邊」，我們只需要在這個新的二部圖中找一個完備匹配即可，一個完備匹配唯一對應著一個可行方案。而找完備匹配可以借用最大匹配的演算法，因為如果一個二部圖的最大匹配數等於N，則找到了一個完備匹配，否則該圖中將不存在完備匹配。（上圖中的紅色表示一個完備匹配），那麼這一步的時間復雜度為O(NM)，而在本題中M=N2，因此我們可以在O(N3)的時間內判斷出是否存在一個方案滿足最後等上山頂的隊員時間不超過T。 最後，再用二分法枚舉參數T，找到最優解。由於答案必定為某個隊員攀登上其中一個山峰的時間，因此我們開始的時候可以將所有數據排序，這樣最終的時間復雜度為O(N3lgN)。引入參數後求可行解的子問題與原問題最大的區別在於定下上界以後，我們很自然的排除了一些不可取條件，從而留下了「合法」條件，使得問題變的簡單明了。. 上面的例子在增加了上界之後，排除了一些無效條件，其實它的作用絕不僅局限於此，有些時候，它能將不確定條件變為確定條件，比如下面的例子，最大比率問題：有N道題目,每道題目有不同的分值和難度,分別為Ai,Bi；要求從某一題開始, 至少連續選K道題目,滿足分值和與難度和的比最大。 分析：最樸素的想法是枚舉下標i』,j』，得到每一個長度不小於K的連續段，通過累加Ai』->Aj』，Bi』->Bj』求出比值，並找出比最大的一段。這樣做的時間復雜度很高，由於總共有N2段，每次計算比值的時間是O(N)，則總的時間復雜度到達O(N3)，不過計算比值時，可以採用部分和優化，這樣能把復雜度降至O(N2)，但仍然不夠理想。我們需要追求更出色的演算法，先考慮一個簡單的問題——不考慮難度（Bi），僅僅要求分值和最大（當然此時分值有正有負）。這個簡化後的問題可以直接掃描，開始時為一個長度為K的段，設為Q1,Q2,…Qk， 每次添加一個新數，若Q1+Q2+..+QL-K小於0，則把它們從數列中刪去，不斷更新最優解即可。這樣我們就能在O(N)的時間內找到長度不小於k且和最大的連續段。 之所以能成功解決簡化後的問題，是由於該問題中每個量對最終結果的影響是確定的，若其小於0，則對結果產生不好的影響，反之則是有益的影響。那麼原問題每個參數對最終結果的影響是不是確定的呢？很遺憾，並不是這樣，因為每個題目有兩個不同的參數，他們之間存在著某些的聯系，而這些聯系又具有不確定性，故我們很難知道它們對最終結果是否有幫助。想解決原問題，必須設法消除這個不確定因素！那麼有沒有辦法將這些不確定的因素轉化成確定的因素呢？此時，引入參數勢在必行！那麼我們引入參數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可以令Ci=Ai-pBi，則根據上面不等式可知問題實際求一個長度不小於k且和大於０的連續段。由之前的分析可以知道我們能在O(N)的時間內求出長度不小於k且和最大的連續段，那麼如果該段的和大於等於０，則我們找到了一個可行解，如果和小於０，則問題無解。也就是說，我們已經能在O(N)的時間內判斷出是否存在比值不小於P的方案，那麼接下來的步驟也就順理成章了。我們需要通過二分法調整參數P，不斷逼近最優解。計算一下以上演算法的時間復雜度，設答案為T，則該演算法的時間復雜度為O(NlgT)，雖然這並不是多項式級別的演算法，但在實際使用中的效果非常好。引入參數後，由於增加了一個條件，我們就可以將不確定的量變為確定的量，從而解決了問題。三． 總結 本文主要通過幾個例子說明了參數搜索法在信息學中的應用，從上文的例子可以看出加入參數一方面能大大降低思維復雜度，另一方面也能得到效率相當高的演算法，這使得我們解最解問題又多了一中有力的武器。當然，任何事物都是具有兩面性的。參數搜索在具有多種優點的同時也有著消極的一面。由於需要不斷調整參數逼近最優解，其時間復雜度往往略高於最優演算法，且通常依賴於某個權值的大小，使得我們得到的有時不是嚴格意義上的多項式演算法。文章中還總結了使用此方法解題的一般步驟，在實際應用中，我們不能拘泥於形式化的東西，必須靈活應用，大膽創新，這樣才能游刃有餘的解決問題。