1. 引言
斯坦纳树(Steiner tree)问题( [1] - [5] )是组合优化学科中的一个经典问题。组合优化包含许许多多的问题，它们都来源于生活，是许多实际问题的某种抽象。这类问题中的任何一个问题的解决都会给实际生产带来影响；另一方面，其中大部分是一些非常困难的数学问题。其中，经典斯坦纳树问题及其推广形式就是困难问题。一般来说，要得到一斯坦纳最小树，只能通过枚举法，即对个点的各种排列和每一排列的各种拓扑一一求出相应的斯坦纳树，然后进行比较。当然，数学家们也可以设计一些如分支定界法、动态规划法等方法去求解，但这些方法实际仍是枚举法。这意味着对一般的平面点集而言，不大可能存在求解这个问题的多项式时间算法。
在过去的二、三十年中，Steiner树问题及其各种推广与变形问题是研究的热点问题。关于斯坦纳树这个问题可以追溯到17世纪初，数学家Fermat提出的一个问题：在欧氏平面上有三个点，寻找第四个点使得由该点连接这三个点的距离之和最小。在此之后，经过多位数学家的扩展补充，最终以瑞士数学家Steiner的名字命名为Steiner问题。
由于斯坦纳树问题在现代生活中应用( [6] - [9] )十分广泛，比如：计算机网络布局、生物分析、电路设计、基于四边形Steiner最小树的无线传感器网络连通恢复、图的Steiner最小树问题的混合遗传算法、降阶回溯算法、量子蚁群算法、关键词查询方法等，从而成为组合优化和理论计算机科学中一个极其重要的研究问题。该研究问题主要包括欧几里德Steiner问题、直线Steiner问题、网络Steiner问题和进化Steiner问题，本文主要探讨欧几里德Steiner问题。
2. 预备知识
2.1. 基本概念
在欧几里德平面上，给定个端点的集合，寻找一棵连接了中所有端点的Steiner树，使得树的总长度达到最小。我们称这个问题为欧几里德平面上的Steiner树问题。属于上的顶点称为所与点或正则点，不属于上的顶点称为斯坦纳点。恰含个Steiner点称为阶Steiner树，时称为满Steiner树，记为。
令为个所与点所成集合，令为一将此个点连接起来的最小网络，若过上的每一斯坦纳点皆有三条边通过，它们两两交成的角，且任何两边不相交，又若过其中每一所有点只有一边通过，就说具有满拓扑。若上某些所与点又两条或三条边通过，则称是退化的。
在以线段为一边的等边三角形中，如果第三个顶点使构成顺时针方向，则称点是线段的特征点。在线段的端点处，以为一边做周角的三等分，不含的闭角形区域称为线段在端点的特征域。、两端特征域的并称为线段的特征域。
2.2. 欧几里德斯坦纳树的性质
(1) Steiner最小树上任何两条邻接边的夹角不小于。
(2) Steiner最小树上任何一个顶点的关联边不多于3条，且每个叶子都是原点。
(3) 设Steiner最小树的原点为个，则斯坦纳点的个数小于等于。
(4) Steiner最小树上与斯坦纳点相关联的边必定为3条，且这3条边中任意两边夹角为。
(5) [10] Steiner最小树上的斯坦纳点必在点集的凸包之中。
2.3. 欧几里德斯坦纳树的复杂性
对于平面上任意给定的四个点，求它们的Steiner最小树并不难，H. O. Pollak在1978年最早给出了解法。这问题历史上也算是道难题，在大数学家高斯的遗稿中，据说记载着他的儿子曾向他提出刚才所说的问题，高斯并未给出解答。
当给定点的数目大于等于4时，点集的斯坦纳树就不止一棵。没有退化点的斯坦纳树称为完整斯坦纳树，记作FST。对给定的点集，若将它的所有的FST和具有退化点的斯坦纳树加在一起，其数目可以大得惊人。例如当给定点的数目为6时，此数目为5625。当给定8个点时，则为2,643,795 [10] 。给定的点越多，这个数目增长得越快。
由于求Steiner最小树是一问题 [11] ，要从众多的斯坦纳树中求出长度最小者，计算量相当繁重。但有些投资数额巨大的工程，比如从西伯利亚修建一条天然气管道到上海，沿途向许多城市输送天然气，只要在设计上能节约百分之二三，也是一个很大的数字，另外一些问题，例如计算机的微型集成电路芯片，由于同一线路布局的芯片需要量很大，在设计上若能尽量缩短线路总长，也会极大节约成本。因此，如何寻找Steiner最小树变成了许多运筹学工作者所关心的问题。据国外文献所述，对给定点数目小于100的问题，目前已有办法处理。当然，对于许多实际问题来说，100这个数字远为不够。
3. 斯坦纳树构造
3.1. 三个点的斯坦纳树构造
1640年，费尔马提出如下问题：在平面上给出三个点A、B、C，求一点使距离和达到最小。关于这个问题出现了很多解法，比如力学模拟方法，几何证明方法等，其中，意大利数学家托里切利(E. Torricelli)指出：若在的三条边上分别向外作等边三角形，并对每一个三角形作一外接圆，那么这三个圆有一个交点，记为，即为所求的点。在1947年，意大利数学家卡瓦列里(F. B. Cavalieri)指出：在作图中，要求点的三个交角。这样看来，当且仅当三个点两两相连所成的夹角小于的时候才存在一个点在内部，不然，点将退化。现在我们来分类看看这两种情况：
(1) 当内的任一个角大于，设，此时连接A、B、C三点的最小网络就是。
(2) 当的三个内角、、都小于的时，设是内部的一点，且使得之和最小。只需：。此时连接A、B、C三点的最小网络就是。
综上所述，在遇到三个点的最小斯坦纳树问题时，我们找出使得。的斯坦纳点是不难的。具体我们可以以的任意一边向外作正三角形，再做正三角形的外接圆，此时外接圆与原三角形的交点即为所求。
3.2. 四个点的斯坦纳树构造
对于平面上四个点的最小斯坦纳树问题，只能存在0阶、1阶和2阶的斯坦纳树。下面定理 [12] 给出了四点集上Steiner树存在的充要条件以及对于具有两株满斯坦纳树如何找出唯一的Steiner最小树判断方法。
定理3.2.1：0阶Steiner树存在的充要条件是路中每条边都在其邻边的特征域中。
定理3.2.2：1阶Steiner树存在的充要条件是线段的特征点位于线段的端特征域中，并且的内角均小于。
定理3.2.3：满Steiner树存在的充要条件是：(1)是凸四边形；(2)；(3) 线段的特征点位于线段特征域外(外)。并且的内角均小于。
定理3.2.4 (H. O. Pollak定理 [8] )：设A、B、C、D为四个所与点，它们构成的四边形的两条对角线的夹角分别为和，再设这四个点的两株满(拓扑)斯坦纳树都存在。如果，那么两株斯坦纳树中最短的一株是位于两条对角线夹角为的那一区域的一株。
3.3. 五个点的斯坦纳树构造
3.3.1.的一般情况
当的情况比的情况复杂的多，之前讨论时，只有两株斯坦纳比树，而且还通过波拉克定理，根据有关四边形的对角线大小，给出了判定其中哪一株是最小的方法，这时问题解决的简单多了。但是，当时，目前并没有类似的方法。因为求Steiner最小树问题已证是难题，目前所用的方法是枚举法。
也就是说，设，先固定其中的一个点，如，其余四点可分成两对(这里至少有两种分法)，如分成和。在和上分别向外作正三角形得到顶点，如图1，这时会有以下三种情况：
(1) 在上，相对于的位置作正三角形，连接。在属于中求一点，使得。连接和，在和上分别求和，使得，。连接和，则
为所求的斯坦纳树，其长为。
(2) 连接，相对于的方向在上作正三角形，连接，按上述(1)中的方法求得斯坦
Figure 1. Isolated points B
图1. 隔离点B
纳树仍是。
(3) 连接，相对于的方向在上作正三角形，连接，按上述(1)中的方法求得斯坦纳树仍是。
按照这样的方法，每固定一个所与点，对余下说我四个点作成的四边形有两种组合，对于其中的一种组合，可以做三株斯坦纳树，但同种组合的三株斯坦纳树是都相同的，因此，只需作出一株即可。即固定一个所与点，可得到两株斯坦纳树。实际上，这两株斯坦纳树中只有一株是可能出现的，只需注意：必须要，必须将，两点和，两点分开。要过再做一条将，两点和，两点分开而又满足的条件的直线段是不可能的。所以，要作出的斯坦纳最小树，只需每次孤立其中的一个点，作出相应的斯坦纳树；再从五株斯坦纳树中选出最短的一株就可以了。
3.3.2.的特殊情况
下面我们来看一下时的特殊情况，也就是其中四个点已确定，设为是位于正方形的四个顶点，余下点在正方形边的垂直平分线上不确定的一点时，斯坦纳树是怎样的。此时，需要以的位置变化分三中情况考虑：
(1) 点在正方形内部对称轴的中点上，如图2。
此时，不用通过枚举法，因为点恰好在正方形对边中线的交点上，也就是对边向外作正三角形所得顶点的连线上，我们可以根据四点集的Steiner最小树的构造，即最小网络长度为。
那么，猜想一下，假如对称轴上的点不在上，此时，该五个点的斯坦纳树又会是怎样的?比如点在或中时。
(1.1) 隔离点，可构造以下两株斯坦纳树，如图3：
易证，所以最小斯坦纳树为。
(1.2) 隔离点 (同点)，如图4；隔离点 (同点)，如图5。
在作图中发现当点被隔离时，在线段上找不到一点使得，所以找不到最小斯坦纳树；当点被隔离时，在线段上也找不到一点使得，所以找不到最小斯坦纳树。
综上，只有隔离点时，存在最小斯坦纳树，即。
(2) 点在正方形内部对称轴(交点除外)上任意一点，如图6。
通过作图发现，当点在正方形内部对称轴(交点除外)上任意一点时，找不到合适的一点使得。
(2.1) 点在正方形外部对称轴上任意一点，当隔离点，如图7；当隔离点 (同点)，如图8；当隔离点 (同点)，如图9。
Figure 2. E in axis of symmetry
图2. E在对称轴中点
Figure 3. Isolated points E
图3. 隔离点E
Figure 4. Isolated points A
图4. 隔离点A
Figure 5. Isolated points D
图5. 隔离点D
Figure 6. E inside the square from any point on the axis of symmetry
图6. E在正方形内部的对称轴上任意一点
Figure 7. Isolated points E
图7. 隔离点E
Figure 8. Isolated points B
图8. 隔离点B
Figure 9. Isolated points A
图9. 隔离点A
通过枚举法，点在正方形外部对称轴上任意一点时，隔离点时才有最小斯坦纳树。
通过上述特殊情况，当时，其中四个所与点已确定，构造斯坦纳树已经不容易了，那么对于五个点都不确定的情况，构造斯坦纳树就非常困难了。对于五个点的斯坦纳树的构造也只能通过枚举法进行一一尝试，最后通过比较证明才能得出，这一过程是十分繁琐复杂的。就如本文中所举得特殊情况，也还是没有得到一般性的结论，所以这个问题仍有待研究。
参考文献