欧氏Steiner最小树的Delaunay剖分混合智能算法研究

VIP免费

3.0 侯斌 2025-01-09 7 4 3.21MB 60 页 15积分

侵权投诉

摘要

欧氏 Steiner 最小树问题是组合优化中一个经典的 NP 难题，在许多实际问题

中有着广泛的应用。通常情况下，欧氏 Steiner 最小树问题均指平面上的二维欧

氏Steiner 最小树问题。事实上，该问题可以进行高维推广，如，三维欧氏 Steiner

最小树问题即是对二维欧氏 Steiner 最小树问题在三维空间中的推广。由于这两

个问题的求解难度均相当高，目前尚无有效的精确算法，而利用普通的智能算法

进行求解时，其拓扑结构极易陷入局部最优，因此，寻找一个有效的启发式方法

显得尤为重要。

本文针对二维欧氏 Steiner 最小树问题，利用平面点集的 Delaunay 三角网剖

分原理，并结合智能算法，从几何的角度入手，设计了一种改进的混合型智能求

解方法，可大幅提高算法在寻找更好拓扑结构上的有效性。

针对三维欧氏 Steiner 最小树问题，本文将求解二维欧氏 Steiner 最小树问题

的算法进行推广，利用空间点集的 Delaunay 四面体网格剖分，并结合智能算法，

从几何的角度入手，设计了一种混合型智能求解方法，亦可大幅提高算法在寻找

更好拓扑结构上的有效性。

3-Sausage 结构是三维欧氏 Steiner 最小树中的一种特殊的拓扑结构，且该结

构已被证明具有最小 Steiner 比。由于其拓扑结构已知，因此，本文利用其几何

特点，设计了一种专门针对 3-Sausage 结构的混合型智能求解方法，并验证了其

有效性。

三种算法均在 Matlab 环境下编程实现，经一系列实例测试，并将本文算法

结果与普通智能算法结果进行对比，获得了满意的改进效果，为求解较大规模的

此类问题提供了新的有效解决途径。

关键词：二维欧氏 Steiner 最小树三维欧氏 Steiner 最小树 3-Sausage 结构

Delaunay 三角网 Delaunay 四面体网格智能算法

ABSTRACT

Euclidean Steiner minimum tree problem is a classical NP-hard problem in

combinatorial optimization, with a wide range of applications in many practical

problems. In the general cases, Euclidean Steiner minimum tree problem refers to the

problem in 2-dimensional space. Actually, this problem can be extended to higher

dimensions. For instance, Euclidean Steiner minimum tree problem in 3-dimensional

space is the extension problem from Euclidean Steiner minimum tree problem in

2-dimensional space. Due to the high difficulty of solving these two problems, there

are no effective accurate algorithms for them. On the other hand, it is easy to get stuck

into local optimal topology by using general intelligent algorithms for large scale of

these problems. Therefore, looking for an effective heuristic method is particularly

important.

In this paper, from the perspective of geometry, a combination of Delaunay

triangulation technique and intelligent algorithm is modified to design a hybrid

intelligent method for solving Euclidean Steiner minimum tree problem in

2-dimensional space. This method can apparently improve the effectiveness of

searching for better topology structures.

In a similar way, a hybrid intelligent method for solving Euclidean Steiner

minimum tree problem in 3-dimensional space can be extended from the above

method with the combination of Delaunay tetrahedron mesh generation and intelligent

algorithm. It can also apparently improve the effectiveness of searching for better

topology structures in 3-dimensional situation.

3-Sausage topology is a special structure of Euclidean Steiner minimum tree

problem in 3-dimensional space, which has been proved to have minimal Steiner ratio.

Because the topology structure of 3-Sausage is known, a specific hybrid intelligent

method is designed by using its geometric characteristics.

Promising results are obtained by using these hybrid algorithms coded in

MATLAB to solve series instances. Satisfactory improvements can be seen by

comparing the results from these hybrid algorithm and general intelligent algorithm.

Therefore, it provides a new effective way for solving large scale Euclidean Steiner

minimum tree problem in both 2-dimensional space and 3-dimensional space.

Key Words: Euclidean Steiner minimum tree problem in 2-dimensional space,

Euclidean Steiner minimum tree problem in 3-dimensional space,

3-Sausage topology, Delaunay triangulation,

Delaunay tetrahedron mesh generation, intelligent algorithm

中文摘要

ABSTRACT

第一章绪论......................................................... 1

1.1 选题背景..................................................... 1

1.2 国内外研究现状............................................... 3

1.3 本文主要内容和结构........................................... 3

第二章欧氏 Steiner 最小树问题 ........................................ 5

2.1 二维欧氏 Steiner 最小树问题 .................................... 5

2.1.1 问题概述................................................ 5

2.1.2 性质.................................................... 6

2.1.3 拓扑结构................................................ 6

2.1.4 Steiner 比 ................................................ 7

2.2 三维欧氏 Steiner 最小树问题 .................................... 8

2.2.1 问题概述................................................ 8

2.2.2 性质.................................................... 9

2.2.3 拓扑结构................................................ 9

2.2.4 Steiner 比 ............................................... 11

2.2.5 3-Sausage 结构 .......................................... 12

第三章 Delaunay 剖分 ............................................... 14

3.1 平面点集的 Delaunay 三角网剖分 ............................... 14

3.2 空间点集的 Delaunay 四面体网格剖分 ........................... 15

第四章智能算法.................................................... 16

4.1 智能算法的概念.............................................. 16

4.2 常见智能算法的介绍.......................................... 16

4.2.1 模拟退火算法........................................... 16

4.2.2 遗传算法............................................... 17

4.2.3 禁忌搜索算法........................................... 18

4.3 智能算法求解 Steiner 树时的缺陷 ............................... 20

第五章二维欧氏 Steiner 最小树的求解 ................................. 21

5.1 算法描述及示例.............................................. 21

5.2 算例测试.................................................... 24

5.3 结果分析.................................................... 31

第六章三维欧氏 Steiner 最小树的求解 ................................. 33

6.1 算法描述及示例.............................................. 33

6.2 算例测试.................................................... 36

6.3 结果分析.................................................... 42

第七章 3-Sausage 结构的求解 ......................................... 44

7.1 算法描述及示例.............................................. 44

7.2 算例测试.................................................... 46

7.3 结果分析.................................................... 50

第八章总结与展望.................................................. 52

8.1 全文总结.................................................... 52

8.2 进一步的工作................................................ 52

参考文献........................................................... 53

在读期间公开发表的论文和承担科研项目及取得成果..................... 56

致谢............................................................... 57

第一章绪论

1.1 选题背景

对Steiner 树的讨论由来已久，可以上溯到 17 世纪初[1]。1634 年，法国数学

家费马写了一本关于求某些曲线的切线的小册子，其中便提到了这样一个问题：

对平面上任意给定的三个点，如何求出一个点，使得该点到这三点的距离之和为

最小。这个问题可认为是本文所要介绍的 Steiner 树问题的滥觞。

费马所提的问题后来被瑞士的斯坦纳(J.Steiner,1796-1863)推广成：在平面上

任意给定 n个点 A1,…,An，如何求一点 P使得

|PA|

1i i





为最小，这里的|AiP|表示

从Ai到P的距离。斯坦纳本人虽然未曾做过任何具体贡献，但这一问题却引起

不少人的注意。由于在数学上无法解决，一些人还为之设计出某些简单机械来求

此点 P，如图 1-1。

图1-1 求解 Steiner 树的简单机械

1934 年，亚尔尼克(V.Jarnik)和克斯勒(M.Kossler)曾提出现在所说的斯坦纳树

问题：对于平面上给定的 n个点 A1,…,An，如何求出一个连接这 n个点的最小网

络。即所引进的不是一个 P点，而是由一些线段构成的连接这 n个点的一个最小

连通网络。1941 年，库朗(R.Courant)和罗宾斯(H.Robbins)在他们所著的《数学是

什么》(What is Mathematics)一书中又提出这一问题，并说：斯坦纳对费马问题

所做的只是一种浅薄的推广。要对该问题做出真正有意义的推广，所应考虑的不

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

欧氏Steiner最小树的Delaunay剖分混合智能算法研究.pdf

共60页,预览6页

还剩页未读，继续阅读

欧氏Steiner最小树的Delaunay剖分混合智能算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: