由圖論問題淺析算法優(yōu)化

1、2006年全國信息學(xué)冬令營講座第1頁共20頁由圖論問題淺析算法優(yōu)化武鋼三中賈由【摘要】論文以圖論問題為對(duì)象、以算法優(yōu)化為主題、以分類和舉例為基本模式進(jìn)行了一系列探討。第一部分引言簡單地介紹了圖論與信息學(xué)競賽的關(guān)系；第二部分分析了算法優(yōu)化的根本途徑：尋找特別之處；第三部分從算法的糾錯(cuò)入手，詳細(xì)討論其中的方法，進(jìn)一步展示了發(fā)現(xiàn)問題的特殊點(diǎn)對(duì)算法優(yōu)化的推動(dòng)作用。【關(guān)鍵字】圖論算法優(yōu)化錯(cuò)誤分析【正文】一、引言一、引言圖論是一個(gè)十分有趣而且與信息

2、學(xué)競賽聯(lián)系緊密的數(shù)學(xué)分支。隨著圖論問題的日漸增多，一些經(jīng)典圖論模型與它們的相關(guān)算法已成為競賽中不可或缺的知識(shí)。與此同時(shí)，題目也越來越注重模型的轉(zhuǎn)換與算法的優(yōu)化。這意味著在將知識(shí)轉(zhuǎn)變?yōu)榉謹(jǐn)?shù)的過程中，我們需要做出更多的努力。本文以其中的算法優(yōu)化為主題，嘗試了一些相關(guān)的歸納與討論。另外，由于黑箱測(cè)試的緣故，我們所體驗(yàn)到的信息學(xué)可以說是一個(gè)以結(jié)果論成敗的學(xué)科。這是很好的，因?yàn)榻Y(jié)果是對(duì)歷史的總結(jié)。但無論如何，對(duì)于一次以優(yōu)化為主題的討論來說，得到的

3、最優(yōu)算法僅僅是用來證明我們的優(yōu)化過程是切實(shí)而有效的。二、尋找特別之處二、尋找特別之處——優(yōu)化的根本途徑優(yōu)化的根本途徑2.1介紹介紹每一個(gè)讓算法更加漂亮的改進(jìn)都可以稱為優(yōu)化。不過在整體考慮一個(gè)問題時(shí)，優(yōu)化的過程應(yīng)該包括從原始算法到一個(gè)優(yōu)秀算法當(dāng)中的所有改進(jìn)。這通常是一個(gè)逐步發(fā)現(xiàn)并利用問題的特殊之處、使算法更有針對(duì)性的過程。做好優(yōu)化的根本在于找出題目的特別之處。這是一個(gè)寬泛的想法，沒什么步驟和訣竅可言。解決具體問題時(shí)，我們只能靠廣泛的優(yōu)化經(jīng)

4、驗(yàn)、充足的耐心以及一部分的靈感因素。關(guān)于經(jīng)驗(yàn)，之前的幾篇論文已經(jīng)分別就一些有共同特征的題目介紹了深入挖掘信息的具體過程。這一章不再深入探討某類問題，而是通過一個(gè)經(jīng)典算法對(duì)“尋找特別之處”作出解釋。2006年全國信息學(xué)冬令營講座第3頁共20頁ST圖1建立網(wǎng)絡(luò)將試驗(yàn)田轉(zhuǎn)化為點(diǎn)、并連接相鄰的試驗(yàn)田后可以發(fā)現(xiàn)，我們得到的是一個(gè)二分圖。通過對(duì)原圖的黑白染色，可以把其中的一部分稱為白點(diǎn)、另一部分稱為黑點(diǎn)。由二分圖建立網(wǎng)絡(luò)：加入源點(diǎn)和匯點(diǎn)，從源點(diǎn)向每

5、個(gè)白點(diǎn)引一條邊，容量為白點(diǎn)對(duì)應(yīng)試驗(yàn)田的面積；從每個(gè)黑點(diǎn)向匯點(diǎn)引邊，容量為該黑點(diǎn)的對(duì)應(yīng)面積。最后將相鄰點(diǎn)之間的邊改為網(wǎng)絡(luò)中的邊，由白點(diǎn)指向黑點(diǎn)，容量為正無窮。方案對(duì)應(yīng)的割：將方案中所選的白點(diǎn)和未選的黑點(diǎn)再加上源點(diǎn)劃為一個(gè)集合，其它點(diǎn)劃到另一個(gè)幾何，就得到了一個(gè)割。直接把這個(gè)過程反過來，我們很容易由割得到一個(gè)方案。在這個(gè)對(duì)應(yīng)中：一、不合法方案對(duì)應(yīng)的割均為正無窮；二、在合法方案對(duì)應(yīng)的割中，割上的點(diǎn)代表了方案沒有取到的邊。所以當(dāng)割的容量最小時(shí)、

6、方案選取的面積最大，而根據(jù)最大流最小割定理，我們可以通過求網(wǎng)絡(luò)最大流得到它的最小割。廣搜可增廣鏈廣搜可增廣鏈這同樣是由二分圖轉(zhuǎn)換來的網(wǎng)絡(luò)，但是邊的容量一般化了。我們?nèi)匀豢梢圆凰阉魇孜矁蓷l邊，不同的是以某一個(gè)“新源點(diǎn)”（原可增廣鏈上的第二個(gè)點(diǎn)）為起點(diǎn)的廣搜可能要進(jìn)行多次，次數(shù)最多等于源點(diǎn)到它的邊的容量；同理，一個(gè)“新匯點(diǎn)”可以容納多個(gè)可增廣鏈。另外，為白點(diǎn)和黑點(diǎn)分別設(shè)計(jì)擴(kuò)展過程也可以大大提高算法的效率。三、改進(jìn)錯(cuò)誤算法三、改進(jìn)錯(cuò)誤算法——

7、更靈活的優(yōu)化更靈活的優(yōu)化3.1介紹介紹我們常說的算法優(yōu)化有四個(gè)方向：時(shí)間復(fù)雜度的優(yōu)化、空間復(fù)雜度的優(yōu)化、編寫難度的優(yōu)化以及思維難度的優(yōu)化。但是正如標(biāo)題所表達(dá)的，這一部分的內(nèi)容是如何提高算法的正確率。糾錯(cuò)也算是優(yōu)化嗎？如果你也有同樣的疑問，那你一定是想到代碼的查錯(cuò)上去了。提高算法的正確率當(dāng)然是對(duì)算法的優(yōu)化。甚至，算法的錯(cuò)誤常常也是由于對(duì)題目信息的不充分利用導(dǎo)致的，只不過除此之外還有很多別的原因，我們一會(huì)兒就會(huì)進(jìn)一步分析到它們。應(yīng)對(duì)錯(cuò)誤需要