特定材料构建支撑树问题的近似算法研究

摘  要：结合最小支撑树问题和装箱问题，该文研究了一类新的组合优化问题：给定权重图和一种长度为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.