Local Optimization in the Steiner Problem on the Euclidean Plane

By the local optimal Steiner tree is meant a tree with optimally distributed Steiner points for a given adjacency matrix. The adjacency matrix defines the point of local minimum, and all arrangements (coordinates) of the Steiner points that are admissible for it define the minimum neighborhood. Solution is local optimal if the tree length cannot be reduced by rearranging the Steiner points. An algorithm of local optimization based on the concept of coordinatewise descent was considered.     

Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of thebottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio √2. In this paper, the special case of the problem is proved to beNP-hard and cannot be approximated within ratio √2. First a simple polynomial time approximation algorithm with performance ratio √2 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio—√2+∈ is proposed, for any ∈>0. Supported partially by Shandong Province Excellent Middle-Aged and Young Scientists Encouragement Fund (Grant No.03BS004) and the Ministry of Education Study Abroad Returnees Research Start-up Fund, and the National Natural Science Foundation of China (Grant No.60273032).     

Grade of Service Steiner Minimum Trees in the Euclidean Plane

Abstract. Let P = {p ₁ , p ₂ , \ldots, p _n } be a set of n {\lilsf terminal points} in the Euclidean plane, where point p _i has a {\lilsf service request of grade} g(p _i ) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ⋅s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points p _i and p _j there is a path whose minimum grade of service is at least as large as \min(g(p _i ), g(p _j )) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies. A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n ^1.5 (log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm. Preliminary computational results are presented.     

Grade of Service Steiner Minimum Trees in the Euclidean Plane

Abstract. Let P = {p ₁ , p ₂ , \ldots, p _n } be a set of n {\lilsf terminal points} in the Euclidean plane, where point p _i has a {\lilsf service request of grade} g(p _i ) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ?s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points p _i and p _j there is a path whose minimum grade of service is at least as large as \min(g(p _i ), g(p _j )) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies. A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n ^1.5 (log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm. Preliminary computational results are presented.     

Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem

We present a class of O(n log n) heuristics for the Steiner tree problem in the Euclidean plane. These heuristics identify a small number of subsets with few, geometrically close, terminals using minimum spanning trees and other well-known structures from computational geometry: Delaunay triangulations, Gabriel graphs, relative neighborhood graphs, and higher-order Voronoi diagrams. Full Steiner trees of all these subsets are sorted according to some appropriately chosen measure of quality. A tree spanning all terminals is constructed using greedy concatenation. New heuristics are compared with each other and with heuristics from the literature by performing extensive computational experiments on both randomly generated and library problem instances. Received October 27, 1997; revised May 7, 1998.     

欧氏Steiner最小树问题的智能优化算法

欧氏平面内连接固定原点的最小树长问题，即欧氏Steiner最小树问题，为组合优化中的NP难题，因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将中面划分成网格，然后分别介绍两种算法的原理及实现过程，最后通过一系列计算实验，测试了算法的运行性能，获得了较好的效果。     

On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

一种求解欧式平面TSP问题的混合算法

TSP问题是一个经典的组合优化问题。本文采用基于凸多边形的插入方法来构造路径,然后使用调整算法对路径进行调整以缩短回路长度,最后采用遗传算法中的交叉算子,再对路径进行优化。实验结果表明,该算法具有较高精度和较强实用性。     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。     

关于Steiner网络设计问题的近似算法综述

随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视.如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣.著名的最小Steiner网络问题就是这个课题中最为引人关注的问题之一.在过去的十年里,作为可靠网络领域的基础问题之一,Steiner网络设计问题得到很好的研究.我们总结了关于Steiner网络设计问题当前最好的近似算法的近似比与时间复杂度,并简明的概述了这些算法的主要思想.     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向.     

基于进化规划求解Steiner Tree 问题

提出基于进化规划求解Ｓｔｅｉｎｅｒ Ｔｒｅｅ问题的新方法。通过和原有启发式算法的结合提高了进化算法的效率,仿真证明了进化规划算法的有效性。     

关系型数据库向图数据库的转换方法

由于关系型数据库和图数据库存储模式的天然差别,将关系型数据库中的数据转存到图数据库的过程中,需解决对于关系的定义、节点唯一性以及保留原数据库约束信息的主要问题.针对上述问题,提出了一种关系型数据库向图数据库转换的方法.首先通过自定义或使用已有主键,并结合数据库表名的唯一性,解决了节点唯一性的问题;通过不同的配置方案,最大化保留了原关系型数据库的约束信息;然后提出了基于配置与中间表的边定义方法(Edge Definition Method based on Configura-tion and Intermediate Table,EDCIT),针对多种类型的数据库提供不同关系的映射方案,解决了转换过程中对于关系的定义.最终,通过对多个数据集进行实验,并使用Gremlin语句对转换后的数据进行测试,验证了转换后的数据具有完整性和可靠性.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions

We propose algorithmic frameworks based on the iterated local search (ILS) metaheuristic to obtain good‐quality solutions for the Euclidean Steiner tree problem (ESTP) in n dimensions. This problem consists in finding a tree with minimal total length that spans p points given in an n‐dimensional Euclidean space and, eventually, also some additional points whose insertion contributes to reduce the total length of the tree. These ILS approaches make use of both the tree enumeration structure, called topology‐describing vector, and the exact minimization step of a well‐known branch‐and‐bound method for the ESTP. Computational results are provided.     

空间平面图形平等投影图的求解

在分析空间点平等投影的基础上,提出了求解空间平面图形与其平等投影所生成图形之间数学关系的方法,并引出此方法在三维规则图形投影中的扩展应用,然后以空间椭圆为例,论证了投影图与空间椭圆间转换关系,最后在三维openGL环境下,实现了两圆柱体相交的二维投影图。     

迷宫问题转变成图的问题的讨论

迷宫问题在《数据结构》中一般都是作为队列的应用举例，并且迷宫的存储结构以二维数组来存储，表面上似乎迷宫问题是一种特殊问题的解决方法，其实迷宫问题是一种特殊形式图的问题，因此，迷宫总量可转化为图的问题来解决。本文讨论如何将迷宫转化成图，以及如何利用图的算法来解决迷宫问题。     

基于知识图谱的协议转换方法研究

互联网＋政务大数据具有跨领域、多协议、难融合的特点。在大数据采集汇聚过程中,存在多种协议转换的需求,要求网关能够实现统一协议适配转换,为多源异构数据汇聚和数据融合提供数据支撑。传统的协议转换方法通常针对特定的协议转换需求设计的,可扩展性较差,不适用于多种协议转换。该文拟通过研究分析协议报文结构及协议转换特点,提出一种协议转换知识图谱的构建方法。通过构建图谱的模式层以及数据层,建立含有协议报文结构和报文字段映射关系的协议转换知识图谱。并在此基础上提出一种基于知识图谱的协议转换方法,以实现不同协议之间的报文转换。同时,通过协议转换应用实例以及与已有协议转换方法的对比实验,验证了该方法的有效性。     

基于图压缩的最大Steiner连通k核查询处理

研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1～2个数量级.