算法合集之《淺談隨機(jī)化在信息學(xué)競賽中的應(yīng)用》

《算法合集之《淺談隨機(jī)化在信息學(xué)競賽中的應(yīng)用》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

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

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

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

6、I2004)選取值最小的點(diǎn)以這個(gè)點(diǎn)為新矩陣的中心，以現(xiàn)在矩陣的邊長的固定比例長度作為新矩形的邊長(如圖中取3/4)，從原來的矩陣中取出一塊作為新矩陣的范圍例題：Twosawmills(CEOI2004)然后繼續(xù)在新矩陣中重復(fù)這樣的操作，直至新矩陣足夠小時(shí)，我們即可枚舉新矩陣上的每一個(gè)點(diǎn)，取其中最小值作為答案。例題：Twosawmills(CEOI2004)我們驚喜地發(fā)現(xiàn)，這種隨機(jī)化算法對(duì)于測試數(shù)據(jù)能夠全部通過！例題：Twosawmills(CEOI2004)隨機(jī)化算法的靈活多變使得它的具有更為廣闊的運(yùn)用范圍而這樣的多變性也使得我們需要靈活恰當(dāng)?shù)剡\(yùn)用隨機(jī)化算法才能發(fā)揮出它的優(yōu)勢隨機(jī)化

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