技能集擴張問題的組合最優化方法

摘要：最優技能集擴張問題是從一個已有技能集擴張為一個要求技能集,使得擴張過程的獲取費用為最小.目前文獻中已有基于整數規劃的數值方法.本文建立有向網絡的連接模型,并提出組合最優化的研究途徑.主要結果是證明如下結論:1)問題是強NP-困難的;2)當中間頂點數是常數時,問題可在多項式時間求解;3)問題存在性能比為2的近似算法.此外,本文還提供精確算法(分枝定界算法)及啟發式算法.