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

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

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

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

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

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

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

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