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

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