Geometry-Experiment Algorithm for Steiner Minimal Tree Problem
Geometry-Experiment Algorithm for Steiner Minimal Tree Problem
复制标题
Steiner最小树问题的几何实验算法
DOI：
10.1155/2013/367107
复制
发表时间：
2013-04
影响因子：
--
通讯作者：
Gao, Yan-Ping
中科院分区：
文献类型：
--
作者：
Yang, Zong-Xiao;Jia, Xiao-Yao;Hao, Jie-Yu;Gao, Yan-Ping
Steiner最小树问题是经典的非线性组合优化问题之一。一种可视化实验方法成功地自动生成了斯坦纳点，并物理直观地显示了系统的最短路径，即斯坦纳最小树。然而，当给定点数目增加且分布不规则时，难以形成稳定的系统最短路径。利用Delaunay图的性质和Geo-Steiner算法的基本原理，结合可视化实验方法（VEA），构造几何算法和几何实验算法（GEA）来求解系统最短路径。通过两个算例的GEA和VEA得到了近似的优化结果。通过解决工程、实验和对比分析等实际问题，验证了GEA的有效性。通过多次实际计算，GEA可以成功地求出全局最短路径。
It is well known that the Steiner minimal tree problem is one of the classical nonlinear combinatorial optimization problems. A visualization experiment approach succeeds in generating Steiner points automatically and showing the system shortest path, named Steiner minimum tree, physically and intuitively. However, it is difficult to form stabilized system shortest path when the number of given points is increased and irregularly distributed. Two algorithms, geometry algorithm and geometry-experiment algorithm (GEA), are constructed to solve system shortest path using the property of Delaunay diagram and basic philosophy of Geo-Steiner algorithm and matching up with the visualization experiment approach (VEA) when the given points increase. The approximate optimizing results are received by GEA and VEA for two examples. The validity of GEA was proved by solving practical problems in engineering, experiment, and comparative analysis. And the global shortest path can be obtained by GEA successfully with several actual calculations.
登录
查看更多内容
DOI：
10.1007/springerreference_6200
发表时间：
2012-04
期刊：
--
影响因子：
--
作者：
F. Hwang;D. Richards;P. Winter
通讯作者：
F. Hwang;D. Richards;P. Winter
影响因子：
--
作者：
Hao Jie-yu
通讯作者：
Hao Jie-yu
DOI：
10.1109/tpds.2004.1271184
发表时间：
2004-04
影响因子：
5.3
作者：
Xiangyang Li;I. Stojmenovic;Yang Wang
通讯作者：
Xiangyang Li;I. Stojmenovic;Yang Wang
DOI：
10.1109/tcad.2008.2006085
发表时间：
2008-11
影响因子：
2.9
作者：
Sertac Cinel;C. F. Bazlamaçci
通讯作者：
Sertac Cinel;C. F. Bazlamaçci
DOI：
10.1007/978-1-4757-3171-2_6
发表时间：
2000
期刊：
Materials Science Forum
影响因子：
--
作者：
David M. Warme;P. Winter;Martin Zachariasen
通讯作者：
David M. Warme;P. Winter;Martin Zachariasen