论文部分内容阅读
本文在一维装箱问题和具有终点的Steiner树问题的基础上研究了新的组合最优化问题，即网络中具有终点的Steiner树构建问题。此问题是NP-难的。本文对该问题的两种不同模型分别做了讨论。第一种模型:只有一种材料，且不含边的构建费用，对于这个模型本文设计了一个7-渐近近似算法;第二种模型:有多种材料的构建问题，本文设计了一个8-近似算法。最后，本文在附录中编程实现了相应的算法。
论文包括以下四章:
在第一章中，回顾了问题的来源及理论的形成过程，给出了具有终点的Steiner树以及装箱问题到目前为止的一些研究现状;
在第二章中，给出本文中所涉及的定义、概念和符号;
在第三章中，给出了具有终点的Steiner树问题及装箱问题的相关算法和性质;
在第四章中，讨论网络中具有终点的Steiner树的构建问题，并设计解决此问题的近似算法;
最后给出结论并展望此问题将来可能的研究方向。