论文部分内容阅读
一维装箱问题及Steiner树问题都是组合最优化中的经典问题，它们在实际生活中都有着广泛的应用。基于这两个问题，我们给出了本文研究的问题:给定一个赋权图G=（V,E;w）及常数L，其中w(:) E→(R)+为边的长度函数。要寻找一棵Steiner树T，T上的每一条边用长度为L的材料来构建，对于Steiner树的边e，如果w(e)＞L,用完整的材料L来构建，直到边剩余的长度不超过L,这里Steiner树的每条边至多只允许拼接一次料头（材料L用于构建某条边后所剩余的部分）。目标是使所用的材料根数达到最小。在本文中，对该问题我们设计了一个4-近似算法，对边进行分类处理后，我们设计了一个7/2-渐近近似算法。并给出了相应的程序设计。
本论文由下面的四章构成。
在第一章中，回顾了问题的由来及理论形成，给出了Steiner问题及装箱问题到目前为止的一些研究现状;
在第二章中，给出文中所出现的定义，定理和符号;
在第三章中，给出Steiner树问题及装箱问题相关的算法;
在第四章中，讨论了Steiner树构建问题，并给出了相应算法;
最后，给出相关结论。