【摘 要】
：
最短路问题在网络流问题中占据着核心地位,一维装箱问题是组合最优化中的经典问题。以这两个问题为基础,研究了一个新的最优化问题:给定一个赋权连通网络G=(V,E;w;s,t),其中s
论文部分内容阅读
最短路问题在网络流问题中占据着核心地位,一维装箱问题是组合最优化中的经典问题。以这两个问题为基础,研究了一个新的最优化问题:给定一个赋权连通网络G=(V,E;w;s,t),其中s,t是两个固定的顶点,w:E→(R)+是边的长度函数。现有一种长度为L的材料,要用这种材料构建从顶点s到顶点t的路P,这里允许w(e)≥L。目标是使所用材料数尽可能的少。该问题是NP-难的。本文对该问题设计了一个2-近似算法,并加以改进,设计了一个7/4-渐近近似算法,同时给出了相应的程序设计。
本文由以下四个章节构成。
在第一章中,回顾了问题的由来,给出了到目前为止的一些研究成果;
在第二章中,给出本文所涉及的定义,概念和符号;
在第三章中,给出最短路问题及装箱问题相关的算法和定理;
在第四章中,讨论最短路的网络构建问题,给出了相应算法;
最后,本文给出相关结论以及未来的研究方向。
其他文献
图上的旋转游走是随机游走的一种确定性的对比模型。本文研究了在特定的初始旋转配置下，Zd上n个粒子从原点出发依次序进行旋转游走，击中原点或者无穷远点停止。当维数d≥3时，逃
干部监督是党的三代领导核心的一贯要求,加强对领导干部的监督,是整个干部工作的一个重要环节。在新的历史条件下,干部队伍和干部工作中出现了许多新情况,一些惰性的、消极
一维装箱问题及Steiner树问题都是组合最优化中的经典问题，它们在实际生活中都有着广泛的应用。基于这两个问题，我们给出了本文研究的问题:给定一个赋权图G=（V,E;w）及常数L，其中w(
分布式模型预测控制是解决大规模系统控制的一种有效方法,能在尽可能简单的系统通信方式和尽可能小的通信负担之下达到尽可能好的控制性能,同时保证算法的收敛性和系统的稳定
1994年,Shor利用量子纠缠性和叠加性提出了著名的大数因子分解的量子算法hor算法。利用该算法的思想并借助量子计算机,可以在多项式时间内分解大整数、解决一些有限交换群(如
随着中国科技的发展和不断进步,多智能体系统在工程当中的应用越来越广泛,尤其是在航空航天、机器人等人工智能领域都起着越来越重要的作用。多智能体系统是由许许多多的智能
正交辛型李超代数osp(k|2n)(k=2m或2m+1)是一大类很重要的有限维单李超代数,计算它的有限维不可约模的特征标一直是李超代数理论的中心问题之一。本文通过传递函子来研究正交
超指数一超几何-q-超几何项是一类基本的特殊函数.如何把这类函数分解为更简单的函数的乘积,和如何对这类函数进行代数运算是符号计算的基本问题之一.
zeilberger引进的