[科普中国]-最小树问题

基本概念

最小树问题是网络最优化问题之一，是指如何从网络的支撑树中求出最小树的问题。求解最小树问题常用破圈法和贪婪算法。最小生成树问题是组合优化中的一个重要的问题。自五十年代后期Rosenstiehl, Prim和Kruskal先后给出求解这一问题的算法以来，人们对这个问题的研究兴趣一直未断，相关的理论被应用到很多领域。现在这个问题己经得到了很好的解决，其中经典的算法有破圈法、边割法、还有避圈法。

研究背景及意义随着网络通信技术的日益成熟，互联网在人们生活中发挥着越来越重要的作用，基于网络的应用和服务也是层出不穷。其中一些应用如视频会议、网络教学、多人游戏等，传输时间长、数据量大、要求网络延迟小，对网络的传输和处理能力要求很高。对于这样的应用如果使用单播或广播方式进行通信，数据需要不断的复制，传输的数据量太大，传输的效率很低。同时在数据传输时需要使用大量的带宽，对带宽的要求很高，带宽较低时很容易使网络阻塞。多播能够有效的解决这些网络应用。

多播(multicast)也称为组播，是一种从源节点向多个目的节点传输同一信息的通信方式。所有的目的节点组成的集合被称为多播组，多播组中的每个成员被称为多播组成员。多播通信有多种方法进行路由，其中最简单的也是最常用的方法是沿树状结构进行路由。多播树(multicasting tree) }'〕是一棵根为源节点的生成树，它包含了所有的目的节点。利用多播树进行数据传输的优点在于，从根节点开始数据以并行方式沿树干传输，最终到达所有的目的节点，这样能够加快传输速度。此外，在数据传输过程中，只在树权处进行数据信息的复制，这样网络中传输的信息最少，能够减少占用的带宽，提高网络利用率。

由于多播路由是根据多播树进行路由的，因此如果能够找到费用最小的多播树，多播路由问题就得到了解决。寻找费用最小的多播树可以概括为寻找给定节点集的最小生成树，这就是S teiner最小树问题，得到的最小生成树称为Steiner最小树。Steiner最小树问题根据不同情况又可以细分为垂直距离的、欧几里得距离的、图的等。由于图的Steiner最小树问题应用最为广泛。

Steiner最小树问题Steiner最小树问题最早被作为一个数学问题提出，是经典的组合优化问题。Steiner最小树问题经历了较长时间的发展，最终才形成完整的定义。早在1634年，法国数学家Fermat提出这样一个问题:假设在平面上有a,b,。三个点，怎样寻找第四个点P，使得点P到点a,b,c的距离之和最小。这个问题后来被称为Fermat问题。

19世纪初，瑞士数学家Steiner将Fermat问题推广为:假设在平面上有a1，a2,a3……an这n(n > 3)个点，怎样寻找一个点P，使得点P到这n个点的距离之和最小。1909年，德国数学家Weber首次把该问题推广应用到工厂选址问题中。假设某地有若干个仓库，想要建造一个工厂，对每个仓库赋一个权值用来表示该仓库的影响因素。如何选择厂址，使得每个仓库的权值乘以仓库到工厂的距离的总和最小。

1941年，Courant和Robbins在《什么是数学》一书中对Fermat问题进行了一种更有意义的推广:假设在平面上有a1，a2,a3……an这n,(n > 3)个点，怎样寻找另外的若干个点，使得原有的n个点与后来加入的点组成的网络的总边长最小。他们把这个问题称为Steiner树问题，并给出了一些基本性质。

在网络通信中，有一些网络应用要求数据从源节点出发，最终被多个目标节点接收，这就是多播路由问题〔细。解决多播路由问题的方法有多种，最简单常用的方法是求解包含源节点和所有目标节点的最小生成树。但是在许多情况下，另外加入几个节点，得到的最小生成树的总边长有可能会更小，这种思想就来源于Steiner最小树问题。

分类Steiner最小树问题可以分为垂直S teiner最小树问题、欧氏S teiner最小树问题、图的S teiner最小树问题，下面分别进行介绍。

垂直Steiner最小树问题假设在平面上有一个节点集P包含n个给定的节点，寻找一棵覆盖节点集P中所有节点的树T，使得树T的总边长尽可能的小。节点pi和pj之间的边长用它们的曼哈顿距离(Manhattan Distance)来表示。树T肯定包含节点集P中的所有点，也有可能包含其他的一些点，把这些后来添加的节点称为S teiner点。总边长最小的树T称为垂直Steiner最小树。由于使用曼哈顿距离来计算，所以节点之间的边为直线或者是折线，所有的Steiner点一定在经过树T的水平线和垂直线的交点上。

欧氏Steiner最小树问题在平面上给定一个节点集合V，寻找另外的一个节点集合S，使得节点集合V∪S的最小生成树T的总长度最小。节点vi和sj之间的边长用它们的欧氏距离来表示。把最小生成树T称为欧氏Steiner最小树。

图的Steiner最小树问题图的Steiner最小树问题是求图中连接给定顶点最小树长的问题，最早是在1971年由Hakimi和Levin提出,1972年Karp证明了在一般情况下，在多项式时间内不可能得到最优解，该问题是一个NP一完全问题。2