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