瓶颈Steiner树问题-管理科学与工程专业毕业论文.pdf

瓶颈Steiner树问题 摘要 给出礼个点，用最短的距离将这些点连接起来的树就是最小steiner树． Steiner树问题是组合最优化的重要组成部分，steiner树问题广泛应用在管 理科学、工程技术等多个领域，得到越来越多人的关注．平面上的steiner树 问题在计算机电路板、长距离电话线、邮递路径的设计方面都有着广泛的应 用．它在通讯、交通、Ⅵ．sI设计中也起到了非常重要的作用．在管理科学 中，图的steiner树问题在销售和运输系统的设计、VLsI设计、网络流等方 面也起到指导作用． steiner树问题开始应用于生命科学，解决物种演化问 题，Ste妇r树问题应用范围很广，成为多个学科专业领域的专家学者的研 究热点． 本文将继续对图上的steiner树问题进行研究，文中提出满瓶颈steiller 树问题的模型．给出满瓶颈steiner树问题的性质，给出了多项式时间算法， 并用数值例子说明此算法的正确性和有效性． 近二十年，反问题在管理科学中应用较多，成为被关注的焦点，很多问 题可以归结到数学问题的反问题解决，如反最小支撑树问题、反最短路问 题、反最大流问题等，各种问题的总体思想是相似的，但它们的方法各不相 同．反组合最优化兴起于对道路的设计，另外。它在生物结构科学及一些花 费问题上应用尤为突出． 在本文中，通过对反问题的学习，在研究反瓶颈支撑树问题的性质与算 法的基础上，我们提出反瓶颈steiner树问题模型，研究问题的性质，给出 zz范数下有边界限制的反瓶颈steiner树问题的算法，并证明算法的正确性 及时间复杂性． 题，多项式算法，时间复杂性 BottIeneckSteiner‘rreeProbIem Ab啦恰ct：Given8set a七r∞0f conne!ctthe of俺points，丑ndingminim啪lIen戥h七o of nisca№daminim：眦SteiⅡer is8n tree．Steiner切∞pr砒Ilem point8 import毗 8ection tree c8n oftheco衄binatiorial be optimizati0Inproblem8．Steinerproblem in 80on。Moreand 8ppliedwidelyman戳rementsdence，en酉nIee血gte(岫lo帮and 皿10re 8rec(mcer列edabouttllisaera．Steinertree inthe people p]吣blem computer cir咖t liIl鹤舭ldthe of routehave bo舭d，the10n分di8tancetelephone d鹤ignpostaLl awider it山o ran_ge印plication8．Inthe咖Imlnjcations，tr龇18port，VLSId鹤ign a treein 8Lls0h够 science，Steiner pla．y．8v明了impo毗锄七role．Inm锄娜；ement