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

1、由圖論問題淺析算法優(yōu)化圖論問題2 圖論是數(shù)學(xué)的一個分支，它以圖為研究對象，研究節(jié)點和邊組成的圖形的數(shù)學(xué)理論和方法。 圖論問題與信息學(xué)競賽聯(lián)系緊密，經(jīng)典的圖論模型以及相關(guān)算法已成為競賽中不可或缺的知識。算法優(yōu)化3基礎(chǔ)圖論知識優(yōu)化是一個逐步發(fā)現(xiàn)并利用問題的特殊之處、使算法更有針對性的過程。解決問題原始算法優(yōu)秀算法優(yōu)化針對性化例 二分圖的最大匹配4圖的匹配： 圖中任何兩條邊都沒有共同頂點的子圖。二分圖的最大匹配： 二分圖中邊數(shù)最多的匹配。網(wǎng)絡(luò)流模型5在二分圖中加入源點、匯點，改為網(wǎng)絡(luò)。網(wǎng)絡(luò)流模型6在二分圖中加入源點、匯點，改為網(wǎng)絡(luò)。ST0/10/10/10/10/10/10/10/10/10/1網(wǎng)絡(luò)

2、流算法7廣搜可增廣鏈ST0/10/10/10/10/10/10/10/10/10/1優(yōu)化方法8所有邊的容量均為1不記錄容量優(yōu)化方法9ST0/10/10/10/10/10/10/10/10/10/10000000000優(yōu)化方法10ST0000000000111111優(yōu)化方法11所有邊的容量均為1不記錄容量與源點、匯點相連的邊的流量可由其他邊的流量推出改為記錄點的匹配情況優(yōu)化方法121123456ST000011111504310優(yōu)化方法13所有邊的容量均為1不記錄容量與源點、匯點相連的邊的流量可由其他邊的流量推出改為記錄點的匹配情況可增廣鏈結(jié)構(gòu)特殊優(yōu)化方法14123456ST460102優(yōu)化方法

3、15所有邊的容量均為1不記錄容量與源點、匯點相連的邊的流量可由其他邊的流量推出改為記錄點的匹配情況可增廣鏈結(jié)構(gòu)特殊只搜索中間部分匈牙利算法1612345641624351000000回顧17容量特殊調(diào)整存儲方式網(wǎng)絡(luò)結(jié)構(gòu)特殊改進(jìn)搜索算法設(shè)計網(wǎng)絡(luò)流算法時的兩個實用優(yōu)化手段減少存儲空間減少運行時間小結(jié)18尋找特別之處 優(yōu)化的根本途徑經(jīng)驗 耐心 靈感優(yōu)化方向19速度慢占用空間過大難以實現(xiàn)難以記憶時間復(fù)雜度空間復(fù)雜度編寫難度思維難度 不能完全解決問題正確率應(yīng)對有缺陷的算法20面對難題時，我們難免會有意或無意地設(shè)計出有漏洞的算法簡單處理、提高正確率分析問題、糾正錯誤放棄算法、另尋他解快速處理21加入特殊判

4、斷過程隨機(jī)化重復(fù)求解最優(yōu)化問題取重復(fù)求解得到的最優(yōu)值判定性問題正確率大于50可以正確判斷“是”、“否”中的一個方面導(dǎo)致錯誤的原因22誤解模型的性質(zhì)猜想錯誤忽略算法細(xì)節(jié)Fishing NetFlying RightCow Patterns例 Flying Right23 一條航線上有N個機(jī)場，編號1到N。有K群牛等待乘坐飛機(jī)，第i群牛中有Mi頭牛，它們要從Si機(jī)場飛到Ei機(jī)場（Si小于Ei）。 請問一架可承載C頭牛的飛機(jī)從1號機(jī)場飛到N號機(jī)場最多可以把多少頭牛送到目的地？ 這當(dāng)中，可以將一群牛拆散，只將其中的一部分帶到目的地。輸入數(shù)據(jù)的規(guī)模24機(jī)場數(shù)：牛群數(shù)：每群中的牛數(shù)：飛機(jī)容量：1N10,0

5、001K50,0001MiC1C100逐一考慮每個座位？最小費用流容量：邊所對應(yīng)的群中牛的個數(shù)費用：-1（為了適應(yīng)最小費用流）為空閑的座位加入輔助邊容量無窮大、費用為零254321每個單位流對應(yīng)一個座位群A群B費用為-2最小費用流26算法的時間復(fù)雜度為O(K*N*C),無法承受題目給出的數(shù)據(jù)規(guī)模另一方面，在這個十分特殊的圖上直接套用最小費用流的算法未免有些浪費如何優(yōu)化？忽略后向邊27尋找可增廣鏈時考慮后向邊使得后續(xù)過程可以調(diào)整已擴(kuò)展的流，解決了后效性問題忽略后向邊相當(dāng)于逐一為每個座位選擇運送牛數(shù)最多的方案，選擇后不再改動用動態(tài)規(guī)劃求解，時間復(fù)雜度為O(K*C)，可以接受反例假設(shè)四條邊都只代表一頭牛，而飛機(jī)上有兩個座位對當(dāng)前座位“同樣優(yōu)”的兩條邊可能會對最終結(jié)果有不同的影響283214A牛B牛C牛D牛需要進(jìn)一步判斷邊的優(yōu)劣關(guān)系邊的優(yōu)劣關(guān)系29一條邊含有兩個參數(shù)： 起點、終點假設(shè)飛機(jī)正停在某個機(jī)場設(shè)法減少一個選擇目的地最近的！cbad-換個角度看問題-選擇這一條最終算法30將所有邊按照終點排序在每個機(jī)場攜帶目的地最近的C頭牛繼續(xù)飛行直接實現(xiàn)的時間復(fù)雜度為O(N*C)問題解決小結(jié)分析錯誤的能力為大膽猜想提供了保障31思路受阻猜想錯誤算法問題解決小結(jié)32提高算