特定材料構建支撐樹問題的近似算法研究

摘 ?要：結合最小支撐樹問題和裝箱問題，該文研究了一類新的組合優化問題：給定權重圖和一種長度為L的特定材料，要在圖G中尋找一顆支撐樹，并用給定的材料來構建支撐樹的邊，支撐樹的總構建費用包括材料費用和構建費用兩部分，目標是使得總構建費用達到最小。該問題是NP—難的，不存在多項式時間算法，除非P=NP。該文對所提問題設計了一個2—近似算法，并分析了算法的復雜性，證明了算法的近似度。

關鍵詞：支撐樹 ?裝箱 ?NP—難 ?近似算法

中圖分類號：TP301.6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1672-3791（2019）06（a）-0228-02

1 ?問題描述及分析

我們可以將該實際問題抽象成如下數學模型。

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

一維裝箱問題可以在多項式時間內規約到問題1，因為一維裝箱問題是NP—難的，所以問題1也是NP—難的，從而問題1不存在多項式時間算法，除非P=NP。下面給出求解該問題的一個近似算法，算法的總體思路如下。

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

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

第三步，記第二步中尋找到的最小支撐樹T上的所有邊為，將這些邊的長度看成物體的大小，特殊材料的長度L看成箱子容量，調用FFD算法得到材料的截斷方案（即每一根長度為L的材料截斷成多少段，每一段有多長的具體方案），算法求出所使用的箱子數即為所需材料的根數k，材料的截斷方案即為材料的使用方案，由此可以計算出構建支撐樹T的總費用。

2 ?算法設計與算法分析

2.1 算法設計

2.2 算法分析

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

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

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

證明 假設問題1 的最優支撐樹為T*，所需材料的根數為k*，則實例的最優費用值，記算法1解決問題1的得到的支撐樹為T，所需材料的根數為k，對應的費用值。因為算法1是以c'為權重的最小支撐樹，從而有，即，由引理1知，另一方面，從而，也即是OUT<2·OPT。

算法1中，步驟1的時間復雜度為，步驟2的時間復雜度為，步驟3的時間復雜度為，故整個算法的時間復雜度為。

3 ?結語

最小支撐樹問題在通信工程以及網絡運輸布局等問題中有著普遍應用。該文基于最小支撐樹問題及一維裝箱問題的相關算法，對提出的特定材料構建支撐樹問題給出了一個2—近似算法，并證明了算法的近似度。因為最小支撐樹問題存在多項式時間內的最優算法，一維裝箱問題是NP—難的，目前最好近似度為—近似，因此筆者猜想，問題1還可以進一步改進近似度。

參考文獻

[1] 謝政.網絡算法與復雜性理論[M].2版.長沙：國防科技大學出版社，2003.

[2] 高隨祥.網絡與網絡流理論[M].北京：高等教育出版社，2009.

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

[4] 何帥.網絡中路的構建問題[D].云南大學，2011.