部分貪心在信息學競賽中的應用

部分貪心在信息學競賽中的應用北京市清華附中高逸涵1引言引入眾所周知，貪心算法是一個在信息學競賽中應用廣泛的高效算法。但是有的時候，由于小規(guī)模針對性數據的存在，使得貪心算法不能得到正確的結果。如何解決這一問題呢？部分貪心，顧名思義，就是在問題的局部采用貪心算法，而在其他部分采用其他算法。部分貪心2引言為什么要“部分”貪心？當問題的特殊情況普遍較小的時候，對于邊界數據采用其他算法處理可以有效的回避特殊情況的討論。部分的普通算法對于總體時間復雜度影響并不大。部分的貪心可以極大的提高算法的時間效率。3引言舉個例子：我們要最優(yōu)化目標函數為了求得目標函數的最小值，我們可以首先貪心的求出趨勢函數的最小值，然后在其左右尋找目標函數的最小值。4例題[例題1]駱駝[例題2]CowRelays5[例題1]駱駝有p個人帶著x個小包y個大包穿越沙漠每匹駱駝可以背的物體只能是下列四種組合之一：不超過3個小包；不超過2個大包；1個人與不超過2個小包；1個人和1個大包。問最少需要多少駱駝？數據范圍：1<=p,x,y<=10000000006[例題1]駱駝首先，當所有人所帶的包的種類確定以后，剩下需要的駱駝數目可以直接算出來。所以我們需要求的只是有多少個人帶大包，多少個人帶小包。很容易得到如下公式：(p,x,y分別為人,小包,大包數)但由于數據規(guī)模巨大，直接枚舉顯然行不通，需要另想辦法。7[例題1]駱駝由于取整運算符的存在，導致直接數學計算變得比較困難。但是從整體趨勢上來看，i的增加顯然有利于ans的減小。那么按照貪心思想，我們需要盡量讓人帶著小包。8[例題1]駱駝我們很容易得到一個貪心算法：如果當前小包的個數>=2并且還有人是空閑的，那么令這個人帶著小包，否則令這個人帶大包。很不幸，這個算法是錯誤的(x=3,y=3,p=1)。如何改進？正確性？部分貪心！9[例題1]駱駝當人數和小包的數量都充分大的時候，令人帶小包顯然是沒錯的。經過驗證，人數和小包數>=20的時候，一定存在一個最優(yōu)解使得存在一個駱駝帶著人和小包。算法的正確性采用調整法很容易證明。而當人數和小包數有一個小于20時，可以采用枚舉法解決問題。10[例題1]駱駝已知樸素算法貪心算法解答大規(guī)模數據小規(guī)模特例部分貪心算法xx11[例題2]CowRelays在一個無向圖中有T條邊，每個點至少和兩條邊相連，每條邊有一個長度，詢問從給定起點到給定終點的包含N條邊的路最短是多長。數據規(guī)模：1<=N<=1000000000,1<=T<=10012[例題2]CowRelays首先看到這一題目，我們的直觀感受是，最優(yōu)解一定是這樣的一條路經：首先從起點運動到某一個點上。然后在這個點所連接的最小邊上往復運動。最后從這個點直接運動到終點。針對這一思想，我們很容易設計出一個貪心算法——枚舉一條邊做往復運動，然后從起點和終點分別向這條邊走增量最短的路徑到達。13[例題2]CowRelays所謂增量最短路徑，就是將所有邊減去基準邊之后得到的新圖內的最短路徑。ST5555477N=20基準邊31111314[例題2]CowRelays這樣的貪心算法的復雜度為，但是運用部分貪心算法避免重復計算，可以將復雜度進一步降為算法瓶頸在于對于每條邊，我們都要求一次最短路，我們希望在一次中解決所有最短路問題。15[例題2]CowRelays回顧我們求最短增量路徑的過程，顯然，我們所求的最短增量路徑一定是在邊數確定時的最短路徑。因此，我們只需要用動態(tài)規(guī)劃預處理出源點到每一個點所走邊數一定時所得的最短路徑的長度，然后在貪心時枚舉最短增量路徑長度即可。部分貪心思想！16[例題2]CowRelaysST5555477N=20N/A71015……基準邊32317SuvTSuvTSuvT[例題2]CowRelays貪心算法：樸素動態(tài)規(guī)劃：部分貪心：快快快慢慢慢優(yōu)勢互補！18結果[例題1]駱駝時間復雜度效果貪心算法O(1)WrongAnswer樸素算法O(N)TimeLimitExceed部分貪心算法O(1)Accepted19結果[例題2]CowRelays時間復雜度效果倍增算法較慢貪心算法較慢樸素算法很慢部分貪心算法很快20總結樸素算法 ——思路簡單，算法低效，不易出錯貪心算法 ——思路復雜，算法高效，易出錯部分貪心 ——思路簡單，算法高效，不易出錯取長補短，優(yōu)勢互補集兩家之所長，自成一體21ThankYou!22例題1正確性證明假設當有至少20個小包和20個人時，存在最優(yōu)解使得沒有駱駝帶著人和小包。則至少有6個駱駝只帶著小包，20個駱駝帶著大包和人。那么將4個帶著小包的駱駝和6個帶著大包和人的駱駝重分配，這時我們有12個小包，6個大包，6個人，我們只需令6個駱駝帶著人和小包，3個駱駝帶著大包，這樣只需要9個駱駝即可，即我們得到了一個比最優(yōu)解更優(yōu)的解，矛盾，因此假設不成立。23