《2022年约束Steiner最小树问题文件 .pdf》由会员分享，可在线阅读，更多相关《2022年约束Steiner最小树问题文件 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浙江大学学报990410浙江大学学报SCIENCES EDITION1999年 第26卷 第4期 vol.26No.4 1999约束 Steiner最小树问题陈光亭何勇姚恩瑜摘要：本文首先提出一个约束Steiner最小树问题。设欧氏平面上直线L的一侧有n个点，记点集为N，现要在L上找一点P，使关于N P 的 Steiner树长度最小。文章解决了n=2及n=3的情形。 关键词：约束Steiner最小树； 约束 Steiner标准化 中图分类号：O157.5 文献标识码：AConstrained Steiner Minimum Tree ProblemCHEN Guang-ting1,HE Yon
2、g2,YAO En-yu2(1.The School of Science and Arts ,Hangzhou Institute of Electronic Engineering,Hangzhou 310037,China; 2.Department of Mathematics， Zhejiang University, Hangzhou 310027， China)Abstract:The constrained Steiner minimum tree problem(CSMTP)is presented. Let L be a straight line in a Euclide
3、an plane,and N=A1,A2, ,An be a set of n points in the same side of L.The problem is to find a point P in L such that the length of Steiner minimum tree about NP is minimal.In this paper, the cases of n=2 and 3 are solved. Key words:constrained Steiner minimum tree; constrained Steinerization1引言在实际应用
4、中，我们常会碰到一类与Steiner最小树问题有密切联系但又有所不同的问题。其数学模型可以归结为如下形式的最短网络问题：设欧氏平面上有一直线L，在 L同侧有 n个点A1,A2, ,An，记点集为N。现要在L上取一点P，使连通P与 N这 n+1个点的网络在欧氏距离下长度最短。这样的问题我们把它称为约束Steiner最小树问题，简记为CSMTP ，相应的连接n+1个点的 Steiner最小树称为N关于 L的约束 Steiner最小树。显然，CSMTP 是一般的Steiner最小树问题的推广，易见其为NP-C问题。 本文首先给出了n=2时的结果，在此基础上引进了一个约束Steiner标准化过程，然后
5、对 n为 3的情形给出了CSMTP 的解。2记号和引理设 N是平面上点集，|N|=n ， L为平面上一直线，且N位于 L同一侧。记N关于 L的约束Steiner最小树为CS*(N) ，同时也用它表示该树的边的集合。S*(N) 则表示点集N的 Steiner最小树，并也用它表示该树的边集。下文中，有时也用记号CS*(ABC) 表示 A， B， C三点关于 L的约束 Steiner最小树，而S*(ABC) 则表示 A,B,C 三点的 Steiner最小树，当N=A,B 时，类file:/E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm（第 1 9 页） 2010-3-
6、23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 浙江大学学报990410似的也有CS*(AB) 等记号。树中关联A， B两顶点的边记为AB，而其长度即为欧氏距离d(A,B) ，树 T的总长则记为l(T)。 下述引理概括了Steiner树的一些主要性质。 引理2.1 (a) 对S*(N) 中的每一个Steiner点，恰好有3条边与之相关联，且三条边中任何两条边的夹角为120。 (b) 设 A是S*(N) 的
7、正则点，则与A关联的两条边在A处的夹角至少为120。 (c) S*(N) 中至多有n-2 个 Steiner点，这里n=|N| 。 引理2.2 设 ABC 三内角均小于120，以 AB为一边向外作一正三角形ABC ，则A,B,C 三点所确定的Steiner点 S在 CC 上，S*(ABC)=SA SB SC，且 l(S*(ABC)=d(C,C ) 。当 ABC 中有一内角大于或等于120时，该角两边即构成S*(ABC) 。 引理 2.3 设 A，B， C， D为平面上给定四点且由该四点构成一个凸四边形。向四边形外侧作正三角形ABE， CDF ， AFG ，如图 1，若 EF与 BG 交点在四边
8、形内部，则EF=BG 为关于 A， B， C， D四点的一条Steiner树长。该Steiner树的 Steiner点在 EF上，其中之一即为 EF与 BG 的交点。图1结合引理2.2 及引理 2.3 ，图 1中的 Steiner点S实际上即为A， B， F三点的 Steiner点。若 EF另外还有一个Steiner点，则应为E， C， D三点的 Steiner点。 以上引理见文献4,5。对于点集N关于直线L的约束 Steiner树，则有如下引理。 引理2.4 CS*(N) 中与 P关联的边至多为两条。若仅有一条边与P关联，则该边必与L垂直。若与P关联的边有两条，分别为AP与 PB，则 AP与
9、 PB在同一直线上，这里B为 B关于 L的对称点，且APB 120。3 n=2的情形设 N=A,B,A,B为直线 L同侧的两点，且A点离直线L较近，如图2所示。又设我们要找的 L上的点为P， A为 A关于直线L的对称点，BA与直线L的夹角为，AA与 L的交点为 O， OAB= 。下面我们分情形讨论P点的选取与约束Steiner最小树 CS*(N) 的确定。 情形1 120。此时按的大小又分为两种子情形。file:/E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm（第 2 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - -
10、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 浙江大学学报990410图2情形1.1 30。根据引理2.4 ，此时与P关联的边只能有一条，且该边与L垂直。又由引理2.2 ，可得 CS*(N) 的作法如下：以AB为边向上作正三角形ABE，过 E作 L的垂线， L上垂足即为所求点P。关于 A， B， P三点的 Steiner树有一个Steiner点 S， S即为 EP与ABE的外接圆的交点，而该Steiner树长即为d(E,P)，如图 3所示。图3情形1.2 30。此时问题退
11、化为找直线上一点Q，使 d(A,Q)+d(Q,B)最小。则很明显 Q点即为 A B与 L的交点，而最优Steiner树即为 AQ 连接 QB 所构成。 情形2 120。该情形可看成情形1.1 的退化，即S退化到 A。其最优网络由QA 连接AB而成， O点即为直线上所求点。4 n=3的情形设 N=A,B,C， A，B， C为直线 L同侧的三个点。我们不妨以L为 x轴建立直角坐标file:/E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm（第 3 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
12、 - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 浙江大学学报990410系，使 A， B， C三点均在第象限。设三点坐标分别为(x1,y1),(x2,y2),(x3,y3) ，不妨设y3=miny1,y2,y3 0，我们分以下两类情形来讨论n=3时 CS*(N) 的求解。 (1) x3=maxx1,x2,x3; (2) maxx1,x2,x3 x3 minx1,x2,x3 。 4.1 x3=maxx1,x2,x3 第一种情形与x3=minx1,x2,x3 是对称的，不必另外讨论x3=minx1,x2,
13、x3 的情形。 此时，不妨设x1=minx1,x2,x3 ，即 A点在最左侧，C点在最右侧，且C点离 L最近。设P为L上所求点，显然其横坐标落在x 1,x3 中。 S*(N) 为A， B， C三点所确定的Steiner最小树，分别从A， C引 L的垂线 AD及 CE，记S*(N) AD构成的树为Sl(N),S*(N) CE构成的树为Sr(N) 。现在，对Sl(N) 与Sr(N) 引进一个约束 Steiner标准化过程。 首先，对Sr(N) ，设Sr(N) 中与 C关联的两条边的夹角为。 (1) 若 120，则Sr(N) 已符合标准化要求，如图4所示。file:/E|/qk/zjdxxb/zjd
14、x99/zjdx9904/990410.htm（第 4 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 浙江大学学报990410图4 (2) 若 120，则设C为 C关于 L的对称点，则S*(ABC ) 与 L有唯一交点G，设S*(ABC ) 与L在 G点处形成锐角为。 (2.1)当 30，在角所张区域内取一点S，使它满足如下要求：过S引 L的垂线SF，则关于A， B， C， F四
15、点的 Steiner最小树以S为一个 Steiner点，而且S与 F， C关联。该Steiner最小树即为Sr(N) 标准化后的结果。如图5所示。图5 (2.2)当 30， GC 连接S*(ABG) 构成的树即为对Sr(N) 实现标准化后的结果。如图6所示。 把Sr(N) 实现约束Steiner标准化后所得的树记为S*r(N) 。下面对约束Steiner标准化过程作一些说明。file:/E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm（第 5 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
16、 - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 浙江大学学报990410图6 1.S*(ABC ) 与 L的交点是唯一的。这是由C点坐标的特殊性确定的。 2. 在标准化过程(2.1)中，当30时， S必可取到，且S是唯一的。首先，当B在 A，C连线上方，设T=CS*(BC) AB，若 T满足引理2.1 中关于 Steiner树的要求，即T在 B点处所成角度不小于120，则 T就是S*r(N), 而且 CS*(BC) 中的 Steiner点即是所要求的S。若 T在 B点处所成角度小于120，则设ABH
17、是以 AB为边且在AB上侧的正三角形，则S即为 CS*(HC) 中的 Steiner点，如图7与 8所示。其次，若B在 A， C连线下方，则S为 CS*(BC) 中的Steiner点，且S*r(N)=CS*(BC) AB。 图7图8file:/E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm（第 6 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 浙江
18、大学学报990410 3. 对Sl(N), 可以用与Sr(N) 对称的方法实现约束Steiner标准化，标准化后的结果记为S*l(N) 。但必须说明的是，当B在 AC下方或 AC与 CE的夹角大于等于120时，不能实施标准化过程，此时可认为S*l(N) 不存在。 4. 约束 Steiner标准化的结果是唯一确定的。这是因为在标准化过程中，由(1) 及 (2.2)所确定的结果都是唯一的，而由(2.1)所确定的结果则根据说明2也是唯一的。 现在我们可以给出如下定理。 定理4.1 在情形1的条件下，S*r(N) 与S*l(N) 中长度较短的一条即为CS*(N) ，且当S*l(N) 不存在时，Sr(N
19、) 即为 CS*(N) ，这里 N=A,B,C。 证明设CS*(N) 在 L上的点为P，由引理2.4 ， CS*(N) 中与 P关联的边至多有两条。 当与P关联的边只有一条时，该边必与L垂直，且与P邻接的点要么是C，要么是一个Steiner点，否则CS*(N) 不可能最短。若P与 C邻接，则CS*(N) 实际上就是S*r(N) 。若 P与一个 Steiner点邻接，则根据A， B， C三点的位置可说明该Steiner点或者与A邻接或者与C邻接，但不可能既与A邻接又与C邻接。根据约束Steiner标准化过程，若与A邻接，则CS*(N)即为S*l(N) ，若与 C邻接，则CS*(N) 为S*r(N
20、) 。 当 CS*(N) 中与 P关联的边有两条时，同样P或者与 A邻接或者与C邻接，且两者仅居其一。为了使CS*(N) 达到最短，当P与 A邻接时，CS*(N) 中除去 PA后余下部分必然是关于P，B， C三点的 Steiner最小树，如此CS*(N) 即为S*l(N) 。同样当P与 C邻接时，CS*(N) 即为S*r(N) 。证毕。 特别地，对情形1有如下推论。 推论4.2 若图 4(a) 中的120，则S*r(N) 即为 CS*(N) 。 证明因为S*l(N) 的长度不小于S*r(N) 的长度，而S*l(N) 即为S*l(N) ，S*r(N) 的长度则小于S*r(N) 的长度，因此S*r
21、(N) 的长度比S*l(N) 要小，即CS*(N) 应为S*r(N) 。证毕。 4.2 maxx1,x2,x3 x3 minx1,x2,x3 不妨设x1=minx1,x2,x3,x2=maxx1,x2,x3 。即 A， B， C三点均在L上方且 A在左侧，B在右侧， C点居中且C点离 L最近。过C点作 CD L， D为垂足。 现按如下方式引进S*1(N) 。 (1) 当 ACD 120时，S*1(N) 不存在。 (2) 当 ACD 120时，设A为 A关于 L的对称点，且CA与 L夹角为。 (2.1)当 30，S*1(N)=CS*(AC) CB，如图 9所示。file:/E|/qk/zjdxx
22、b/zjdx99/zjdx9904/990410.htm（第 7 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 浙江大学学报990410图9 (2.2)当 30，考虑Steiner树S*(A BC)，该树与L有唯一交点G，则S*1(N)=S*(BCG) AG ，如图 10所示。图 10把 A与B的地位对换，对称地我们可定义S*2(N) 。 把S*(N) 连接 CD 所得的树记为S
23、*3(N) 。当S*3(N) 在C点处任两条边所夹角度不小于120时，把S*3(N) 定义为S*3(N) ，否则认为S*3(N) 不存在。 这里对S*i(N) 的定义作如下说明。 1. 定义S*1(N) 的步骤 (2.2)中，与 L的交点是唯一的。 2.S*i(N) 均为满足引理2.1 要求的 Steiner树。 3.S*1(N) ，S*2(N) 及S*3(N) 最多存在两个。因为当ACD 120时，S*1(N) 不存在；当 BCD 120时S*2(N) 不存在；当ACB 120时，S*3(N) 不存在。 至此，有如下结论。 file:/E|/qk/zjdxxb/zjdx99/zjdx9904
24、/990410.htm（第 8 9 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 浙江大学学报990410定理4.3 在情形2条件下，S*i(N) 中长度较短者即为CS*(N) 。 证明设CS*(N) 在 L上的点为P，则当与P关联的边只有一条时，该边必与L垂直。再由 C点位置的特殊性，可以说明CS*(N) 中至多有一个Steiner点。 其次，当CS*(N) 中含一个Steiner
25、点时，若P=D，则 CS*(N) 必为S*3(N) 。否则 P与该Steiner点邻接，而由引理2.1 则可说明该Steiner点不能同时与A， B邻接，即只能与A， C或者 B， C邻接，即CS*(N) 为S*1(N) 或S*2(N) 。 再者，当CS*(N) 不含 Steiner点时，若P=D,则必有 AC， BC， CD 两两夹角均为120，此时 CS*(N) 即S*3(N) 。而当 P与 D不同时，P要么与 A， C同时邻接，要么与B， C同时邻接，而不可能与A， B同时邻接，否则不符合引理2.1 的要求。由此，CS*(N) 要么为S*1(N)要么为S*2(N) ，证毕。5结束语对于C
26、SMTP ，以下问题值得进一步研究。 1. 对于一般的CSMTP ，研究 n个点的一些特殊分布以使问题为多项式可解。 2. 当约束中直线L换以圆或其他曲线时问题如何处理? 3. 鉴于问题的难解性，讨论其有效近似解将会很有意义。作者简介：陈光亭(1965-)，男，副教授，主要从事组合优化、Steiner树问题及图论等方面研究。 作者单位：陈光亭杭州电子工学院文理分院，浙江 杭州 310037 何勇姚恩瑜浙江大学玉泉校区数学系，浙江 杭州 310027参考文献 1 Du D Z,Hwang F K.Computing in Euclidean Geomerty. J of Combin Theor
27、y Ser A.1982,32(3):396 400. 3Courant R,Robbins H.What is Mathematics?. Annals of Discrete Mathematics,Amsterdan,North-Holland,1992,53:3 10. 5 Melzak Z A.On the Problem of Steiner Tree. 数学的实践与认识，1986 ， 3： 17 21。 7陈国先。带( 直线 ) 约束的两点间最短连线收稿日期：1997-03-26file:/E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm（第 9 9
28、 页） 2010-3-23 21:52:21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 约束Steiner 最小树问题作者：陈光亭， 何勇， 姚恩瑜作者单位：刊名：浙江大学学报（理学版）英文刊名：JOURNAL OF ZHEJIANG UNIVERSITY年，卷(期)：1999 ，26(4)被引用次数：1次引证文献(1条)1. 陈光亭 . 丁巍. 张固 带禁区约束的直线上选址问题期刊论文-杭州电子工业学院学报 2004(4)本文链接： http:/ (fddxtsg) ，授权号：1869a77e-a7ef-4858-a2af-9de5017bd3c3下载时间：2010 年9月2日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -