上海理工大学学报
第３０卷第５期Ｊ．ＵｎｉｖｅｒｓｉｔｙｏｆＳｈａｎｇｈａｉｆｏｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＶ０１．３０Ｎｏ．５２００８
文章编号：１００７—６７３５（２００８）０５—０４４３一０６
度约束欧氏Ｓｔｅｉｎｅｒ最小树问题及其求解
张瑾１，丁爱萍２，马良１
（１．上海理工大学管理学院，上海２０００９３；２．黄河水利职业技术学院信息３－程系，开封４７５００３）
摘要：在欧氏Ｓｔｅｉｎｅｒ最小树的基础上，对每个正则点加上了度约束限制，提出了度约束欧氏Ｓｔｅｉｎ—ｅｒ最小树问题，分析了该问题的特性，给出了该问题的模拟退火和蚂蚁算法求解过程，并使用Ｄｅｌ—
ｐｈｉ语言编程，在ＷｉｎｄｏｗｓＸＰ平台上运行通过．通过大量算例的计算结果验证了该问题的实用性及算法的有效性．
关键词：度约束；欧氏Ｓｔｅｉｎｅｒ最小树；算法
中图分类号：０２２文献标识码：Ａ
Ｓｏｌｖｉｎｇｔｈｅｄｅｇｒｅｅ－ｃｏｎｓｔｒａｉｎｅｄＥｕｃｌｉｄｅａｎＳｔｅｉｎｅｒ
ｍｉｎｉｍａｌｔｒｅｅｐｒｏｂｌｅｍ
ＺＨＡｈｌ６３ｉｎｌ，ＤＩＩＸｌＧＡｉ．ｐ骨，ＭＡＬｉａｎ９１
（１．ＦｕｓｓｉｎｅｓｓＳｃｈｏｏｌ，ＵｎｉｖｅｒｓｉｔｙｏｆＳｈａｎｇｈａｉｆｏｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏ幻ｇｙ，Ｓｈａｎｇｈａｉ２０００９３，Ｃｈｉｎａ；
２．ＤｅｐａｒｔｍｅｎｔｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＹｅｌｌｏｗＲｉｖｅｒＣｏｎｓｅｒｖａｎｃｙＴｅｃｈｎｉｃａｌＩｎｓｔｉｔｕｔｅ，Ｋａｉｆｅｎｇ４７５００３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｄｅｇｒｅｅ－ｃｏｎｓｔｒａｉｎｅｄＥｕｃｌｉｄｅａｎＳｔｅｉｎｅｒｍｉｎｉｍａｌｔｒｅｅｐｒｏｂｌｅｍｗａｓｄｉｓｃｕｓｓｅｄｂａｓｅｄｏｎｔｈｅＥｕｃｌｉｄｅａｎＳｔｅｉｎｅｒｍｉｎｉｍａｌｔｒｅｅｗｉｔｈｅａｃｈｏｒｉｇｉｎａｌｐｏｉｎｔｂｅｉｎｇａｄｄｅｄｗｉｔｈａｄｅｇｒｅｅｃｏｎｓｔｒａｉｎｔ．Ｔｈｅｐｒｏｐｅｒｔｙｏｆｔｈｅｐｒｏｂｌｅｍｗａｓａｎａｌｙｚｅｄａｎｄｔｈｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｐｒｏｃｅｓｓｏｆｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍｂｙｕｓｉｎｇｔｈｅｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍａｎｄｔｈｅａｎｔａｌｇｏｒｉｔｈｍｗａｓｐｒｅｓｅｎｔｅｄ．Ｂｏｔｈａｌｇｏｒｉｔｈｍｓａｒｅｃｏｄｅｄｉｎ
ＤｅｌｐｈｉａｎｄｒｕｎｏｉｌｔｈｅＷｉｎｄｏｗｓＸＰｅｎｖｉｒｎｍｅｎｔ．Ｓｅｒｉｅｓｏｆｎｕｍｅｒｉｃａｌｅｘａｍｐｌｅｓｗｅｒｅｔｅｓｔｅｄａｎｄｔｈｅｅｆｆｉ—ｃｉｅｎｃｙ
ｏｆｔｈｅｓｅａｌｇｏｒｉｔｈｍｓｗｅｒｅｖａｌｉｄａｔｅｄ．
Ｋｅｙｗｏｒｄｓ：ｄｅｇｒｅｅ－ｃｏｎｓｔｒａｉｎｅｄ；ＥｕｃｌｉｄｅａｎＳｔｅｉｎｅｒｍｉｎｉｍａｌｔｒｅｅ；ａｌｇｏｒｉｔｈｍ
最小生成树问题是运筹学、组合优化中的常见问题，即寻找一棵连接给定点并使树的总长度最短的生成树．理论上树中每个结点的度数可以不受限制，即在一个包含咒个结点的图的生成树中，每个结点的度数最大可以达到咒一１．而在实际应用中，结点间的连接往往会受到各种因素的影响，结点的度数不能随意取值．如在通信网络中，为防止结点故障引起的网络瘫痪而对网络结点的度数进行限制，或为了维持网络的传播速度及负载平衡而对结点的度数加以限制等．寻找总长最短且符合度约束限制
的一棵生成树是工程设计人员所追求的目标．而在组合优化中，７ｚ个结点的一棵Ｓｔｅｉｎｅｒ最小树要优于仅包含１＂／个结点的最小生成树，鉴于此，本文提出度约束欧氏Ｓｔｅｉｎｅｒ最小树问题，并寻找有效算法对其进行求解．
１数学模型
欧氏Ｓｔｅｉｎｅｒ最小树（ＥＳＭＴ）是指对给定欧氏平面上的原点集Ｐ（也称正则点集），找出连接Ｐ的最短网络．该问题可引入辅助点集Ｓ（称ｓ点集），使
收稿日期：２００７—０６—１３
基金项目：国家自然科学基金资助项目（７０４７１０６５，７０８７１０８１）；上海市重点学科建设资助项目（Ｔ０５０２）；河南省科技厅资助项目（０７２４００４４０３１０）
作者简介：张瑾（１９７４一），女，博士研究生．
上海理工大学学报２００８年第３０卷
得由正则点和ｓ点构成的网络树总长最小［１，２］．
Ｓｔｅｉｎｅｒ最优树的树长与相应的仅由原点构成的最
小生成树的树长之比称为Ｓｔｅｉｎｅｒ比，记为尺．已经
证明１３］，ｎ＞洳／２．如果对每个原点的度数加上一定
程度的限制则构成度约束欧氏Ｓｔｅｉｎｅｒ最小树
ＤｌｍＳＭＴ）问题．
欧氏Ｓｔｅｉｎｅｒ最小树具有如下重要性质（在此仅
列出与问题说明相关的部分）：
性质１设ＥＳＭＴ的原点为，ｚ个，则ｓ点数小
于等于咒一２．
性质２ＥＳＭＴ上和５点关联的边有３条，且
这３条边中任意２条边的夹角为１２０。．
性质３假设由咒个原点所围成的区域为凸
包，则所有ｓ点都包含在凸包内．
Ｄ（您ＳＭＴ问题可描述为：
已知图Ｇ＝（Ｖ，Ｅ），其中，Ｖ为顶点集，Ｅ为
边集．Ｖ＝ＰＵＳ，其中，集合Ｐ＝｛１，２，…，７ｚ一１，咒｝
为原点集合中元素的索引集，集合Ｓ＝｛咒＋１，咒＋
２，…，２竹一３，２”一２｝为ｓ点集合中元素的索引集．
定义（ｉ，歹）为图Ｇ中的一条边，ｉ，ＪＥＶ且ｉ＜歹，Ｅ１
＝｛（ｉ，歹）ＩｉＥＰ，ＪＥＳｆ，Ｅ２＝｛（ｉ，Ｊ）Ｉｉ∈Ｓ，歹∈
ｓ｝，Ｅ＝Ｅ１ＵＥ２，Ｖ中任意两点ｚｆ与ｚｉ间的距离
ｌ置一ｘｊｌ为这两个结点之间的欧氏距离．其数学模
型可表示为
ｍｉｎｚ＝∑ｋ一勺ＩＹ巧
（ｉ，Ｊ）∈Ｅ
ｓ．ｔ．ｘｉ∈Ｒ２ｉ＝７ｚ＋１，玎＋２，…，２７ｚ一３，２ｎ一２（１）
∑ｙ巧＝１，ｉＥＰ（２）
∑均＋∑均＋∑蛳＝３ｉＥＰｋ＜ｊ，＾∈Ｓ≈＞』，Ｅ∈Ｓ
１ＶｌｌＶｌ
∑∑＝ｌＶＩ一１
ｆ＝１Ｊ＝１歹∈Ｓ（３）
（４）
∑Ｙ玎≤ＩＴｌ一１，ＶＴｃＶ，Ｔ≠勿（５）ｉ，Ｊ∈Ｔ
∑Ｙ打≤ｂｉ，ｉＥＶ（６）Ｊ＝１
ＹｉｉＥ｛０，ｌ｝，（ｉ，Ｊ）∈Ｅ（７）式中，ｂｉ为每个结点必须满足的度约束限制；Ｙ打为变量．
约束条件（１）说明每个ｓ点都应存在于二维的欧氏空间中．约束条件（２）限制了每个原点仅与一个Ｊ点相连，约束条件（３）限制每个ｓ点的度为３，约束条件（４）和（５）保证所求得的为一棵生成树，约束条件（６）为原点必须满足的度约束限制，约束条件（７）
说明当边（ｉ，歹）是最优Ｓｔｅｉｎｅｒ树中的边时，ｙ巧＝１；否则，Ｙ０＝０．
２算法思想
求解度约束欧氏Ｓｔｅｉｎｅｒ最优树问题的难点主要有两个方面：首先是确定ｓ点的数目及位置，然后检查在添加ｓ点后各个原点是否满足其度约束，如果不满足则需重新确定ｓ点的数目和位置．因此，本文将从经典ＥＳＭＴ问题和度约束最小树问题的求解这两个角度来探讨ＤＣＥＳＭＴ问题，并针对这两个问题都属于非确定性多项式（ＮＰ）难题的特性［４￣８］，将启发式方法与智能优化算法相结合，寻找有效的求解算法．
由欧氏Ｓｔｅｉｎｅｒ最优树问题的性质３可知，任意５点都被局限于由原点构成的凸包内，则ｓ点的搜索范围即可确定．本文将其限制在由原点坐标围成的矩形区域Ｚ内．假设在Ｚ中已确定了ｍ个ｓ点及其位置，将咒个原点和优个ｓ点构成一个完全图Ｇ７，然后为Ｇ７寻找一棵满足度约束限制的最小生成树．
２．１度约束最小树问题解决方案
Ｐｒｉｍ算法和Ｋｒｕｓｋａｌ算法是两种传统的计算最小生成树的算法，其时间复杂度分别为０（咒２）和０（ｆＥｆｌ０９２Ｅｆ）．前者与边数无关，因而适用于稠密图；而后者与顶点数无关，适用于稀疏图．由于本文是将新加ｓ点与原点看成完全图来处理的，因此，将对Ｐｒｉｍ算法进行改造以使其适合于度约束最小生成树问题的求解．
假设Ｇ＝（Ｖ，Ｅ）是连通图，ｕ是顶点集合Ｖ的一个非空子集，求得的最小生成树为丁＝（Ｖ，Ｂ）．其中，Ｖ和Ｅ分别为图Ｇ的顶点集和边集，ｈ为最小生成树的边集．Ｐｒｉｍ算法的过程为：从Ｕ＝｛“ｏ｝，珏＝｛妒｝开始．在所有（“，ｕ）ＥＥ的边中（“∈Ｕ，ｕＥＶ—Ｕ）找一条权值最小的边（“７，口７），并分别将ｕ７和（“７，勘７）并人Ｕ和１１Ｅ．重复上述过程至Ｕ＝Ｖ为止．在此过程中，由于任意结点的度数都不受限制，边可以随意选取．因此，本文处理度约束最小树问题的策略是对边的选取这一操作过程加以限制，并在选取权值最小边的同时，考虑该边所邻接的两个顶点在度数增加１的情况下其总度数是否会超过该点的度约束限制，如果超过，则放弃该边，重新选择另一条次优边；不超过则保留该边，然后令该边所邻接顶点的度数值加１．重复上述过程至Ｉ丁ＥＩ＝咒一１或找不到度约束最小树为止．
第５期张瑾，等：度约束欧氏Ｓｔｅｉｎｅｒ最小树问题及其求解４４５
在上述寻找度约束最小树的过程中，如果起始点“。不同，将得到不同的计算结果，因此，可令起始点遍历整个顶点集合Ｖ，在计算所得的至多砚个结果中最小的一个就是所求的度约束最小生成树．本文将上述过程定义为函数ＭｙＰｒｉｍ，Ｍ夕阳ＩＴＩ完成为任意图寻找度约束最小生成树且返回树长的操作．
２．２ｓ点搜索空间的预处理操作
现确定ｓ点的数目及位置．假定首先已确定了；ｒｆｔ个ｓ点及其位置，然后可以在每个点的邻域内进行搜索，如果搜索到更优的Ｓ点，则用新点替换旧５点．由于５点的搜索范围局限于区间ｚ内，若能遍寻搜索空间ｚ内的任意位置来确定ｓ点，则能够得到最优解．然而，由于可行解集的庞大，该方案是不可行的．受高等数学积分计算思想的启发，可以对搜索空间Ｚ进行细分．具体处理方案为：
ａ．由原点集合Ｐ中元素的横纵坐标值确定一个矩形区域Ｚ；
ｂ．按照一定的精度要求将Ｚ等分为若干网格．如果网格细分倍数足够高的话，则原点和ｓ点都可以置于网格的顶点上，简称格点．以行序为主，按列值由小到大递增的顺序对格点进行编号．为每个格点设置一个标记变量，当格点处放置有原点或Ｓ点时，则将标记置为１；否则，置为０；
ｃ．用格点的行列值替代平面上相应点的坐标；平面上结点间的距离可以用绝对值距离代替；
ｄ．任一格点的邻域定义为在其周围８个方向上的８个格点（矩形边缘的点除外）．
当确定了最佳Ｓｔｅｉｎｅｒ点的个数即其位置后，将Ｓｔｅｉｎｅｒ点所在的格点编号存于整形数组ＢｅｓｔＳｏｌｕ．ｔｉｏｎ中．然后分别采用模拟退火和蚂蚁算法求解Ｅ§啊。
２．３模拟退火算法
模拟退火（ｓＡ）算法来源于固体退火原理，即将固体加温至充分高，再让其慢慢冷却．加温时，固体内部粒子随温度的升高变为无序状，内能增大，而慢慢冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小．
模拟退火最早由Ｋｉｒｋｐａｔｒｉｃｋ等用于组合优化，它是基于ＭｏｎｔｅＣａｒｌｏ迭代求解的一种通用随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性，通过设定一个初始温度初态，伴随温度的不断下降，结合概率突跳特性在解空间中通过邻域函数迸行随机搜索，最终得到全局最优．
区别于传统的邻域搜索算法，ＳＡ以概率ｒａｉｎ｛１，ｅｘｐ（一Ａ／ｔ）｝来接受新状态，其中，△为新旧状态的目标值差，ｔ为温度．算法保留了向优良解概率１的趋化过程，而赋予差的状态一定的可控接受概率，同时这种概率随温度的不断下降而趋于零．由于这种概率性的劣向转移，使得算法具有跳出局部极小而实现全局最优的能力．
模拟退火算法求解ＤＣＥＳＭＴ的伪代码为
Ｂｅｇｉｎ
Ｉｎｉｔｉａｌｉｚｅ（ｔｏ）；∥初始化退火温度；
Ｍｉｎ－－Ｔｒｅｅ－Ｌｅｎｇｔｈ＝ＭｙＰｒｉｍ（Ｇ（７ｚ））；．
∥调用ＭｙＰｒｉｍ，Ｇ为７２个原点构成的图；
Ｆｏｒｔ＝ｔｎｔＯ终止温度ｄＯ
Ｂｅｇｉｎ
Ｒｅｐｅａｔ
在当前ｍ个Ｓ点的情况下执行下述
操作；
∥Ｏ≤ｍ＜竹一２，即初始情况下为０
÷｜令ｓ氨
Ｃａｓｅ随机条件ｏｆ
条件１：加入ｒ个新Ｓ点；
ｍ＝优＋ｒ；∥ｒ为０到７／，一
２一ｍ之间的随机数
条件２：删除ｒ个已有ｓ点；
ｍ＝ｍ—ｒ；∥ｒ为小于ｍ
的随机数
条件３：逐一把每个ｓ点移至其邻
域内的任一允许位置；
ＥｎｄＣａｓｅ；
Ｎｅｗ—Ｔｒｅｅ—Ｌｅｎｇｔｈ＝ＭｙＰｒｉｍ（Ｇ７（”
＋ｍ））；
∥此处为Ｇ７由咒个原点和新增加的
∥ｍ个ｓ点构成的完全图
Ｄｉｆｆｅｒｅｎｃｅ２Ｍｉｎ－Ｔｒｅｅ—Ｌｅｎｇｔｈ—Ｎｅｗ－
Ｔｒｅｅ－Ｌｅｎｇｔｈ；
Ｉｆｍｉｎ｛１，ｅｘｐ（Ｄｉｆｆｅｒｅｎｃｅ／ｔ）｝＞ｒａｎ—
ｄｏｍ［Ｏ，１］
ｔｈｅｎ接收新解；
Ｕｎｔｉｌ当前温度下系统达到平衡；
ｔ＝ｔ＊０．９：
Ｅｎｄ
Ｆｎｄ
上海理工大学学报２００８年第３０卷
２．４蚂蚁算法
蚂蚁算法（Ａｎｔ算法）是近几年出现的一种仿生类算法，它模拟蚂蚁搜索食物过程中的行为特性，即蚂蚁在搜索食物时，能在其走过的路径上释放信息素（ｐｈｏｎｅ），使得一定范围内的其他蚂蚁能够察觉并影响其行为．路径上走过的蚂蚁越多则留下的信息素浓度越大，后来蚂蚁选择该路径的概率也就越高．同时，信息素会逐渐挥发，从而随着时间的推移，一些长期无蚂蚁通过的路径上的信息素将逐渐消失．最后将会形成一条寻找食物的最佳路线［９￣１１Ｊ．对每个格点ｉ，ｔ为第ｉ个格点的信息素，△ｔ为单位蚂蚁在第ｉ个格点上遗留下来的信息素增量，Ｑ为单位蚂蚁遗留的信息素数量（本文中取为１）．信息素的更新采用蚁密模型，即Ａｒｉ＝Ａｒｉ＋Ｑ．｜Ｄ为轨迹的持久度，且０≤｜０≤１（本文中取为０．７）．蚂蚁惫由点ｉ选择移动到点歹的转移概率
一攉
Ｐ（ｋ，ｉ，歹）＝磬
２５碍彷
ｆ
其中，％＝１／ｗ驴叫百为第ｉ个格点与第＿『个格点间的距离；ａ、口为非负数，此处取为１．
蚂蚁算法求解ＤＣＥＳＭＴ的伪代码为
ＦｏｒＮｒ＝０ｔｏ指定最大循环次数ｄｏ
Ｂｅｇｉｎ
对每个格点ｉ，初始化ｒｉ及Ａｒ；；
∥ｔ为较小的正常数（此处为１），即每个格
∥点上信息素强度的初始值，Ａｒｉ为０
Ｍｉｎ－Ｔｒｅｅ－Ｌｅｎｇｔｈ＝ＭｙＰｒｉｍ（Ｇ）；
Ｆｏｒ：ｉｒａ２１ｔｏ，ｚ一２ｓｔｅｐ１ｄｏ
Ｂｅｇｉｎ
Ｆｏｒｃｏｕｎｔ＝０ｔｏ指定循环次数ｄ０
Ｂｅｇｉｎ
随机生成ｋ个ｓ点；
∥ｋ只蚂蚁置于此ｋ个格点处，
∥１≤忌≤孢一２
对当前蚂蚁所在位置更新Ａｒ＝△ｒ＋Ｑ；
Ｎｅｗ—Ｔｒｅｅ—Ｌｅｎｇｔｈ＝ＭｙＰｒｉｍｆＧ７
（扎＋ｋ））；
Ｍｉｎ－Ｔｒｅｅ—Ｌｅｎｇｔｈ＝ｍｉｎｆＭｉｎ－Ｔｒｅｅ～
Ｌｅｎｇｔｈ，Ｎｅｗ－Ｔｒｅｅ－Ｌｅｎｇｔｈ）；
更新ＢｅｓｔＳｏｌｕｔｉｏｎ；
Ｆｏｒｉ＝０ｔｏｋ一１ｄｏ
Ｂｅｇｉｎ
产生随机数Ｒａｎｄｏｍ；
ＩｆＲａｎｄｏｍ＞Ｐ（ｋ，ｉ，Ｊ）ｔｈｅｎ
在当前蚂蚁的邻域内移动；
Ｅｌｓｅ
转移到另一蚂蚁Ｊ所在的邻
域内；
对当前蚂蚁所在位置更新Ａｒ
＝Ａｒ＋Ｑ；
Ｅｎｄ
Ｎｅｗ－Ｔｒｅｅ－Ｌｅｎｇｔｈ＝ＭｙＰｒｉｍ（）；
Ｍｉｎ－Ｔｒｅｅ－Ｌｅｎｇｔｈ＝ｍｉｎ（Ｍｉｎ－Ｔｒｅｅ
—Ｌｅｎｇｔｈ，Ｎｅｗ－Ｔｒｅｅ－Ｌｅｎｇｔｈ）；
更新ＢｅｓｔＳｏｌｕｔｉｏｎ；
Ｅｎｄ
Ｅｎｄ
对每个格点ｉ
Ｂｅｇｉｎ
ｒｉ
２
１０“＋Ａｒｉ；
Ａｒｉ＝０；
Ｅｎｄ
Ｅｎｄ
上述算法均用Ｄｅｌｐｈｉ１０．０编程实现，并在Ｗｉｎ—ｄｏｗｓＸＰ系统下运行通过．
３数值试验
本文采用的数据取自国际上公布的ＳｒＥＩＮＬＩＢ测试库．在不同原点个数及度约束取值的情况下进行了大量试验，部分数据如表１～６所示．
表１ｄｉ＝１时ＳＡ算法计算结果
Ｔａｂ．１ＲｅｓｕｌｔｓｏｆｔｈｅＳＡａｌｇｏｒｉｔｈｍｗｈｅｎｄｉ２１
第５期张瑾，等：度约束欧氏Ｓｔｅｉｎｅｒ最小树问题及其求解４４７
表２ｄｉ＝１时Ａｎｔ算法计算结果
Ｔａｂ．２ＲｅｓｕｌｔｓｏｆｔｈｅＡｎｔａｌｇｏｒｉｔｈｍｗｈｅｎｄｉ２１
表３ｄｉ＝２时ｓＡ算法计算结果
Ｔａｂ．３ＲｅｓｕｌｔｓｏｆｔｈｅＳＡａｌｇｏｒｉｔｈｍｗｈｅｎｄｉ２２
表４ｄｌ＝２时Ａｎｔ算法计算结果
Ｔａｂ．４ＲｅｓｕｌｔｓｏｆｔｈｅＡｎｔａｌｇｏｒｉｔｈｍｗｈｅｎｄｉ＝２
表５ｄｉ＝３时ｓＡ算法计算结果
Ｔａｂ．５ＲｅｓｕｌｔｓｏｆｔｈｅＳＡａｌｇｏｒｉｔｈｍｗｈｅｎｄｌ＝３
类型
原点数ｎ
５８
度约束最小树长
ＤＣＥＳＭＴ树长最优值ＤＣＥＳＭＴ树长最差值ＤＣＥＳＭＴ树长平均值１．７２８６２０
１．７０８２５０
１．７２８６２０
１．７１９５４８
０．７７００２０
０．７６９８５０
０．７７００２０
０．７６９９８６
２．１１６９８０
２．０４００８０
２．１１６９８０
２．０８４０４０
２．２３７８５０
２．２０４５３０
２．２３７８５０
２．２２８６４０
型塑生主壁尘堡煎丝！：鱼丝ｉ２１Ｑ：Ｚ鱼！Ｑ踅兰：Ｑ圣Ｑ垒２堡三：！坠兰Ｑ！
表６也＝３时Ａｎｔ算法计算结果
Ｔａｂ．６ＲｅｓｕｌｔｓｏｆｔｈｅＡｎｔａｌｇｏｒｉｔｈｍｗｈｅｎｄｉ２３
上海理工大学学报２００８年第３０卷
通过对数据进行分析可以发现，蚂蚁算法的性能优于模拟退火算法，在最好情况下，蚂蚁算法计算所得度约束Ｓｔｅｉｎｅｒ最优树的总长仅为ＳＡ算法所得结果的８０％，且对于某些数据，模拟退火算法无法找到比度约束最小树更好的度约束Ｓｔｅｉｎｅｒ最小树，而蚂蚁算法却可以找到．但在计算速度方面，蚂蚁算法则比模拟退火算法慢，尤其是在原点个数较多的情况下，其计算时间可为模拟退火算法的几十倍．这也恰恰符合无免费午餐定理中的观点．智能启发式方法可以保证算法以一定的概率收敛到最优解，但在某些情况下可能会出现无法找到最优解的情况．在度约束比较紧的情况下（如ｄｉ＝１），传统的度约束最小树往往是不存在的，而利用度约束Ｓｔｄｎｅｒ最优树思想，无论采用模拟退火还是蚂蚁算法，都可以找到满足原点的度约束限制的最小生成树．从而验证了度约束Ｓｔｄｎｅｒ最小树优于传统度约束最小树．在度约束大于等于３的情况下，ＤＣＥＳＭＴ问题则基本上等价于传统的ＥＳＭＴ问题．
４结束语
度约束最小树问题拥有广泛的应用背景，找到满足结点的度约束限制并使得树长最短是用户所追求的目标．本文提出的度约束欧氏Ｓｔｅｉｎｅｒ最优树思想不仅可以实现上述目标，而且可以使最后结果优于传统的度约束最小树．如何使算法速度较快且性能较优是后续研究的方向和重点．
参考文献：
［１］ＧＩＬＢＥＲＴＥＮ，ＰＯＬＬＡＫＨＯ．Ｓｔｅｉｎｅｒｒｎｉｍｍａｌｔｒｅ∞
［Ｊ］．ＳＩＡＭＪＡｐｐｌＭａｔｈ，１９６８，１６（１）：ｉ一２９．
ＭＡＣＵＬＡＮＮ，ＭＩＣＨＥＬＯＮＰ，ＸＡＶＩＥＲＡＥ．ＴｈｅｅＨ—
ｄｉｄｅａｎＳｔｄｎｅｒｐｒｏｂｌｅｍｉｎＲ”：Ａｍａｔｈｅｍａｔｉｃａｌｐｒｏｇｒａｍ—
ＩＩｌｉｎｇ
ｆｏｒｍｄａｔｉｏｎ［Ｊ］．ＡｎｎａｌｓｏｆＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２０００，９６（１１）：２０９—２２０．
ＤＵＤＺ．ＨＷＡＮＧＦＫ．Ｔｈｅｓｔｄｎｅｒｒａｔｉｏｃｏｎｊｅｃｔｕｒｅｏｆ
Ｇｉｌｂｅｒｔ－Ｐｏｌｌａｋｉｓｔｍｅ［Ｊ］．Ａｌｇｏｆｉｔｈｍｉｃａ，１９９２，７（１）：１２１
—１３５．
ＷＩＮＴＥＲＰ．ＡｎａｌｇｏｒｉｔｈｍｏｆｔｈｅＳｔｅｉｎｅｒ
ｐｒｏｂｌｅｍｉｎｔｈｅＥｕｃｌｉｄｅａｎｐｌａｎｅ［Ｊ］．Ｎｅｔｗｏｒｋｓ，１９８５，１５（２）：２３３—２４５．
ＧＡＪ乏ＥＹＭ．ＧＲＡＨＡＭＲＬ．ＪＯＨＮＳＯＮＤＳ．Ｔｈｅｃｏｍ—
ｐｌｅｎｔｙｏｆｃｏｍｐｕｔｉｎｇｓｔｏｎｅｒ
ｍｉｎｉｍｕｎ仃∞［Ｊ］．ＳＩＡＭＪｏｕｒｎａｌｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，１９７７，３２（４）：８３５—
８５９．
ＧＡＲＥＹＭ，ＪＯＨＮＳＯＮＤＳ。Ｔｈｅｒｅｃｔｉｌｉｎｅａｒｓｔｅｉｎｅｒ
ｐｒｏｂｌｅｍｉｓＮＰ—ｃｏｍｐｌｅｔｅ［Ｊ］．ＳＩＡＭＪｏｕｒｎａｌＯｎＡｐｐｌｉｅｄ
Ｍａｔｈｅｍａｔｉｃｓ，１９７７，３２（６）：８２６—８３４．
ＮＡＲＵＬＡＳＣ，ＨＯＣＡ．Ｄｅｇｒｅｅ－ｃｏｎｓｔｒａｉｎｅｄｍｉｎｉｍｕｍ
ｓｐａｎｎｉｎｇａｅｅ［Ｊ］．ＣｏｍｐｕｔｅｒｓａｎｄＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，
１９８０，７（４）：２３９—２４９．
马良，蒋馥．度约束最小生成树的快速算法［Ｊ］．运筹
与管理，１９９８，７（１）：ｌ一５．
ＤＯＲＩＧ０Ｍ，ＭＡＮＩＥＺＺ０Ｖ，ＣＯＬ（）ＲＮＩＡ．Ａｎｔｓｙｓ—
ｔｅｒｎ：ＯｐｔｉｍｉｚａｔｉｏｎｂｙａｃｏｌｏｎｙｏｆｃｏｏｐｅｒａｔｉｎｇＡｇｅｎｔｓ
［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＳｙｓｔｅｍｓ，Ｍａｎ，ａｎｄＣｙｂｅｒ—
ｎｅｆｉｃｓ，ＰａｒｔＢ，１９９６，２６（１）：２９—４１．
马良，蒋馥．度限制最小树的蚂蚁算法［Ｊ］．系统工程
学报，１９９９，１４（３）：２１１—２１４．
金慧敏，马良，王周缅．欧氏Ｓｔｄｎｅｒ最小树的智能优
化算法［Ｊ］．计算机工程，２００６，３２（１０）：２０１—２０３．］
］
］
］
］
］
］
］
］
］
２
３
４
５
６
７
８
９
ｍ
¨
ｒＬ
ｒＬ
ｒＬ
ｒＬ
ｒＬ
ｒＬ
ｒＬ
ｒＬ
ｒＬ
ｒＬ
度约束欧氏Steiner最小树问题及其求解
作者：张瑾， 丁爱萍， 马良， ZHANG Jin， DING Ai-ping， MA Liang
作者单位：张瑾,马良,ZHANG Jin,MA Liang(上海理工大学管理学院,上海,200093)， 丁爱萍,DING Ai-ping(黄河水利职业技术学院信息工程系,开封,475003)
刊名：
上海理工大学学报
英文刊名：JOURNAL OF UNIVERSITY OF SHANGHAI FOR SCIENCE AND TECHNOLOGY
年，卷(期)：2008，30(5)
被引用次数：1次
参考文献(11条)
1.GILBERT E N.POLLAK H O Steiner minimal trees 1968(01)
2.MACULAN N.MICHELON P.XAVIERAE The eu-clidean steiner problem in R":A mathematical program-ming formulation 2000(11)
3.DUDZ.HWANG F K The steiner ratio conjecture of Gilbert-Pollakistrue 1992(01)
4.WINTER P An algorithm of the Steiner problem in the Euclidean plane 1985(02)
5.GAREY M.GRAHAM R L.JOHNSON D S The com-plexity of computing steiner minimun tree 1977(04)
6.GAREY M.JOHNSON D S The rectilinear steiner problem is NP-complete 1977(06)
7.NARULA S C.HO C A Degree-constrained minimum spanning tree 1980(04)
8.马良.蒋馥度约束最小生成树的快速算法 1998(01)
9.DORIGO M.MANIEZZO V.COLORNI A Ant sys-tem:Optimization by a colony of cooperating Agents 1996(01)
10.马良.蒋馥度限制最小树的蚂蚁算法[期刊论文]-系统工程学报 1999(03)
11.金慧敏.马良.王周缅欧氏Steiner最小树的智能优化算法[期刊论文]-计算机工程 2006(10)
引证文献(1条)
1.丁雪枫.马良.丁雪松基于模拟植物生长算法的构造通讯网络Steiner最优树方法[期刊论文]-上海理工大学学报2010(1)
本文链接：https://www.doczj.com/doc/401140913.html,/Periodical_shlgdxxb200805008.aspx
授权使用：复旦大学图书馆(fddxtsg)，授权号：7a1c0428-3f74-4d68-a581-9de5017bfa27
下载时间：2010年9月2日