算法合集之淺析信息學(xué)中的“分”與“合”-閱讀頁(yè)
2024-11-02 18:36本頁(yè)面
【正文】 態(tài)規(guī)劃與貪心之所以不能得到正確解，其關(guān)鍵原因在于 —— 題目中存在著一個(gè)元素只能被取一次的限制，而對(duì)于這種限制各點(diǎn)被選取次數(shù)的題目，我們通常使用網(wǎng)絡(luò)流來(lái)解決，那么這道題是否也能通過(guò)轉(zhuǎn)化圖論模型來(lái)使用網(wǎng)絡(luò)流解決呢？答案是肯定的。 ?所有點(diǎn) i向點(diǎn) (i+1)連邊，容量為 +∞ ，費(fèi)用為 0 ?源 S向所有點(diǎn) i各連一條邊，容量為 +∞，費(fèi)用為 0 ?所有點(diǎn) i’ 向匯 T各連一條邊，容量為 +∞，費(fèi)用為 0 ?所有點(diǎn) i’ 向點(diǎn) (i+M)連邊，容量為 +∞ ，費(fèi)用為 0 3’ 2’ 1’ …… n’ 1 2 3 n T S …… 容量 = 1 費(fèi)用 = value[i] +∞ 0 [例三 ]最優(yōu)序列 —— 整體分析 ?構(gòu)圖完成之后，網(wǎng)絡(luò)中的每個(gè)單位流量表示一個(gè)子問(wèn)題的解，因此，我們只需要在網(wǎng)絡(luò)中尋找 K次最大費(fèi)用增廣路即可得到答案。 總結(jié) 分 合 對(duì)立 統(tǒng)一 “ 分”的思想幫助我們迅速地切入問(wèn)題核心，但若過(guò)分細(xì)化則會(huì)使問(wèn)題太過(guò)凌亂，失去求解的方向；而“合”的思想則以線(xiàn)串珠，使各種紛雜無(wú)序的問(wèn)題具有了整體性
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1