斯坦纳树问题是组合优化学科中的一个问题。
组合优化学科包含许许多多的问题，它们都来源于生活，是许多实际问题的某种抽象。这类问题中任何一个问题的解决都会给实际生产带来影响;另一方面，其中大部分是一些非常困难的数学问题，对于这些问题的解决，那些传统的抽象性强的数学似乎无能为力，而要求广泛的数学基础和大量的数学训练。
问 题 的 提 出
平原上的三个城镇间要兴建一个公用的煤气供应站，在选址问题上，要考虑的主要问题是使由供应站到三个城镇的输送管道的总长最短。如何去寻找合适地点？
假若要建的是一个垃圾处理站，要修建三条公路将垃圾站与三个城镇连起来。这时，因为三个城镇的居民的数目或工业性质等的不同，每天运送垃圾使用的车辆数目各不相同，运输的费用也就各异。因此，选取地点时，如果仍考虑使三条公路的总长最小，就不合理了。这时应该考虑：先计算出三个城镇单位时间内生产的垃圾数量的百分比（或每日运输费用的百分比），如何选取地点，使得每个城镇垃圾运输数量与公路里程的乘积之和为最小。
1638年，法国数学家费马在他所写的一本关于求极值的书中就有了第一个问题，称为费马问题；第二个问题则到了18世纪中叶才由辛普森（A.R.Simpson）提出来。
在17世纪初，解析几何刚开始出现，求极值问题刚露萌芽，费马问题在当时竟成了难题，据说一时无人能解。梅森（M.Mersenne，1588—1648）将它带到意大利，后被托里彻利（M.Torricelli，1608—1647）所解决。稍后，卡瓦列里（B.F.Cavalieri，1598—1647）指出：若O为所求之点，则过O的三条线段OA，OB和OC两两交成120°的角。由于都是利用圆规和直尺作图，他们所考虑的都是三角形的三只内角皆小于等于120°的情况，否则无法作图。
直到1834年，海嫩（Heinen）才考虑其中有一只角（设为∠B）大于等于120°的情况。他证明：此时连接三角形三个顶点A，B，C的最小网络就是连接三点的折线AB+BC。此种情况称为退化情况，因为O点已经退化到B。问题的证明现在看来已很容易[1]。
费马问题很容易就被推广到若干个点的情况。瑞士数学家斯坦纳（J.Steiner，1796—1863）将问题推广成：在平面上求一点，使得这一点到平面上给定的若干个点（称为所与点）的距离之和最小。这可以看作斯坦纳树问题的雏形。斯坦纳在这个问题上未曾作过什么贡献。
其后，德国的两位数学家韦伯(H.Weber，1842—1913)和维斯菲尔德（E.Wieszfeld）分别在1909年和1937年将该问题作为工厂选址问题提出来：某地有给定的若干个仓库，每个仓库的其他相关因素可以换算成一个权重表示，求一建造工厂的合适地点，使工厂到每个仓库的距离与权重乘积的总和最小，则这个工厂的地址是最经济、便利的。维斯菲尔德并给出了一个算法用以求出工厂地址的近似值。我国在1950年代末期也曾提出类似的选址问题。
在1970年，美国数学家库恩（H.W.Kuhn）指出了维斯菲尔德的算法不是一个收敛算法，并给出了收敛的算法。我国的王长钰在1978年也给出了收敛的算法。
斯坦纳树问题的推广
斯坦纳树问题得到进一步发展是由于库朗（R.Courant）和罗宾斯（H.Robbins）在1941年的一本科普性读物《什么是数学》中提到了费马问题。书中说，斯坦纳对此问题的推广是一种平庸的推广。要得到一个有意义的推广，需要考虑的不是引进一个点，而应是引进若干个点，使引进的点与原来给定的点连成的网络最小。他们将此新问题称为斯坦纳树问题，并给出了这一新网络的一些基本性质。
设X为平面上给定n个点的点集。连接任意给定两点的线段叫做一条边，此两点为此边的端点。设G是由某些边做成的图形。边的端点叫做G的顶点。若对G的任意两个顶点皆可通过G的某些边把它们连起来，则称G为可连通的。此时若G上任何两顶点只有一条路可连通，则G称为一棵树。更进一步，若G的顶点集包含X中所有点，则称G为X的生成树，记作MST。
假设原来已经给定了n个点，库朗等指出需要引进的点数至多为n-2，此种点称为斯坦纳点。过每一斯坦纳点，至多有三条边通过。若为三条边，则它们两两交成120°角；若为两条边，则此斯坦纳点必为某一已给定的点，且此两条边交成的角必大于或等于120°。其中最小的网络称为已给定点的集合的最小斯坦纳树，记作SMT。若此SMT的斯坦纳点中有等于给定点的点，则称此SMT为退化的，此给定点称为退化点。
库朗等人的推广大大扩充了这一问题的应用范围，也增加了问题的难度。试想：假若平面上给定了100个点，要在平面增加若干个（至多为98个）点并把它们连成一个网络，同时要使得这一网络的长度是所有连接这100个点的网络中最短的。如何去找这些点，如何把这些点连起来？
对于平面上任意给定的四个点，求它们的SMT并不难，波拉克（H.O.Pollak）在1978年最早给出了解法。这问题历史上也算是道难题，在大数学家高斯的遗稿中，据说记载着他的儿子曾向他提出刚才所说的问题，高斯并未给出解答。
当给定点的数目大于等于4时，点集的斯坦纳树就不止一棵。没有退化点的斯坦纳树称为完整斯坦纳树，记作FST。对给定的点集，若将它的所有的FST和具有退化点的斯坦纳树加在一起，其数目可以大得惊人。例如当给定点的数目为6时，此数目为5625，当给定8个点时，则为2643795。给定的点越多，这个数目增长得越快。
要从众多的斯坦纳树中求出长度最小者，计算量相当繁重。但有些投资数额巨大的工程，比如从西伯利亚修建一条天然气管道到上海，沿途向许多城市输送天然气，只要在设计上能节约百分之二三，也是一个很大的数字。另外一些问题，例如计算机的微型集成电路芯片，由于同一线路布局的芯片需要量很大，在设计上（此时所用的距离不同于普通的欧氏距离，后文将要提到）若能尽量缩短线路总长，也会极大节约成本。因此，如何寻找SMT变成了许多运筹学工作者所关心的问题。据国外文献所述，对给定点数目小于100的问题，目前已有办法处理。当然，对于许多实际问题来说，100这个数字远为不够。
早在1977年，加利（M.R.Garey）等人即已指出，上述问题属于NP困难问题，因此看来不可能出现有效算法，即所谓的多项式算法来处理这一问题。目前文献中所提出的算法只不过是遍数法的种种改进，即在具体计算过程中，根据给定的实际问题，利用某些准则可以抛弃一部分情况不予考虑。其效果（指计算次数）是不能保证的。看来，对于一个给定的点集，希望存在一个有效算法去求出它的SMT，只能从点集的性质去考虑，即当点集满足什么样的条件时，必有一有效算法可以把它的SMT求出来。当然，要得出一有意义的、概括面相当广的条件是不容易的，但这一问题值得探索。
寻 找 最 优 解
对于大型问题或多次重复出现的问题，总希望能找到所有点集的SMT。而对于要求不太高的问题，往往满足一个较好的解答，并不需要动用大型计算机和大量的人力，这样就出现了近似解的问题。近似解就是接近于最优解SMT的解。对SMT的性质，除了知道它至多包含n 2个斯坦纳点和过每一个斯坦纳点至多有三条边通过这两点简单性质，几乎别无所知。因此对于何谓近似解及其求法，就需要仔细考虑了。所幸的是，自20世纪中期以来，这方面取得了不少进步。
平面点集X的生成树中边的总长最小者称为X的最小生成树。对于给定的X，求最小生成树很容易：只需将n（n+1）/2条边按由短到长的次序排列（量纲为nlogn），然后取出其中最短的一条，在图上标出，再取出第二短的一条在图上标出，如此进行。每当发现标出的边形成一个圈时，即将最后取到的边划去，再往下取直到最后。由于每一条边都被考虑到，最后得到的图必是连通的，又因为自始至终不许出现圈的情况，因此最后所得必是一棵树，而且容易证明这棵树决不会比其他的树长，因而是一棵最小生成树（MST），其长记作LM（X）。
据说当初美国的贝尔公司就是按MST来收取长途电话费。（无论这一说法是否确实，该公司对研究MST与SMT之间的关系是很重视的，这可以从它的实验室发表的大量有关文献看出。）后来有人提出异议：认为当点集给定之后，MST的长度总是大于SMT的长度，按MST来计算收费不利于用户，应按SMT来收费，于是便提出了一个问题：这两者之差是多少？
用LS（X）表示SMT的长度，问题就变成如何估计LM（X）－LS（X）。由于X是任意给定的集，问题正确的提法是：
如何估计 对所有X成立。
若此α与1相差甚少，则以MST代替SMT收费也就无可非议。
先根据给定点数目n甚小，例如3，4，5的情况对上述比值进行计算，然后对α的数值作一些猜想。若X={A，B，C}为一正三角形的三个顶点，则易算出
L(X)/L(X)=/2 。
若将此三角形的三个顶点从各自附近截去，则得一六角形，容易算出此时这一比值仍然接近 ，但比它稍小一些。
吉尔伯特（E.N.Gilbert）和波拉克根据对一些问题的实际计算，认为这一最大的α可能就是 。于是在1968年，他们发表了一篇有一定影响的文章，其中提出一个猜想，就是
L(X)/L(X)=/2
对所有有限点集X成立。开始时，这一猜想称为G-P猜想，后来则改为斯坦纳比猜想。由于 ≈0.866，以MST去代替SMT，损失不会超过13.4%。对于一般性问题还可以接受。
这一猜想被提出之后，立即引起了不少同行的兴趣。当n=3时，只有一棵斯坦纳树，SMT和MST的关系由图像上可以清楚看出，要证明G-P猜想成立是很容易的。当n=4时，情况就较为复杂。此时有两棵不同的斯坦纳树，LS（X）与LM（X）的关系不是很明显。在1968年，波拉克在证明n=4的G-P猜想成立时，其证明就有14页之多。对n=5的情况，有几种不同的证明，最早是1985年由我国姚恩瑜等人做出的，他们的证明相当复杂。当n=6时，国外有人发表了他们的“证明”，但那谈不上是一个证明。
对于一般的n，2000年以前，在这问题上真正取得进展的应推金芳蓉和黄光明在1978年发表的结果，他们证明了
L(X)/L(X)≥0.74 ，
而且证明也只对部分情况成立。但无论如何，在该问题上已经取得了突破。笔者在2000年的《运筹学学报》第一期上发表了一个证明，同时对n=3，4，5的情况也给出了简单的证明[1]。
像上述证明G-P猜想成立这样的工作，称为最坏情况研究，即证明该不等式对所有X成立。而实际上，只有某些特殊的X（最坏情况）才使
L(X)/L(X)=/2 。
例如对于矩形来说，设X为它的四个顶点，若短边长为1，长边为l≥1，则容易证明
L(X)/L(X)≥0.91 ，
而且l越大，此比值越接近于1。那么X具有什么样的结构，才使与之相应的比值 接近于 ，例如大于或等于0.9；是否存在某一算法，在计算的复杂度方面与求最小生成树具有同样等级或稍复杂些，比如增加n倍，但它给出的比值L(X)/L(X)却比 要大，比如大于或等于0.9。
网络图中的斯坦纳树问题
上文谈到的都是欧氏斯坦纳树问题。因为对于两点（x1，y1）和（x2，y2）的距离，用的是欧氏距离
d=。
但实际生活中的许多问题，两点间的距离却不能如此定义。例如在一城市中有若干个点，需要修建一些管道把它们连接起来。这时从甲点到乙点的距离就不能以欧氏距离来计算。你不能将管道从别人家的屋里或地下穿过去，这样就产生了网络（图）上的斯坦纳树问题。
在这类问题上工作的人不少，也有种种算法被提出来，但这类问题也是NP完备问题，已经提出的算法实际上都是遍数法的某种改进。由于作者们所使用的程序语言、计算机类型、用于计算的例子的来源和数量以及判断最优性准则等等难以统一，又很少有读者去验证他们的结果，因此一般也就姑妄听之。
在图上的斯坦纳树中，有一类具有普通性的是在由许多相互垂直相交的直线构成的网络上的斯坦纳树问题（RST）。这类问题在超大规模的集成线路设计中具有很重要的意义，在系统发育学中也常用到。
设要在一板块上某些规定的地方打孔，而打孔机的运动只能是：向前、向后、左移或右移。这时就在所给的板块上，过每一给定的点画上横向和垂向的直线，因而这些点全在格子点上。在保证所有被指定的点都能打上孔的要求下，如何设计打孔机的运行线路，使总的线路之长（运行时间）为最小？这种线路也称为斯坦纳最小树，以RSMT记之。第一个字母R表示所走的路线是按横线或垂线方向进行。研究此类问题时，两点（x1，y1）和（x2，y2）之间的距离则是按照|x1－x2|+|y1－y2|来计算。
在电子工业生产中，具有同样设计需要打孔的板块数目很大，打孔机运行线路的选取便是一个重要问题。早在1970年代中期就有人开始研究这一问题，至今不衰。
如前所述，各种用于解决这一问题的方法都是启发式的，只能用于n相当小的情形。对于上述的问题，当X给定之后，也可定义它在所述网络上的最小生成树，也可求它的斯坦纳比，即 。黄光明在1976年证明这一比值大于或等于2/3 ，而且这个数值是不能改进的。但2/3太小了，若用RMST去替代RSMT，则损失达1/3，很难承受，必须改用别的图形去逼近RSMT。这一问题也引起了许多人的注意，并获得进展。
设G是个图，将G中只与一条边相连的那种顶点叫做G的终端，其余的仍叫做顶点。设G是一个将X中的点连接起来的连通图。设H是G的一个连通子图，它的终端全属于X，其他的顶点则不属于，则称H为G的一完全分支。这样，每一连接X的连通子图G都可以分成若干个（除终端外）互不相交的完全分支。若G的任何完全分支的终端数皆不超过k，则称G为k-限制图。
设X={A，B，C}，AB=2，C到AB的垂足D为AB的中点，CD=1。显而易见，X=RSMT即为AB+CD 。若用X的2-限制树（即最小生成树）去逼近X的RSMT，则此2-限制树的总长为4，G-P猜想的比值为3/4=0.75。若用3-限制树去逼近G-P猜想，此比值为1。容易看出，对于一般情况，k越大，k-限制树越接近RSMT。上面提到的黄的结果，即用2-限制树去逼近X的RSMT，G-P猜想的比值大于或等于2/3 。伯曼（O.Berman）等在1992年证明：若用3-限制树去逼近，则G-P猜想中的比值大于或等于11/8 。这结果仍不甚佳，因为在最坏的情况下，损失可达37.5%。即使对k=10，也仍可能有32%的误差。无论是一般的斯坦纳树问题，还是网络图上的斯坦纳树问题，皆是值得深入研究的问题。
[1] 越民义.组合优化导论.杭州：浙江科学技术出版社,2001