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

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

1、淺談隨機(jī)化在信息學(xué)競(jìng)賽中的應(yīng)用——廣東省韶關(guān)市第一中學(xué)劉家驊【摘要】如今信息學(xué)競(jìng)賽題目日新月異，各種新型算法層出不窮，而作為一種新興的算法，隨機(jī)化算法在信息學(xué)競(jìng)賽這個(gè)舞臺(tái)上也發(fā)揮著獨(dú)特而重要的作用。本文通過幾個(gè)典型例題簡(jiǎn)單介紹隨機(jī)化算法在信息學(xué)競(jìng)賽中的應(yīng)用。【關(guān)鍵字】信息學(xué)競(jìng)賽隨機(jī)化【引言】伴隨著信息學(xué)競(jìng)賽的發(fā)展，“隨機(jī)化”一詞在參加信息學(xué)競(jìng)賽的同學(xué)心中經(jīng)歷了一個(gè)由陌生到熟悉的過程。隨機(jī)化算法以其特有的靈活多變，逐漸在越來越多不同類型的競(jìng)賽題目中得到巧妙運(yùn)用，在越來越多樣化的信息學(xué)競(jìng)賽中擁有獨(dú)有的優(yōu)勢(shì)。掌握了隨機(jī)化算法，無疑手上又多了一把解決問題的利刃。簡(jiǎn)單題目的另類算

2、法例題：Geometricaldreams(Ural1046)有一個(gè)多邊形A1A2…AN，在每條邊AiAi+1上向多邊形外做一個(gè)等腰三角形AiMiAi+1使得角AiMiAi+1=αi。由αi組成的集合滿足其任何非空子集的角度和不是360度的倍數(shù)。給出N，所有Mi的坐標(biāo)和αi，寫一個(gè)程序，輸出多邊行的頂點(diǎn)的坐標(biāo)。分析：這道題目用簡(jiǎn)單的解方程就能夠解決。讓我們從另外一個(gè)角度思考問題，從題目的條件易知，只要確定了一個(gè)頂點(diǎn)的坐標(biāo)，多邊形的其他頂點(diǎn)的坐標(biāo)就能夠通過簡(jiǎn)單計(jì)算得到，那么問題就轉(zhuǎn)化為確定多邊形的一個(gè)頂點(diǎn)的坐標(biāo)。如何確定一個(gè)頂點(diǎn)的坐標(biāo)呢，枚舉和二分等常用算法都無法為我們解

3、決問題，于是，我們想到了隨機(jī)化。我們開始時(shí)將第一個(gè)點(diǎn)放在原點(diǎn)，通過計(jì)算能夠得出第N+1個(gè)頂點(diǎn)的坐標(biāo)，如果第N+1個(gè)頂點(diǎn)和第1個(gè)頂點(diǎn)重合，這個(gè)多邊形就是所求，但是顯然這樣的可能性非常渺茫，于是我們需要調(diào)整第一點(diǎn)的位置。顯然，第一個(gè)點(diǎn)距離第N+1個(gè)點(diǎn)的距離越小，其位置越接近其實(shí)際位置。我們每次可以在暫時(shí)確定第一個(gè)點(diǎn)的位置附近隨機(jī)一個(gè)點(diǎn)，判斷第一個(gè)點(diǎn)放在這里這個(gè)位置時(shí)與原來相比第一個(gè)點(diǎn)與第N+1個(gè)點(diǎn)的距離是否比原來更小，如果是，則將第一個(gè)點(diǎn)的位置暫時(shí)定在這個(gè)位置，然后繼續(xù)上述操作，直至第一個(gè)點(diǎn)與第N+1個(gè)點(diǎn)重合，我們就確定了多邊形的頂點(diǎn)的坐標(biāo)了。事實(shí)證明，這種方法能夠通過這道

4、題目。雖然這樣的方法顯然在任何方面都要比前面提到的普通做法要復(fù)雜，對(duì)于解決這道題目沒有太大的意義，但是，它提供給我們一種嶄新的思路——隨機(jī)化。隨機(jī)化算法對(duì)于這樣的題目沒有優(yōu)勢(shì)，但是，它在很多問題上都能得到運(yùn)用，下面，我們一起來進(jìn)一步領(lǐng)略隨機(jī)化算法的魅力吧。小試牛刀例題：Twosawmills(CEOI2004)從山頂?shù)缴侥_的路上有n棵老樹，現(xiàn)在政府決定砍掉它們，為了不浪費(fèi)木材，每一棵樹都會(huì)被轉(zhuǎn)運(yùn)到鋸木場(chǎng)。樹只能往一個(gè)方向運(yùn)輸，向下。在路的盡頭有一個(gè)鋸木場(chǎng)。兩個(gè)額外的鋸木場(chǎng)可以在路上的任意一棵老樹的位置上，你必須選擇在哪里建造，使得運(yùn)輸?shù)馁M(fèi)用達(dá)到最少。運(yùn)輸費(fèi)用是一分每米每

5、千克木材。分析：這道題目的標(biāo)準(zhǔn)算法將數(shù)據(jù)轉(zhuǎn)化為圖象，用棧進(jìn)行處理求出兩個(gè)矩形的最大覆蓋面積，時(shí)間復(fù)雜度為O(N)。但是，這種算法對(duì)能力要求不小，不太容易想到。我們看下隨機(jī)化算法在這題上的表現(xiàn)。首先最容易想到的隨機(jī)化當(dāng)然就是直接隨機(jī)尋找兩個(gè)點(diǎn)，計(jì)算出以這兩個(gè)點(diǎn)為鋸木場(chǎng)時(shí)的總運(yùn)費(fèi)，多次隨機(jī)后將總費(fèi)用最小的輸出。我們可以進(jìn)行預(yù)處理，將計(jì)算的時(shí)間復(fù)雜度降為O(1)，那么在時(shí)限內(nèi)我們可以隨機(jī)幾百萬次甚至幾千萬次，但是相對(duì)于總狀態(tài)的四億來說，尋找到最優(yōu)解的幾率不是很大。有沒有更好的方法呢？我們剛才是用隨機(jī)化算法直接出解，準(zhǔn)確性不太好，為了增加準(zhǔn)確性，那么我們嘗試一下用隨機(jī)化來縮小區(qū)

6、域范圍。我們建立一個(gè)矩陣P，P[X,Y]表示第一個(gè)鋸木場(chǎng)建立在X，第二個(gè)鋸木場(chǎng)建立在Y時(shí)的總運(yùn)費(fèi)。一開始時(shí)，矩陣的邊長(zhǎng)為N。我們隨機(jī)尋找一定數(shù)量的點(diǎn)(如下左圖所示，取點(diǎn)數(shù)量應(yīng)該充分利用時(shí)限并且注意效率，由于矩陣的大小一直在變化，推薦使用矩陣大小的定比確定取點(diǎn)數(shù)量)，計(jì)算出它們的值，取其最小點(diǎn)，以這個(gè)點(diǎn)為新矩陣的中心，以現(xiàn)在矩陣的邊長(zhǎng)的3/4的長(zhǎng)度為新矩形的邊長(zhǎng)（如下右圖所示），從原來的矩陣中取出一塊作為新矩陣的范圍(若新矩陣的范圍出了原矩陣的邊界就將其向里移動(dòng)到原矩陣內(nèi))，然后繼續(xù)在新矩陣中重復(fù)這樣的操作，直至新矩陣足夠小時(shí)，我們即可枚舉新矩陣上的每一個(gè)點(diǎn)，取其中最小值

7、作為答案。我們驚喜地發(fā)現(xiàn)，這種隨機(jī)化算法對(duì)于測(cè)試數(shù)據(jù)能夠全部通過！通過這道題目可以看出，隨機(jī)化算法的靈活多變使得它的具有更為廣闊的運(yùn)用范圍，在許多看似難以入手的地方通過巧妙地運(yùn)用發(fā)光發(fā)熱。而這樣的多變性也使得我們需要靈活恰當(dāng)?shù)剡\(yùn)用隨機(jī)化算法才能發(fā)揮出它的優(yōu)勢(shì)。隨機(jī)化算法并不只是簡(jiǎn)單地隨便亂來，使用隨機(jī)化算法的時(shí)候與其他算法一樣值得細(xì)細(xì)斟酌，需要匠心獨(dú)運(yùn)。下面，讓我們來看看隨機(jī)化算法在實(shí)際比賽中的運(yùn)用解析。實(shí)戰(zhàn)解析例題：小H的聚會(huì)(NOI2005)小H從小就非常喜歡計(jì)算機(jī)，上了中學(xué)以后，他更是迷上了計(jì)算機(jī)編程。經(jīng)過多年的不懈努力，小H幸運(yùn)的