《計算機應用研究》|Application Research of Computers

節點加權的Steiner樹問題的降階回溯算法

Backtracking algorithm with reduction for node-weighted steiner tree problem

免費全文下載 (已被下載 次)  
獲取PDF全文
作者 胡沁,寧愛兵,茍海雯,張惠珍
機構 上海理工大學 管理學院
統計 摘要被查看 次,已被下載
摘要 節點加權的Steiner樹問題是組合優化中一個經典的NP-Hard問題,現有算法研究該問題時存在時間復雜性高或無法得到最優解的缺點。針對現有算法的不足,提出了一個基于降階技術的回溯算法。該算法首先研究該問題的數學性質,利用數學性質對該問題進行降階以縮小問題的規模;接著提出上界子算法和下界子算法,利用上下界子算法對該問題的解空間樹進行剪枝,提高搜索效率;最后利用上下界子算法和數學性質設計了一個回溯算法求解該問題。示例分析以及實驗的結果表明,該算法不僅時間復雜性較低而且可以得到問題的最優解。
關鍵詞 節點加權的Steiner樹;上界;下界;回溯算法
基金項目 國家自然科學基金資助項目(71401106)
上海市一流學科建設項目(S1201YLXK)
本文URL http://www.048285.live/article/02-2020-11-011.html
收稿日期
修回日期
頁碼 -
中圖分類號 TP301.6
文獻標志碼
012曾道人三尾中特书