摘要：最優(yōu)技能集擴(kuò)張問題是從一個已有技能集擴(kuò)張為一個要求技能集,使得擴(kuò)張過程的獲取費用為最小.目前文獻(xiàn)中已有基于整數(shù)規(guī)劃的數(shù)值方法.本文建立有向網(wǎng)絡(luò)的連接模型,并提出組合最優(yōu)化的研究途徑.主要結(jié)果是證明如下結(jié)論:1)問題是強(qiáng)NP-困難的;2)當(dāng)中間頂點數(shù)是常數(shù)時,問題可在多項式時間求解;3)問題存在性能比為2的近似算法.此外,本文還提供精確算法(分枝定界算法)及啟發(fā)式算法.
注：因版權(quán)方要求，不能公開全文，如需全文，請咨詢雜志社
