计算欧几里德斯坦纳最小树的精确算法与实验比较

13原始论文EURO Journal on Computational Optimization（2020）8：309https://doi.org/10.1007/s13675-020-00125-w计算段上的Euclidean Steiner树恩斯特·阿尔特豪斯1·费利克斯·劳特伯格2·莎拉·齐格勒1投稿时间：2019年11月5日/受理时间：2020年5月18日/在线发表时间：2020年6月11日©作者（S）2020摘要在经典的欧氏斯坦纳最小树（SMT）问题中，我们在欧氏平面上给定一组点，我们应该找到连接所有这些点的最小长度树，允许添加任意额外的点。我们调查的变体的问题，其中输入是一组线段。我们允许这些段的长度为0，即，它们是点，因此我们推广了经典问题。此外，它们可以相交，这样我们就可以对多边形输入进行建模。如Juhl等人的GeoSteiner方法（Math ProgramComput 10（2）：487-我们证明了这些完整的组件，这使我们能够使用几乎相同的GeoSteiner算法在经典的SMT问题的结构定理第二阶段，选择一个最小的成本子集的构造完整的组件，是完全相同的GeoSteiner方法。最后，我们报告了一些实验结果，表明我们的方法比通过对片段进行采样获得的近似解更有效。欧氏斯坦纳最小树·精确算法·结构定理数学学科分类计算几何BErnst Althausernst. uni-mainz.deFelix Rauterbergf.web.de莎拉·齐格勒gles@uni-mainz.de1Johannes Gutenberg Universität Mainz，Mainz，Germany2德国达姆施塔特工业大学13310E. Althaus等人1 介绍我们感兴趣的是以下问题：给定欧几里得平面中的一组线段，通过最小总长度的附加线段连接这些线段，其中我们可以使用额外的点，称为Steiner点。我们将把这个问题称为线段上的欧氏斯坦纳最小树（SMT）问题，并在后面正式定义它（见图11）。1为例）。我们允许这些段的长度为0，即，它们是点，因此我们推广了经典问题。此外，它们可以相交，这样我们就可以对多边形输入进行建模。这个问题的动机是一个地理学生的需要，他想连接一组高度相互关联的区域，描述为平面上的多边形要构建的网络的部分已经存在的情况当建造一个电网或一些管道时。在经典的Euclidean Steiner最小树问题中，输入只是一组称为终端的点。它有许多应用，并已被广泛研究，因为它的介绍。最有效的公开实现是Juhl等人的GeoSteiner包（2018），它实施了Winter（1985）首次引入的两阶段方法在第一阶段，生成一个所谓的全分量的超集，在第二阶段，计算这个超集的最小子集第一阶段的算法基于Winter和Zachariasen（1997）的方法，而第二阶段基于Warme（1998）的方法或者，第二阶段可以通过使用图中Steiner树问题的算法来解决，如Polzin和Daneshmand（2003）所示。后续论文中给出了计算研究和几项改进（Juhl等人，2018; Warme等人，1999，2000）。上面提到的作者考虑了欧几里得Steiner树问题的几种变体，例如避障Steiner树（Zachariasen和Winter1999），其他度量的Steiner树，如曼哈顿距离（Warme1997）和位于多边形内的Steiner树（Winter等人2002）。据我们所知，我们正在调查的问题以前没有考虑过。图1.我们看到了以红色粗体显示的线段集。SMT由所有显示的部分组成，包括红色部分，即，我们将输入段定义为属于SMT。添加黑色、蓝色和绿色的线段是为了获得连通性，这些线段被称为非终结线段，其中不同的颜色对应于不同的全分量（在第2节中定义）。SMT的Steiner点是以蓝色计算段上的Euclidean Steiner树31113=∈SSS将点输入推广为段输入被研究用于计算几何中的几个问题，如计算段Voronoi图（Karavelas2004）或最近对问题（Daescu et al.2006年）。我们的算法是基于Steiner最小树的一个结构定理，将允许我们使用一个算法，这是非常相似的GeoSteiner中实现的，所以我们可以重用他们的第二阶段的实现我们的方法精确地解决了这个问题，并且当我们对给定的片段进行采样时，比不精确的解决方案更有效（参见第5节对比较中使用的采样方法的描述）。本文组织如下：在下面的部分中，我们正式定义了问题，并介绍了必要的符号和定义。在第3节中，我们证明了我们的主要定理，并讨论了如何修改GeoSteiner中第一阶段的算法。在第4节中，我们展示了如何减少计算的全分量超集的大小。我们展示了一些计算实验节。5、最后，在第五节结束。六、2 方法的基本定义和概述我们现在正式定义Steiner最小树问题和一些进一步的基本实体。我们遵循Brazil和Zachariasen（2016）的方法。一个几何网络G（ V（ G）， E（ G））是一个嵌入平面的图，即，顶点V（ G）是平面中的点，边E（ G）是连接其中两点。1几何网络的长度是E（ G）中所有线段的欧几里得长度之和。注意，与平面嵌入图相反，我们不要求边不相交。虽然这对于Steiner最小树显然是正确的，但我们不想争论当我们在中间步骤中构造几何网络时这是否总是正确的。定义1给定一个有限段集S，我们定义S的Steiner树T为包含S的连通几何网络。S的Steiner最小树（SMT）是S的最小总长度的Steiner树。在下文中，我们假设线段的内部是成对不相交的，因为我们可以在它们的交点处分割线段线段s称为终端线段，它们的端点称为终端点。开放的终端段是没有端点的终端段。一个由端点和端点线段组成的集合称为连通分支，如果它是一个极大集合，使得集合中的每对点之间都有一个连接。Steiner树的边中不包含的部分称为非终端线段，不是终端点的点称为Steiner点。我们假设Steiner点的度至少为3，因为度为0或1的 Steiner点可以被删除（连同度为1的点的入射边）而不增加几何网络的长度[1]与我们的定义相反，Brazil和Zachariasen（2016）允许边是两个端点之间的任意简单曲线，但显然在最小成本网络中，它们必须是直线。此外，它们需要连接几何网络。312E. Althaus等人13S[客户端][客户端]|S=-T=TT- -S||=||如果一个Steiner树包含一个度为2的Steiner点p，它的邻居是q和r，我们可以去掉p和边pq和pr，并添加一个边qr，得到的几何网络仍然是一个Steiner树，它的长度不能增加。请注意，一组线段本身就是一个几何网络。Steiner树的拓扑是无向图（V（）、 E（））─放置几何网络，其顶点标记有端点、开终端段和Steiner点。因此，在拓扑中，端点的位置是固定的，开放的终端段的位置在段上，但不在其端点之一上，斯坦纳点的位置是自由的。拓扑表示图的节点和边，但没有关于边的长度 或 节 点 的 位 置 它 们 仅 指 定 相 邻 节 点 。 请 注 意 ， 这 些 定 义 与 Brazil 和Zachariasen（2016）的定义略有不同，因为我们的问题更普遍。注意，在Steiner树的这个定义中，SMT的长度包括给定段的长度。作为SMTT for基础的图不一定是树，因为它包含圈当且仅当给定的段形成它们时。如果我们收缩每个这样的循环到一个节点，它就变成了一棵树，记为T。图G（ V， E）的边（u，v）的收缩导致图Gr（V r，E r），其中u和v被单个节点u v代 替 ，并且边的每个端点u或v被u v代替。一个圈的收缩是其上所有边的收缩由于我们允许一个线段只由一个点组成，因此线段上的SMT问题推广了经典的欧几里德SMT问题（在终端上），因此该问题是NP-难的。下面的基本性质可以很容易地表示出来，并且是SMT在终端上的众所周知的性质的概括引理1设T是S上的SMT。1. T的入射非终端段形成至少2 π/3的角。2. 一对非终端线段和终端线段以π/2的角度相交或更大3. 如果终端点不与终端段相关联对应的末端段具有长度0），并且否则具有至多两个关联的非末端段。4. T中的斯坦纳点的度数为3，每对入射边相交的角度为2 π/3。5. T至多有n2个Steiner点和至多2n3个非终结线段，其中n是由S构成的几何网络的连通分支数.草图（Sketch）1. 假设两个入射的非终端线段pq和pr的夹角小于2π/ 3。设qr在pq上，rr在pr上，使得pqrprr如果我们用线段ps，qrs和rrs代替Steiner树的线段的部分pqr和prr，其中s是三角形p， qr，rr的Fermat-Torricelli点，我们得到一个较短的Steiner树。计算段上的Euclidean Steiner树31313SS|SS2. 假设非终端线段pq与终端线段pr的夹角小于π/2。在pq上选择qr，使得qr与通过p和r的直线的垂线与线段pq上的直线相交，并设rr为交点。如果我们用qrr rr代替线段pq的部分pqr，我们得到一个更短的Steiner树。3. 接下来的两个点是由所有线段入射到一个点的角度之和为2π的事实得出的。考虑一个端点p。如果所有入射到p的线段都是非终结的，它们之间的夹角必须至少为2π/ 3。因此，最多有3个。如果至少有一个末端线段，则不可能有三个非末端线段，因为它们与末端线段的夹角至少为π/2，它们之间的夹角至少为2π/ 3。4. 当度数至少为3时，两段之间的角度至少为2π/ 3。5. 考虑一个SMTT，收缩几何网络的所有连通分支，以获得Tr。显然，Tr是一棵树，最多有n片叶子，并且包含所有非终结线段。因此，Tr最多可以有n-2个斯坦纳点，因为斯坦纳点不是叶子，而且它们的度至少是此外，由于树最多有n+n−2= 2n− 2个节点，因此Tr的边总数有2n−п给定一个Steiner树T，T的满拓扑是T的内顶点为Steiner点的极大子树。T的全分支是全拓扑的几何网络。因此，完整的拓扑只是树，其叶子用端点或开放的终端段标记，但没有任何几何信息。请注意，完整组件的所有叶子都在的元素上（参见图2的示例）。请注意，可能有多个完整组件具有相同的完整拓扑。在经典的欧几里德斯坦纳树问题中，对于每个全拓扑，存在唯一的最小全分量（参见，例如，Brazil and Zachariasen2016）。同样，这些定义与Brazil和Zachariasen（2016）的定义略有不同，因为我们有一个广义问题。与经典的欧氏斯坦纳树问题一样，我们希望在第一阶段枚举SMT的全分量的超集在下文中，我们推导出全分量的一个属性，这将允许我们使用与经典SMT中几乎相同的图2我们展示了三个可能的完整组件，它们连接着四个给定的多边形。前两个几何网络具有相同的拓扑，而第三个几何网络的拓扑是不同的，因为其中一个顶点的标签是不同的（连接到左上角线段的顶点在最后一个拓扑中是端点，在前两个拓扑中是开放的终端线段我们的结构定理表明，我们可以限制全拓扑的最多一个开放的终端部分，即全拓扑，我们不必考虑前两个，而只需考虑第三个。314E. Althaus等人13不联系我们在第二阶段，我们选择一个最小的成本子集的枚举的完整的组件，其工会形成一个斯坦纳树。它的工作原理与经典SMT完全相同。我们将超图中的满分量超集解释为带权超边，并计算超图中的最小生成树在我们的实验中，我们使用了Juhl等人提供的实现。（2018年）。在经典的情况下，枚举的全组件的数量不能比可能的拓扑的数量更好地有界。由于超图问题中的最小生成树是NP-难的，并且我们在分析运行时间时不能在我们构造的实例中使用一些特殊的结构，所以我们也不能比指数更好地分析第二阶段的运行时间（经典情况也是如此）。3最优Steiner树的结构我们现在概述（稍微修改）用于枚举全分量超集的经典SMT算法，并参考Winter和Zachariasen（1997）了解详细信息。对于两个点p， q，设ep，q为点q绕p逆时针旋转π/3得到的点。因此，ep， q和eq， p是两个等边三角形的第三个角，角为p和q。关键的见解是，对于每个固定的拓扑结构，有一个唯一的最小成本完整组件与此拓扑结构，可以计算如下。具有两个端点的拓扑的最小成本全组件就是连接两个端点的线段。任何包含至少三个终端的拓扑都有两个终端u和v，有一个共同的相邻斯坦纳点s。设t是与s相邻的第三个点。已知s位于两个等边三角形之一的外接圆的u和v之间的弧上，这两个等边三角形的角是u和v，并且eu，v或ev，u。这条弧称为相应等边点的斯坦纳弧可以计算出应该使用两个等边三角形中的哪一个，但我们在这里不讨论这个我们简单地假设eu，v是这个三角形的第三个角在算法中，两个等边点都被枚举。给定一个包含u，v，s和t的极小满分支及其拓扑，如果我们用线段teu，v替换满分支中的线段su，sv和st，我们得到一个极小满分支，u，v， s eu，v，即，其中，我们移除顶点u、v和s以及边su、s、v和st，并添加端点e u、v和边teu、v（参见图3的说明）。因此，我们可以通过迭代地用适当的等边点替换两个相邻的终端和Steiner点，直到只剩下一个终端和一个等边点，来迭代地构造给定拓扑的最小全分量在这种情况下，最小完整分量就是这两点之间的直线。相反，我们可以通过迭代地从两个已知的等边点构造所有的等边点来枚举所有具有相应的最小满分量的拓扑，从端点开始，然后将等边点连接到另一个端点。显然，在这样的构造中使用的终端必须是成对不同的，因此这个枚举过程是有限的。计算段上的Euclidean Steiner树31513图3我们想构造拓扑的一个最小全分支，其中a和b连接到一个公共的Steiner点，称为s，c和d都连接到sr。最后，这两个斯坦纳点是有联系的为了构造一个最小的全分支，我们首先构造等边点ec， d，它允许我们将拓扑简化为三个端点a， b和ec， d。然后，我们构造等边点eb，ec，d，将拓扑简化为端点a和eb，ec，d。仅由端点a和eb， ec， d组成的拓扑的最小全分量正好是它们之间的线然后，我们通过首先用线段as，bs和ec，ds替换eb， ec， d来反转简化，其中s是线段aeb， ec， d与eb， ec， d的Steiner弧。最后，我们将线段sec， d替换为线段ssr，csr和dsr，其中sr是线段ec， ds与ec， d的Steiner弧的交点。最后的圆满组件显示为黑色枚举算法构造下面的等边点和端点列表。从所有终端开始对于列表中的每对点p， q，我们构造等边点ep，q和eq， p，只要：– 用于构造p和q的端子是不同的。– 修剪测试不能排除潜在的完整组件，即，测试表明潜在的完整组件不能是SMT中完整组件的一部分。在构造了所有这些等边点之后，我们可以通过将这些点中的一个点p与在构造p时没有使用的端点t相结合来构造所有的全分量。请注意，我们多次枚举全分量：我们可以选择一个任意终端作为最终连接到等边点的终端。在Brazil和Zachariasen（2016）中，算法略有不同，以确保每个完整组件只枚举一次。正如我们将在下一段中看到的，对于我们的方法，我们以这种方式修改算法是有帮助的我们将证明，对于我们的问题，我们可以假设S的SMT的每个全分量最多包含一个开放终端段，并且我们几乎可以使用316E. Althaus等人13S不不+++SS≤≤≤与上面描述的算法相同。我们选择开放的终端段（如果有）作为最终连接到等边点的全分量的一部分，因此，等边点仅由端点构成。因此，等边点列表的构造与经典SMT完全一样，只是从端点而不是端子开始此外，我们确保用于构造等边点的端点来自几何网络的不同组成部分，该几何网络恰好由。为了从一个等边点和一个终端构造全分支，我们必须另外考虑终端是一个开放终端段的情况在这种情况下，我们必须找到开放终端段上的点，该点导致开放终端段和构造的段之间的角度为π/引理2对于每一组线段，存在一个Steiner最小树T，使得每个完整拓扑最多包含一个标记为开终端线段的顶点。证明考虑一个Steiner最小树，它有最大数量的满分量。只要存在至少一个具有至少两个开放终端段的拓扑的完整组件，我们将用具有至少一个较少开放终端段的相同成本/长度的拓扑和完整组件来替换这样的拓扑和完整组件考虑具有至少两个开放终端段的拓扑的全组件F，并且设P是两个开放终端段之间的路径我们表明，我们可以移动段的完整组件，而不改变其成本，直到P的一个（或两个）端点（S）是（是）移动到端点的开放终端段或完整的组件分裂成两个（矛盾的事实，我们认为一个最佳的斯坦纳树与最大数量的完整组件）。设b0，b1，. b n是P，s1，...，在P上的斯坦纳点，a1，...，在与S1，...，sn，s0和sn1是P（见图）4）.假设我们移动路径P的线段，方法是在它的开放终端线段上移动s 0（在任一方向上），s i沿着a i2的方向移动，我n且最终在其开放终端段上为Sn1，使得所有所得段平行于对应的原始段。下面，我们展示了完整组件的长度我们一直移动，直到s0或sn1到达开放终端段的端点，或者直到某个非终端段退化为长度0。在第一种情况下，我们减少了完整组件中开放终端段的数量。第二种情况不可能发生，正如我们在下文中所看到的。如果段bi，1在n<退化的情况下，我们得到一个4次的Steiner点，而不增加长度的完整组件。因为我们假设我们从最小的全分量开始，所以这个全分量仍然是最小的，因此我们与引理2部分矛盾4.如果b0或bn退化，则不满足开放终端段上的角度条件（引理2第2部分），因此所构造的全分量不可能是最小的。最后，如果段ai降级，我们要么得到一个具有更多完整组件的SMT（如果ai的第二个端点是终端），这与我们开始的假设相2 线段的方向是指线段的支撑线的方向计算段上的Euclidean Steiner树31713+≤ ≤−图4我们画出一条路径s0，s1，. Sn1之间的两个开放的终端段，其中段B0，B1，.， bn. 如果我们沿着各自的开放终端段移动s0和sn，并且Steiner点si在方向ai上， 我n，使得路径的结果段平行于原始段，路径的总长度不变用一个具有最大数量的全分量的SMT，或者我们再次得到一个4度的Steiner点（与引理2第4部分相矛盾）。因此，仍然需要证明上面定义的移动不会改变完整分量的长度。考虑一个小的移动，并围绕斯坦纳点s1，...，s n，使得对于Steiner点s i，三角形的三个线段与bi1，bi和ai正交（再次参见图4）。这些三角形的确切大小并不重要，只要线段具有非零长度并且三角形不相交即可。请注意，这些三角形是等边的，因为三角形的三个线段中的两个之间的角度每次都是2π/3。三角形外部的完整组件的部分的总长度不会改变，因为P的线段平行移动并且与三角形的线段正交三角形内的长度不因Viviani定理而改变 Pech 2007），指出等边三角形中任何一点到三个线段的距离之和为等于三角形的高度，即，它是恒定的。п4 部分拓扑回想一下在Sect.3 .第三章。我们从端点开始迭代构造所有等边点。在这一节中，我们展示了一些方法来从这个枚举中排除许多等边点每个等边点替换完整零部件的一部分。我们说一个等边点的拓扑是被等边点所取代的完整分支的拓扑的子树。在下文中，我们考虑这个拓扑植根于Steiner点，该点位于等边点的Steiner弧上。318E. Althaus等人13==图5 假设我们构造ep，q，peu，v，并且eu，v的弧已经被简化为ur和vr之间的子弧。我们可以首先将ep，q的弧限制为pr和qr之间的子弧，如图中所示。根据几何图形的必要性绘制此外，eu，v的子弧可以简化为pr和vr，如果在ep， q内使用。我们尝试通过额外的修剪测试来进一步减少子弧在构造时，我们知道对应于等边点ep，q的拓扑根的Steiner点位于p和q之间的Steiner弧上。对于给定的全拓扑，对于在其枚举中使用的给定等边点ep，q，修剪测试试图限制Steiner点从全弧的位置p和q之间的点pr和qr之间的某个子弧（见图1）。（5）称为可行性亚弧如果可行子弧不包含点，我们可以修剪等边点，也就是说，如果我们将它从等边点列表中删除，则不能从它构造等边点或全分量。如果我们减小一个等边点的可行子弧的大小，该可行子弧用于构造另一个等边点，则其弧也可以减小。当减少可行子弧时，我们假设Steiner点位于子弧的两个端点之一，并运行一些测试（见下文），这些测试可能会排除SMT中完整组件的此位置。如果是这种情况，我们通过将我们刚刚测试的端点移向另一个端点来缩小可行子弧，直到该位置不能再被排除。首先，我们可以根据几何形状限制弧，即，如果根的Steiner点位于其可行子 弧 内 ， 则 所 有 其 它 Steiner 点 也 必 须 位 于 其 可 行 子 弧 上 Brazil andZachariasen2016）。另一个著名的修剪测试的例子是lune属性（再次参见Brazil和Zachariasen2016），它的工作原理是如下考虑一个等边点ep，q，设可行子弧由pr和qr限制。此外，设vr是p eu，v的Steiner弧与线段qrp的交点。如果有一个端点r没有在ep， q的构造中使用，它比qrvr的长度更接近qr和vr，则线段qrvr不能是SMTT的一部分，因此qr可以从可行子弧中排除。这是因为我们可以从T中去掉线段qrvr，得到两个连通分量，qr和vr在不同的分量中。然后我们可以添加qrr或vrr，以获得比T短的Steiner树。因此，我们可以将qr移向p，直到这个冲突得到解决。经典Steiner树问题的大多数剪枝测试也可以在这里使用瓶颈Steiner距离检验、楔形性质、投影检验和半月形性质。这些测试在Brazil和Zachariasen（2016）中有详细解释存在一些附加的和可扩展的测试，其使用一些点已经由输入S的段连接的事实，如下面所解释的计算段上的Euclidean Steiner树31913SSS∈SSS∈∈SS图6假设a是可行子弧的一个端点，ear，eu，br. 我们想从可行子弧中移除a，考虑线段ab，如果a确实是Steiner点的位置，则线段ab将是全分量的线段点p1比线段ab的长度更接近a，并且点p2更接近b，因此，a可以从可行子弧中移除。输入P不与ab的弦月相交Steiner树在段上的第一个可扩展测试是lune属性。经典斯坦纳树问题中的lune属性的主要思想是，给定SMTT，不可能有一个终端比该段的长度更接近T的两个端点。这可以扩展如下：如果两个点p1，p2（终端点或开放终端段上的点）已经在，不能有线段abT，使得a比线段ab的长度更接近p1，b更接近p2。请注意，连接p1和p2的线段不一定与经典检验中使用的弦月相交，如我们在图6的例子中所见。修剪测试的正确性在下面的引理中示出。引理3给定一个有限段集，考虑一个潜在的全分量F。F不能包含非终结线段ab使得在的同一连通分支内有两个点p1，p2使得p1比线段ab的长度更靠近a，p2比线段ab的长度更靠近b。我们将用反证法证明这个引理。假设非终结线段ab是SMT的一部分，并且有两个点p1和p2是SMT的同一连通分支的一部分，其中p1比ab的长度更靠近a，p2比ab的长度更靠近b。通过删除线段ab，SMT分解为两个不相交的树t1和t2，其中a∈t1，b∈t2。请注意，p1和p2在同一棵树中，因为它们已经在S中连接。如果p1∈t2，我们可以插入较短的边 ap1，得到较短的Steiner树，这是一个矛盾。类似地，如果p1∈t1，我们可以插入较短的边bp2.п第二个测试在斯坦纳树段是基于角度的条件，在引理1第2部分。每个入射到端点p的非终结线段必须与所有邻近p的开放终结线段至少成π/2的角。这可以用来减少可行子弧。特别地，如果终端点具有至少两个关联的开放终端段，则由其构造的任何等边点不能在两个相邻开放终端段的具有小于π的角度的楔形的一侧上。此外，它不能是一个潜在的完整的部分320E. Althaus等人13R××分支与可能的全分支（引理1第3部分）的另一个线段相交，或者与一个开终端线段相交。5 实施和实验评价我们实现的算法，以构建一个超集的最佳Steiner树的完整组件在Java中，只使用基本的修剪测试，已知的经典SMT问题。为了选择最优树的完整组件，我们使用了Juhl等人的GeoSteiner 5.1的实现。所有实验都在具有2.40 GHz和6 GBDDR3-SDRAM内存的Intel Core i5 2430 M处理器的单核上完成我们做了三个不同的实验。首先，我们解决了地理学家的实例（见图7a），并将其与以下方法进行了比较：给定距离阈值<$，用距离最大为<$的最小数量的等距样本点替换每个片段。然后，我们用GeoSteiner解决了这个经典的欧几里得SMT问题（见图1）。7b）。我们的算法在输入55个多边形的情况下运行时间为3 s，而使用有用的<$求解具有790个样本点的采样实例需要16 s。采样实例的解决方案具有与收缩给定多边形时的最优解决方案相同的拓扑，并且仅稍微大一点。如果我们降低采样密度，这就不再正确了在采样密度为所示实例的四分之一的情况下，仅保留55个多边形的段的542个端点，并且运行时间为12 s，并且当收缩给定多边形时，解决方案不是树采样方法成本更高的主要原因是它枚举了许多包含来自同一多边形的多个端子的等边点注意，这个实例的最优Steiner树是最小生成树（我们将在下面对此进行评论）。其次，我们从Reinelt（1991）中获取了TSP-lib实例，这些实例以前用于对经典SMT问题的GeoSteiner库进行为了得到问题的实例，我们将每个终端连接到其最近的邻居，并解决了产生的实例。我们试图在30分钟内解决46个实例，其中198个高达85900个点构造的连通分量的平均大小在2.3和3.9之间（参见图8b的示例）。在25分钟内，解决了27个问题。10个实例可以在不到30秒的时间内解决，另外4个实例可以在不到60秒的时间内解决。在不到5分钟的时间内解决了20个实例，在11分钟内解决了26个实例。算法的第一阶段在3.58到1318.55秒之间，第二阶段在0. 11和2579.所有低于1100点的实例都可以在62秒内解决。最大的可解实例包含3038个点，并且构造的等边点的数量在193和27878之间变化。最后，我们尝试用n个多边形构造随机实例，这些多边形最多有m个线段，看起来与地理学家的实例相似。结构如下。首先，创建一个kk网格，每个网格的大小为11，对于给定的k.然后，选择n个网格单元，并在每个选定的网格单元内创建一个多边形，如下所示。选择从{3，...，m}。固定点p0=（0，0. 5）和p“m r / 2 =（1，0. 5）。然后，构造随机点pi=（xi，yi），其中1≤i<计算段上的Euclidean Steiner树32113=[−图7a我们用我们构造的算法解决了地理学家的实例。b我们使用相同的实例和相应的采样实例，让GeoSteiner解决问题[（2 i-1）/mr，2 i/mr]和y i在（0. 5，1]。对于<< 0，0。5）。多边形（p0，p1，...，p mr 1，p0）是非自相交的，建设值k用于控制占用网格单元与网格单元总数相比的百分比，我们称之为密度。例如，如果一个实例有50个多边形，k为10，则密度为0。5（见图）8A为例）。我们感兴趣的是测量的运行时间，构建的等边点和完整组件的数量，斯坦纳比取决于多边形的数量，每个多边形的段数和密度的数量被占用的网格单元格除以网格单元格的总数对于这些数量中的每一个，我们构建了10个随机实例，并取测量的平均值在图9中，我们将运行时间显示为多边形数量的函数对于每个多边形的不同的最大段数。在这个实验中，10%的网格单元被多边形占据。正如我们所看到的，对于每个多边形的少量段，我们甚至比经典情况下的算法实现更快（使用仅将每个多边形的第一个角作为输入的实例）：然而，运行时间随着段的数量而增加。在多边形中。322E. Althaus等人13图8a我们随机生成的实例。每个多边形都位于一个网格单元内，并且在网格单元的左侧边界和右侧边界的一半高度处具有端点。b从TSPLIB的实例“ali535”构造的实例807060504030201000 10 20 30 40 50 60 70 80 90 100数量的多边形10段20段40段点输入（参考）图图9运行时间与多边形数量的函数关系。不同的图对应于每个多边形的这可以用图10所示的实验来解释，在图10中，我们显示了相同实例的构造等边点的数量。对于少量的段，这个数字比经典的Steiner树问题小得多，但随着段的数量而增加。构建的完整组件的数量远小于等边点的数量，并且仍然小于经典情况下的数量，即使在增加每个多边形的段数时也是如此（见图2）。11）。这个数字只是稍微大一点运行时间计算段上的Euclidean Steiner树323134500400035003000250020001500100050000 10 20 30 40 50 60 70 80 90 100数量的多边形10段20段40段点输入（参考）图10构造的等边点的数量与多边形的数量的关系。不同的图对应于每个多边形的不同的最大段数。虚线显示了点输入3002502001501005000 10 20 30 40 50 60 70 80 90 100数量的多边形10段20段40段点输入（基准）MST（基准）图11作为多边形数量的函数的构造的完整组件的数量。不同的图对应于每个多边形的不同的最大段数。橙色虚线显示了点输入的构造全分量的数量，灰色虚线显示了最小生成树的边的数量多边形数减1比最小生成树的边的数目（即，多边形的数量减1）。在表1中，我们显示了Steiner比率和构造的等边点的数量取决于多边形占据的网格单元的百分比的增加，例如50个多边形最多10个段。正如我们所看到的，Steiner比率接近1，并且构造的等边点的数量下降到经典Steiner树问题的数量以下我们观察到（见图）。1）Steiner比和最优解中的Steiner点的数量随着实例的密度而减小实例中FST数量等边点数324E. Althaus等人13表1平均斯坦纳比、构造的全分量的平均数、构造的等边点的平均数和构造的最优解中的斯坦纳点的平均数取决于占据的网格单元的百分比。 对于经典的Steiner树问题，我们观察到平均Steiner比率约为0。9678. 为了计算这些斯坦纳树，136。平均构建6个全分量占用网格单元的百分比（%）Steiner比率构造的全组件等边点数最优解中的Steiner点数0.010.9686117. 053388十八岁60.10.9716一百零六43979.4十五岁80.30.9725一百零三83290。013岁80.50.9782七十七。82102号8十一岁410.9801七十三。62073年0十一岁030.984961岁。41336年87 .第一次会议。850.9917第五十七章。01103号6四、870.993655个。4九六九4五、090.991958. 6971. 47 .第一次会议。4110.994155个。4881. 2四、0130.9921五十六6912 6五、2150.990255个。6九百块4四、2200.992755个。4857. 0五、2300.995151. 0589. 81 .一、4400.997750块4548. 40的情况。6500.9991第四十九章。6五百块00的情况。6600.9999第四十九章。6465 40的情况。2751.0000第四十九章。2438. 20的情况。0地理学家认为，与它们的距离相比，这些区域相当大，这解释了这种情况下的施泰纳比率为1。6 结论我们考虑了欧氏斯坦纳最小树问题的变体，其中输入是一组线段而不是一组点。我们证明了一个结构定理的Steiner最小树，使我们能够遵循几乎相同的方法，在经典的SMT问题的全组件。此外，我们实现了我们的算法，并表明它可以解决中等规模的问题在合理的时间。我们提供了一些额外的修剪测试，可以更快地实现。计算段上的Euclidean Steiner树32513我们相信，我们可以扩展这种方法，以避免类似于Zachariasen和Winter（1999）的方法的障碍这将是有趣的工作扩展到其他指标和非线性输入。326E. Althaus等人13鸣谢开放获取基金由Projekt DEAL提供。我们要感谢Manfred Lehn仔细阅读了Sarah Ziegler的硕士论文和一些富有成效的讨论。特别是，证明的结构定理是更加优雅感谢他的意见。开放获取本文章根据知识共享署名4. 0国际许可证授权，该许可证允许以任何媒体或格式使用、共享、改编、分发和复制，只要您对原作者和来源给予适当的肯定，提供指向知识共享许可证的链接本文中的图像或其他第三方材料包括 在文章的知识共享许可证，除非另有说明，在信贷额度的材料。如果文章的知识共享许可证中不包含材料 要查看本许可证的副本，请访问http://creativecommons.org/licenses/by/4.0/。引用巴西M，Zachariasen M（2016）最佳互连树在平面：理论，算法和应用，第1版。施普林格出版公司，柏林Daescu O，Luo J，Mount DM（2006）由点跨越的线段上的邻近问题。Comput Geom Theory Appl33（3）：115Juhl D，Warme DM，Winter P，Zachariasen M（2018）用于在平面上计算Steiner树的geosteiner软件包数学程序计算10（4）：487Karavelas MI（2004）分段Voronoi图的鲁棒有效实现输入：程序第一届国际研讨会VoronoiDiagrams in Science and Engineering，pp. 五十一至六十二Pech P（2007）Selected topics in geometry with classical vs.计算机验证世界科学，新加坡Polzin T，Daneshmand SV（2003）关于超图中的Steiner树和最小生成树奥珀水库Lett 31（1）：12Reinelt G（1991）^J.P.，pp.376-384Warme DM（1997）A new exact algorithm for rectangular steiner trees.在：网络设计：连通性和设施位置，DIMACS研讨会论文集，新泽西州，美国，1997年4月28日至30日，pp. 三五七至三九六Warme DM（1998）超图中的生成树及其对Steiner树的应用弗吉尼亚大学博士论文Warme DM ，Winter P，Zachariasen M （1999 ）大规模平面Steiner树问题的精确解。在：Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms，17-19 January1999，Baltimore，Maryland，USA.，pp. 979-980Warme DM，Winter P，Zachariasen M（2000）平面Steiner树问题的精确算法：计算研究，pp.81-116. Springer US，波士顿Winter P（1985）在Euclidean plane中的Steiner问题的算法。Network 15：323网络30（3）：149-166Winter P，Zachariasen M，Nielsen J（2002）多边形中的短树离散应用数学，118（1）：55- 72 Zachariasen M，Winter P（1999）Obstacle-avoiding Euclidean Steiner trees in the plane：Anexact algorithm.在：算法工程和实验，国际研讨会