10劉家驊淺談隨機(jī)化在信息學(xué)競賽中的應(yīng)用

1、廣東省韶關(guān)市第一中學(xué) 劉家驊,淺談隨機(jī)化在信息學(xué)競賽中的應(yīng)用,信息學(xué)競賽的題目日新月異,新型算法層出不窮,隨機(jī)化算法作為一種新興算法,猶如新生的太陽在信息學(xué)競賽的廣闊天空上煥發(fā)光芒,引言,簡單問題的另類算法,有一個多邊形A1A2AN ，在每條邊AiAi+1上向多邊形外做一個等腰三角形AiMiAi+1使得角AiMiAi+1=i 由i組成的集合滿足其任何非空子集的角度和不是360度的倍數(shù) 給出N(3N50) ，所有Mi的坐標(biāo)和i，寫一個程序，輸出多邊行的頂點(diǎn)的坐標(biāo),例題 Geometrical dreams(Ural1046),例題 Geometrical dreams(Ural1046),一般方

2、法簡單解方程 有沒有其他方法呢？ 讓我們換一個角度思考問題 只要確定了一個頂點(diǎn)的坐標(biāo)，多邊形的其他頂點(diǎn)的坐標(biāo)就能夠通過簡單計算得到，那么問題就轉(zhuǎn)化為確定多邊形的一個頂點(diǎn)的坐標(biāo),例題 Geometrical dreams(Ural1046),確定一個頂點(diǎn)的位置？,隨機(jī)化,當(dāng)?shù)谝粋€頂點(diǎn)的位置被暫時確定 通過計算能夠得到第N+1個頂點(diǎn)的位置 當(dāng)?shù)贜+1個頂點(diǎn)越接近第1個頂點(diǎn) 這個頂點(diǎn)的位置就越接近其實(shí)際位置,例題 Geometrical dreams(Ural1046),我們每次可以在當(dāng)前最優(yōu)位置旁邊隨機(jī)化確定第一個頂點(diǎn)的位置，然后計算此時第N+1個頂點(diǎn)與第1個頂點(diǎn)的距離 如果這個距離比當(dāng)前最優(yōu)距離

3、更小，那么我們就用這個位置更新當(dāng)前最優(yōu)位置 顯然，當(dāng)?shù)?個頂點(diǎn)與第N+1個頂點(diǎn)重合時，此時第1個頂點(diǎn)的位置即為其實(shí)際位置,事實(shí)證明 這種方法能夠通過這道題目,例題 Geometrical dreams(Ural1046),雖然這樣的方法顯然在任何方面都要比前面提到的普通做法要復(fù)雜 對于解決這道題目沒有太大的意義 但是，它提供給我們一種嶄新的思路,隨機(jī)化,隨機(jī)化算法對于這樣的題目沒有優(yōu)勢，但它在很多問題上都能得到運(yùn)用，下面，我們一起來進(jìn)一步領(lǐng)略隨機(jī)化算法的魅力吧,小試牛刀,從山頂?shù)缴侥_的路上有n棵老樹，現(xiàn)在政府決定砍掉它們，為了不浪費(fèi)木材，每一棵樹都會被轉(zhuǎn)運(yùn)到鋸木場 樹只能往一個方向運(yùn)輸向下,例

4、題：Two sawmills(CEOI2004),例題：Two sawmills(CEOI2004),在路的盡頭有一個鋸木場。兩個額外的鋸木場可以在路上任意一棵老樹位置上 你必須選擇在哪里建造，使得運(yùn)輸?shù)馁M(fèi)用達(dá)到最少 運(yùn)輸費(fèi)用是一分每米每千克木材,例題：Two sawmills(CEOI2004),這道題目的標(biāo)準(zhǔn)算法將數(shù)據(jù)轉(zhuǎn)化為圖象，用棧進(jìn)行處理求出兩個矩形的最大覆蓋面積，時間復(fù)雜度為O(N)。 但是，這種算法對能力要求不小，不太容易想到。 我們看下隨機(jī)化算法在這題上的表現(xiàn),例題：Two sawmills(CEOI2004),首先最容易想到的隨機(jī)化當(dāng)然就是直接隨機(jī)尋找兩個點(diǎn)，計算出以這兩個點(diǎn)為

5、鋸木場時的總運(yùn)費(fèi)，多次隨機(jī)后將總費(fèi)用最小的輸出 我們可以進(jìn)行預(yù)處理，將計算的時間復(fù)雜度降為O(1)，那么在時限內(nèi)我們可以隨機(jī)幾百萬次甚至幾千萬次，但是相對于總狀態(tài)的四億來說，尋找到最優(yōu)解的幾率不是很大,例題：Two sawmills(CEOI2004),我們剛才是用隨機(jī)化算法直接出解，準(zhǔn)確性不太好 為了增加準(zhǔn)確性，那么我們嘗試一下用隨機(jī)化來縮小區(qū)域范圍,有沒有更好的方法呢 ？,例題：Two sawmills(CEOI2004),我們建立一個矩陣P，PX,Y表示第一個鋸木場建立在X，第二個鋸木場建立在Y時的總運(yùn)費(fèi),例題：Two sawmills(CEOI2004),一開始時，矩陣的邊長為N,我們

6、隨機(jī)尋找一定數(shù)量的點(diǎn)，計算出它們的值,例題：Two sawmills(CEOI2004),選取值最小的點(diǎn),以這個點(diǎn)為新矩陣的中心，以現(xiàn)在矩陣的邊長的固定比例長度作為新矩形的邊長(如圖中取3/4)，從原來的矩陣中取出一塊作為新矩陣的范圍,例題：Two sawmills(CEOI2004),然后繼續(xù)在新矩陣中重復(fù)這樣的操作，直至新矩陣足夠小時，我們即可枚舉新矩陣上的每一個點(diǎn)，取其中最小值作為答案。,例題：Two sawmills(CEOI2004),我們驚喜地發(fā)現(xiàn)，這種隨機(jī)化算法對于測試數(shù)據(jù)能夠全部通過！,例題：Two sawmills(CEOI2004),隨機(jī)化算法的靈活多變使得它的具有更為廣闊

7、的運(yùn)用范圍 而這樣的多變性也使得我們需要靈活恰當(dāng)?shù)剡\(yùn)用隨機(jī)化算法才能發(fā)揮出它的優(yōu)勢 隨機(jī)化算法并不只是簡單地隨便亂來，使用隨機(jī)化算法的時候與其他算法一樣值得細(xì)細(xì)斟酌，需要匠心獨(dú)運(yùn),通過這道題目可以看出：,下面 讓我們來看看隨機(jī)化算法 在實(shí)際比賽中的運(yùn)用解析,實(shí)戰(zhàn)解析,題目大意是給出由N個點(diǎn)、M條邊組成的圖，求最大生成樹 在圖1所示例子中黑色邊組成的樹即為最優(yōu)方案,例題：小H的聚會(NOI2005),例題：小H的聚會(NOI2005),但是，為了減輕每個頂點(diǎn)的負(fù)擔(dān)，題目設(shè)定了每個頂點(diǎn)的最大連接邊數(shù)ki 還是用圖1的例子，若我們?yōu)?至5每個點(diǎn)分別加上了ki = 1, 1, 4, 2, 2的限制，則

8、上述方案就不能滿足要求了。此時的最優(yōu)方案如圖2所示,例題：小H的聚會(NOI2005),這是一道提交答案題，題目數(shù)據(jù)分為三種類型 第一種類型包括第1-3個數(shù)據(jù)，每個點(diǎn)的度限制均為N-1，等同于沒有限制，直接用最小生成樹算法即可解決 第二種類型包括第4-6個數(shù)據(jù)，其中N-1個點(diǎn)的度限制為N-1，只有一個點(diǎn)有度限制，可以使用最小度限制生成樹算法解決。,例題：小H的聚會(NOI2005),題目數(shù)據(jù)的第三種類型包括第7-10個數(shù)據(jù)，數(shù)據(jù)中所有點(diǎn)都有度限制,沒有太好的準(zhǔn)確算法 而這個題目又是不要求最優(yōu)解的開放性題目 這種問題實(shí)在是隨機(jī)化算法自由翱翔的廣闊天空。 我們可以采取隨機(jī)化算法結(jié)合不同算法解決這個

9、題目。,例題：小H的聚會(NOI2005),我們用Kruskal算法計算出符合點(diǎn)的度限制的一棵生成樹 由于有了度限制，所以這樣得出的生成樹不一定是最優(yōu)的 我們可以在按邊權(quán)大小排序后，再隨機(jī)打亂部分邊的順序，再用Kruskal算法，以求得到更優(yōu)的解。,方法一：基于Kruskal的隨機(jī)化算法,例題：小H的聚會(NOI2005),在每次得到這樣一棵較大的生成樹后，我們再隨機(jī)化選取一條不在生成樹上的邊，加入生成樹上得到一個圈 再在這個圈上試圖刪除一條邊使得生成樹仍然滿足度限制并且結(jié)果更優(yōu) 如此重復(fù)多次，以得到不能再通過這種方法得到更優(yōu)解的極優(yōu)解。,方法一：基于Kruskal的隨機(jī)化算法,例題：小H的聚

10、會(NOI2005),多次使用Kruskal算法后輸出計算出的最優(yōu)解,方法一：基于Kruskal的隨機(jī)化算法,例題：小H的聚會(NOI2005),先用Prim算法計算出一個不考慮度限制的最大生成樹 在這棵生成樹上，每次隨機(jī)選取一個不滿足度限制的點(diǎn)，并試圖尋找不在生成樹上邊替代在生成樹內(nèi)并且連接到這個點(diǎn)的邊以降低這個點(diǎn)的度,方法二：基于Prim的隨機(jī)化算法,例題：小H的聚會(NOI2005),多次重復(fù)直至將這棵樹修改到滿足度限制或者無法再用這樣的方法降低這棵樹不滿足度限制的點(diǎn)的度的時候停止 重新在原最大生成樹上重復(fù)上述操作多次，輸出計算出的最優(yōu)解,方法二：基于Prim的隨機(jī)化算法,例題：小H的聚會(NOI2005),兩種算法的比較,例題：小H的聚會(NOI2005),使用隨機(jī)化算法在開放性題目能夠得到很好的結(jié)果 使用隨機(jī)化算法結(jié)合不同的算法會得到不同的結(jié)果 在解題時運(yùn)用恰當(dāng)?shù)乃惴ㄅ浜想S機(jī)化算法能提高程序的準(zhǔn)確性,通過上面例題可以看出：,總結(jié),針對不同情況靈活運(yùn)