论文部分内容阅读
一维装箱问题是组合最优化中的经典问题，而最短路问题在网络流问题中占据着核心地位。在这两个问题的基础之上，我们研究了一个新的最优化问题：给定一个赋权连通网络N=(V,A；ω，c；s，t)，其中s，t为网络N中两个固定顶点，ω：A→R+为边的长度函数，c：A→R+为边的构建费用函数。现有一种长度为L的材料，每根材料的购买费用是c0，我们要用这种材料构建从顶点s到顶点t的路P，并且对于路P中的每一条边e=(u，υ)，连结顶点u和顶点υ的的材料只能来自某一根材料的部分或全部，目标是使总费用(?)c(e)+m·c0尽可能小，这里m为所用材料根数。即使对于(A)e(?)A，c(e)=0，该问题也是NP-难的。在本文中，对该问题我们设计了一个2-近似算法，对问题的特殊情况我们设计了一个7/4-渐近近似算法，并给出了相应的程序设计。
论文由以下五章构成：
第一章：回顾了问题的由来，理论形成，给出了到目前为止的一些研究成果；
第二章：给出文中所出现的定义，概念和符号；
第三章：给出最短路问题及装箱问题相关的算法和性质；
第四章：讨论网络中路的构建问题，给出了相应算法；
第五章：给出相关结论以及未来的研究方向。