瓶颈Steiner树问题

来源 :沈阳师范大学 | 被引量 : 0次 | 上传用户:jianjian1985
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
给出n个点,用最短的距离将这些点连接起来的树就是最小Steiner树.Steiner树问题是组合最优化的重要组成部分,Steiner树问题广泛应用在管理科学、工程技术等多个领域,得到越来越多人的关注.平面上的Steiner树问题在计算机电路板、长距离电话线、邮递路径的设计方面都有着广泛的应用.它在通讯、交通、VLSI设计中也起到了非常重要的作用.在管理科学中,图的Steiner树问题在销售和运输系统的设计、VLSI设计、网络流等方面也起到指导作用. Steiner树问题开始应用于生命科学,解决物种演化问题,Steiner树问题应用范围很广,成为多个学科专业领域的专家学者的研究热点. 本文将继续对图上的Steiner树问题进行研究,文中提出满瓶颈Steiner树问题的模型.给出满瓶颈Steiner树问题的性质,给出了多项式时间算法,并用数值例子说明此算法的正确性和有效性. 近二十年,反问题在管理科学中应用较多,成为被关注的焦点,很多问题可以归结到数学问题的反问题解决,如反最小支撑树问题、反最短路问题、反最大流问题等,各种问题的总体思想是相似的,但它们的方法各不相同.反组合最优化兴起于对道路的设计,另外,它在生物结构科学及一些花费问题上应用尤为突出. 在本文中,通过对反问题的学习,在研究反瓶颈支撑树问题的性质与算法的基础上,我们提出反瓶颈Steiner树问题模型,研究问题的性质,给出l1范数下有边界限制的反瓶颈Steiner树问题的算法,并证明算法的正确性及时间复杂性.
其他文献
公共基础设施建设是国民经济和社会发展最重要的组成部分,保障基础设施增长与经济增长相协调对城市和社会的发展至关重要。改革开放以来,我国经济的高速发展对公共基础设施的
随着我国加入WTO以及经济全球化和贸易自由化进程的加快,技术性贸易壁垒(Technical Barriers to Trade,TBT)已成为阻止我国出口的主要因素,而且还在逐年加重。 在电子信息