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

由圖論問題淺析算法優(yōu)化圖論是數(shù)學(xué)的一個(gè)分支，它以圖為研究對(duì)象，研究節(jié)點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法。2圖論問題與信息學(xué)競(jìng)賽聯(lián)系緊密，經(jīng)典的圖論模型以及相關(guān)算法已成為競(jìng)賽中不可或缺的知識(shí)?；A(chǔ)圖論知識(shí)優(yōu)化是一個(gè)逐步發(fā)現(xiàn)并利用問題的特殊之處、使算法更有針對(duì)性的過程。解決問題原始算法優(yōu)秀算法優(yōu)化

針對(duì)性化3圖的匹配：圖中任何兩條邊都沒有共同頂點(diǎn)的子圖。二分圖的最大匹配：二分圖中邊數(shù)最多的匹配。4在二分圖中加入源點(diǎn)、匯點(diǎn)，改為網(wǎng)絡(luò)。5在二分圖中加入源點(diǎn)、匯點(diǎn)，改為網(wǎng)絡(luò)。ST0/160/10/10/10/10/10/10/10/10/1廣搜可增廣鏈ST0/170/10/10/10/10/10/10/10/10/1a

所有邊的容量均為18不記錄容量ST0/190/10/10/10/10/10/10/10/10/1ST010000010101010101010110101010a

所有邊的容量均為111不記錄容量b與源點(diǎn)、匯點(diǎn)相連的邊的流量可由其他邊的流量推出改為記錄點(diǎn)的匹配情況1ST00001111151024334150612a

所有邊的容量均為113不記錄容量與源點(diǎn)、匯點(diǎn)相連的邊的流量可由其他邊的流量推出改為記錄點(diǎn)的匹配情況可增廣鏈結(jié)構(gòu)特殊ST41620314052614a

所有邊的容量均為115不記錄容量與源點(diǎn)、匯點(diǎn)相連的邊的流量可由其他邊的流量推出改為記錄點(diǎn)的匹配情況可增廣鏈結(jié)構(gòu)特殊只搜索中間部分4501602403130410520616容量特殊調(diào)整存儲(chǔ)方式17網(wǎng)絡(luò)結(jié)構(gòu)特殊改進(jìn)搜索算法設(shè)計(jì)網(wǎng)絡(luò)流算法時(shí)的兩個(gè)實(shí)用優(yōu)化手段減少存儲(chǔ)空間減少運(yùn)行時(shí)間尋找特別之處

－ 優(yōu)化的根本途徑18經(jīng)驗(yàn)?zāi)托撵`感速度慢19占用空間過大難以實(shí)現(xiàn)難以記憶時(shí)間復(fù)雜度空間復(fù)雜度編寫難度思維難度不能完全解決問題正確率面對(duì)難題時(shí)，我們難免會(huì)有意或無意地設(shè)計(jì)出有漏洞的算法簡(jiǎn)單處理、提高正確率分析問題、糾正錯(cuò)誤放棄算法、另尋他解20加入特殊判斷過程隨機(jī)化＋重復(fù)求解最優(yōu)化問題21取重復(fù)求解得到的最優(yōu)值判定性問題正確率大于50％可以正確判斷“是”、“否”中的一個(gè)方面……誤解模型的性質(zhì)22猜想錯(cuò)誤忽略算法細(xì)節(jié)《Fishing

Net》《Flying

Right》《Cow

Patterns》一條航線上有N個(gè)機(jī)場(chǎng)，編號(hào)1到N。有K群牛等待乘坐飛機(jī)，第i群牛中有Mi頭牛，它們要從Si機(jī)場(chǎng)飛到Ei機(jī)場(chǎng)（Si小于Ei）。請(qǐng)問一架可承載C頭牛的飛機(jī)從1號(hào)機(jī)場(chǎng)飛到N號(hào)機(jī)場(chǎng)最多可以把多少頭牛送到目的地？這當(dāng)中，可以將一群牛拆散，只將其中的一部分帶到目的地。23機(jī)場(chǎng)數(shù)：牛群數(shù)：每群中的牛數(shù)：飛機(jī)容量：1≤N≤10,0001≤K≤50,000i1≤M

≤C1≤C≤100逐一考慮每個(gè)座位？244每個(gè)單位流對(duì)應(yīng)一個(gè)座位1

2

3群A容量：邊所對(duì)應(yīng)的群中牛的個(gè)數(shù)

費(fèi)用：-1（為了適應(yīng)最小費(fèi)用流）為空閑的座位加入輔助邊容量無窮大、費(fèi)用為零費(fèi)用為-2群B25算法的時(shí)間復(fù)雜度為O(K*N*C),無法承受題目給出的數(shù)據(jù)規(guī)模26另一方面，在這個(gè)十分特殊的圖上直接套用最小費(fèi)用流的算法未免有些浪費(fèi)如何優(yōu)化？尋找可增廣鏈時(shí)考慮后向邊使得后續(xù)過程可以調(diào)整已擴(kuò)展的流，解決了后效性問題忽略后向邊相當(dāng)于逐一為每個(gè)座位選擇運(yùn)送牛數(shù)最多的方案，選擇后不再改動(dòng)用動(dòng)態(tài)規(guī)劃求解，時(shí)間復(fù)雜度為O(K*C)，可以接受27283214A牛B牛C牛D牛假設(shè)四條邊都只代表一頭牛，而飛機(jī)上有兩個(gè)座位對(duì)當(dāng)前座位“同樣優(yōu)”的兩條邊可能會(huì)對(duì)最終結(jié)果有不同的影響需要進(jìn)一步判斷邊的優(yōu)劣關(guān)系cbad一條邊含有兩個(gè)參數(shù)：

設(shè)法減少一個(gè)起點(diǎn)、終點(diǎn)-----換個(gè)角度看問題-----假設(shè)飛機(jī)正停在某個(gè)機(jī)場(chǎng)

選擇目的地最近的！選擇這一條29將所有邊按照終點(diǎn)排序30在每個(gè)機(jī)場(chǎng)攜帶目的地最近的C頭牛繼續(xù)飛行直接實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(N*C)問題解決分析錯(cuò)誤的能力為大膽猜想提供了保障思路受阻猜想錯(cuò)誤算法問題解決31