獎(jiǎng)勵(lì)-收集Steiner樹問題的精確算法

摘要： 獎(jiǎng)勵(lì)-收集Steiner樹問題是圖的Steiner最小樹問題的衍生,同時(shí)也是組合優(yōu)化中的NP-hard問題。首先,提出該問題的數(shù)學(xué)性質(zhì)并給出證明,利用數(shù)學(xué)性質(zhì)能降低該問題的規(guī)模;其次,基于該問題的數(shù)學(xué)性質(zhì)設(shè)計(jì)出上下界子算法、降階子算法和回溯子算法,通過上下界子算法和降階子算法可以降低該問題解空間的規(guī)模,從而縮短回溯子算法的搜索時(shí)間,進(jìn)而降低求解該問題最優(yōu)解的時(shí)間;最后,應(yīng)用案例... （共9頁）