信息系統(tǒng)中的組合優(yōu)化問題研究.pdf

1、在實(shí)際應(yīng)用領(lǐng)域產(chǎn)生的許多組合優(yōu)化問題,如工件的排序加工問題、旅行售貨員問題、裝箱問題和頻道分配問題都是NP困難問題.對(duì)于這類問題,從數(shù)學(xué)的角度出發(fā),需要考慮問題的模型,求解此問題.在P≠NP的假設(shè)被人們廣泛地認(rèn)可下,在多項(xiàng)式時(shí)間內(nèi)尋找此類問題的精確解是不可行的.因此,設(shè)計(jì)這類問題的近似算法,已成為計(jì)算機(jī)科學(xué)和數(shù)學(xué)中學(xué)術(shù)探討的一個(gè)無(wú)法抗拒的主題.該文研究了從實(shí)際應(yīng)用中產(chǎn)生的兩個(gè)組合優(yōu)化問題:帶頻道負(fù)荷的頻道分配問題和帶拒絕的裝箱問題.第二

2、章討論了一般網(wǎng)絡(luò)的帶頻道負(fù)荷經(jīng)束的頻道分配問題.概括地說,該文的主要?jiǎng)?chuàng)新點(diǎn)有1.推廣了頂點(diǎn)染色的概念.在給出的圖模型基礎(chǔ)上,定義并討論了k-m限制多重染色.當(dāng)其中的參數(shù)取不同的特定值時(shí),k-m限制多重染色分別對(duì)應(yīng)于圖的頂點(diǎn)染色和頂點(diǎn)多重染色.并利用序列算法得到該染色的一些理論結(jié)果與相應(yīng)的頂點(diǎn)染色和多重染色的有關(guān)結(jié)論.2.給出了求星圖和樹圖的μ-定向最優(yōu)解的多項(xiàng)式時(shí)間算法.首先找到星圖的μ-定向最優(yōu)解,而后利用動(dòng)態(tài)規(guī)劃思想,從樹的最底層葉