摘 ?要：結(jié)合最小支撐樹問題和裝箱問題，該文研究了一類新的組合優(yōu)化問題：給定權(quán)重圖和一種長度為L的特定材料，要在圖G中尋找一顆支撐樹，并用給定的材料來構(gòu)建支撐樹的邊，支撐樹的總構(gòu)建費(fèi)用包括材料費(fèi)用和構(gòu)建費(fèi)用兩部分，目標(biāo)是使得總構(gòu)建費(fèi)用達(dá)到最小。該問題是NP—難的，不存在多項(xiàng)式時(shí)間算法，除非P=NP。該文對所提問題設(shè)計(jì)了一個(gè)2—近似算法，并分析了算法的復(fù)雜性，證明了算法的近似度。

關(guān)鍵詞：支撐樹 ?裝箱 ?NP—難 ?近似算法

中圖分類號(hào)：TP301.6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1672-3791（2019）06（a）-0228-02

1 ?問題描述及分析

我們可以將該實(shí)際問題抽象成如下數(shù)學(xué)模型。

問題1 給定權(quán)重圖和一種長度為L的特定材料，其中V表示圖G的頂點(diǎn)集，E表示圖G的邊集，為滿足的長度函數(shù)，為構(gòu)建費(fèi)用函數(shù)，假定一根長度為L的特定材料費(fèi)用為c0，現(xiàn)需要在圖G中尋找一棵支撐樹T，并用該特定材料的部分或者全部作為連接支撐樹邊的材料（要求連接支撐樹T邊的材料只能來自于某一根材料的部分或者全部，即不允許對料頭進(jìn)行拼接使用），目標(biāo)是使構(gòu)建支撐樹T的總費(fèi)用（k為使用材料的總根數(shù)）達(dá)到最小。

一維裝箱問題可以在多項(xiàng)式時(shí)間內(nèi)規(guī)約到問題1，因?yàn)橐痪S裝箱問題是NP—難的，所以問題1也是NP—難的，從而問題1不存在多項(xiàng)式時(shí)間算法，除非P=NP。下面給出求解該問題的一個(gè)近似算法，算法的總體思路如下。

第一步，對給定的權(quán)重圖，計(jì)算出構(gòu)建邊e所需的總構(gòu)建費(fèi)用c'（e）。構(gòu)建邊e的總費(fèi)用包括構(gòu)建費(fèi)用和材料費(fèi)用兩部分，構(gòu)建費(fèi)用c（e）已知，而材料費(fèi)用需要由該邊的長度w（e）折算出來（一根長度為L的特定材料費(fèi)用為c0，長度為w（e）的邊的材料費(fèi)用為），從而邊e的總構(gòu)建費(fèi)用為。以原圖G中的頂點(diǎn)集V、邊集E分別為頂點(diǎn)集和邊集，以每條邊的總構(gòu)建費(fèi)用c'（e）為權(quán)重，構(gòu)建一個(gè)新的權(quán)重圖。

第二步，在新權(quán)重圖中調(diào)用Prim算法，尋找出一棵以c'為權(quán)重的最小支撐樹T。

第三步，記第二步中尋找到的最小支撐樹T上的所有邊為，將這些邊的長度看成物體的大小，特殊材料的長度L看成箱子容量，調(diào)用FFD算法得到材料的截?cái)喾桨福疵恳桓L度為L的材料截?cái)喑啥嗌俣?，每一段有多長的具體方案），算法求出所使用的箱子數(shù)即為所需材料的根數(shù)k，材料的截?cái)喾桨讣礊椴牧系氖褂梅桨福纱丝梢杂?jì)算出構(gòu)建支撐樹T的總費(fèi)用。

2 ?算法設(shè)計(jì)與算法分析

2.1 算法設(shè)計(jì)

2.2 算法分析

引理1 設(shè)有n個(gè)物品a1，a2，…，an，其長度滿足0≤s（ai）≤L（i=1，2，，n），若用FFD算法將物品裝入長度為L的箱子，記算法輸出的箱子個(gè)數(shù)為m，則。

證明 按照一維裝箱問題的FFD算法，首先需要將物品a1，a2，…，an的大小按非增順序排列，不失一般性，假設(shè)排列之后的大小順序?yàn)椋骸ＴO(shè)算法結(jié)束后所使用的箱子依次為B1，B2，…，Bm，第i個(gè)箱子Bi中所裝物體的容量用來表示。按照FFD算法的執(zhí)行過程可知，除第m個(gè)箱子Bm之外的其余箱子所裝物體的容量一定滿足，并且一定成立（否則第m個(gè)箱子Bm中物品可以裝入第1個(gè)箱子B1中，從而不會(huì)開啟第m個(gè)箱子Bm，矛盾）。從而有：

定理1 算法1是解決問題1的一個(gè)2—近似算法，其算法復(fù)雜度為。

證明 假設(shè)問題1 的最優(yōu)支撐樹為T*，所需材料的根數(shù)為k*，則實(shí)例的最優(yōu)費(fèi)用值，記算法1解決問題1的得到的支撐樹為T，所需材料的根數(shù)為k，對應(yīng)的費(fèi)用值。因?yàn)樗惴?是以c'為權(quán)重的最小支撐樹，從而有，即，由引理1知，另一方面，從而，也即是OUT<2·OPT。

算法1中，步驟1的時(shí)間復(fù)雜度為，步驟2的時(shí)間復(fù)雜度為，步驟3的時(shí)間復(fù)雜度為，故整個(gè)算法的時(shí)間復(fù)雜度為。

3 ?結(jié)語

最小支撐樹問題在通信工程以及網(wǎng)絡(luò)運(yùn)輸布局等問題中有著普遍應(yīng)用。該文基于最小支撐樹問題及一維裝箱問題的相關(guān)算法，對提出的特定材料構(gòu)建支撐樹問題給出了一個(gè)2—近似算法，并證明了算法的近似度。因?yàn)樽钚≈螛鋯栴}存在多項(xiàng)式時(shí)間內(nèi)的最優(yōu)算法，一維裝箱問題是NP—難的，目前最好近似度為—近似，因此筆者猜想，問題1還可以進(jìn)一步改進(jìn)近似度。

參考文獻(xiàn)

[1] 謝政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].2版.長沙：國防科技大學(xué)出版社，2003.

[2] 高隨祥.網(wǎng)絡(luò)與網(wǎng)絡(luò)流理論[M].北京：高等教育出版社，2009.

[3] 文永松.多材料Terminal Steiner樹拼接問題的近似算法研究[J].現(xiàn)代電子技術(shù)，2018（10）：28-30.

[4] 何帥.網(wǎng)絡(luò)中路的構(gòu)建問題[D].云南大學(xué)，2011.