约束最优树论文_林大志

导读:本文包含了约束最优树论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:最优,组合,小树,算法,论文,Steiner。

约束最优树论文文献综述

林大志^[1]（2004）在《关于约束最优树问题的若干结果》一文中研究指出平面上的最短连线问题在交通运输、道路建设、VLSI设计中有广泛的应用。我们考虑的平面上的最短连线问题是只考虑平面上n个给定点及给定直线，距离为欧氏距离，所有连线构成以这些给定点为顶点集的支撑树，并考虑与直线相关联，所以称为约束最优树问题。本文主要研究了平面上约束最优树的若干模型及相关问题，其中直线L外有n个点，可以从直线L上引任意多直线，与n个点连接成连通网络，使总的连线长度最小。这是新提出的模型。对直线L上引出一个点的模型进行了进一步的探讨，并给出了相关的判定条件和若干结果。第二章，提出了具有任意多引出点的约束最优树问题，给出了解决此问题的方法，即把一个几何模型转化为图伦模型，把一个平面上满足约束条件的连接问题(称为问题A)转化为图论中求最小支撑树的问题(称为问题B)，并进行了推广。第叁章，提出了具有一个引出点的约束最优树问题，对何时连接一条线、两条线，叁条线进行了讨论，并给出了连接一条线和两条线的组合算法。对连接叁条线给出了一些必要条件，并且在假定连叁条线的基础上，给出了如何找近似解的方法。第四章，介绍了约束Steiner问题。第五章，提出了进一步研究的问题。主要结果如下：定理2.1问题A等价与问题B．构造完全图G(V，E)．V={P_0，P_1，P_2，P_3；¨，P_n}，边e_(ij)的权定义为，其中‘(几，只)一触到道线L的距离}‘(只，弓)一}点R到点已的距离}eij关联于P0否则定理3.1在L只引出一条线情形，约束最优树r*满足:l(T’)一l(T0) 1+—1】11n 21‘i‘nd盛定理3.2在L引出两条线情形，约束最优树满足:1矛J、.1争」、，尹、，夕矛已了.、z(T’)=咖n{l(T0)+心一1llaX 曰扬(eij){eij}定理3.3在L引出两条线情形，约束最优树满足:l仃’)=Inln日叁石(r0){l(T0)+l(e)一maXI e’E刃T0(e)(本文来源于《郑州大学》期刊2004-05-01）