從一道題目的解法試談網(wǎng)絡(luò)流的構(gòu)造與算法(編輯修改稿)
2025-07-04 16:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 級(jí)。無(wú)論如何剪枝優(yōu)化，也擺脫不了非多項(xiàng)式。3. 動(dòng)態(tài)規(guī)劃本題的結(jié)構(gòu)是有向無(wú)環(huán)圖，而非樹(shù)形結(jié)構(gòu)，不適合動(dòng)態(tài)規(guī)劃。如果一定要做，實(shí)質(zhì)類(lèi)似于搜索，由于狀態(tài)數(shù)量眾多，仍是指數(shù)級(jí)的時(shí)間復(fù)雜度。4. 網(wǎng)絡(luò)流流網(wǎng)絡(luò)的構(gòu)造方法：建立N頂點(diǎn)代表N個(gè)項(xiàng)目，另外增加源s與匯t。若項(xiàng)目i必須依賴(lài)于項(xiàng)目j，則從頂點(diǎn)i向頂點(diǎn)j引一條容量為無(wú)窮大的弧。對(duì)于每個(gè)項(xiàng)目i，若它的預(yù)算C為正（盈利），則從源s向頂點(diǎn)i引一條容量為C的邊；若它的預(yù)算C為負(fù)（投資），則從頂點(diǎn)i向匯t引一條容量為C的邊。求這個(gè)網(wǎng)絡(luò)的最小割（S, T），設(shè)其容量C(S,T)＝F。設(shè)R為所有盈利項(xiàng)目的預(yù)算之和（凈利潤(rùn)上界），那么RF就是最大凈利潤(rùn)；S中的頂點(diǎn)就表示最優(yōu)方案所選擇的項(xiàng)目。 5 1315264 +∞ +∞ 1st +∞ +∞ 3 +∞
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1