共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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). 相似文献
3.
Abstract. Let P = {p
1
, p
2
, \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. 相似文献
4.
Abstract. Let P = {p 1 , p 2 , \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. 相似文献
5.
6.
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. 相似文献
7.
8.
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(n2)-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. 相似文献
9.
TSP问题是一个经典的组合优化问题。本文采用基于凸多边形的插入方法来构造路径,然后使用调整算法对路径进行调整以缩短回路长度,最后采用遗传算法中的交叉算子,再对路径进行优化。实验结果表明,该算法具有较高精度和较强实用性。 相似文献
10.
Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。 相似文献
11.
随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视.如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣.著名的最小Steiner网络问题就是这个课题中最为引人关注的问题之一.在过去的十年里,作为可靠网络领域的基础问题之一,Steiner网络设计问题得到很好的研究.我们总结了关于Steiner网络设计问题当前最好的近似算法的近似比与时间复杂度,并简明的概述了这些算法的主要思想. 相似文献
12.
Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向. 相似文献
13.
14.
由于关系型数据库和图数据库存储模式的天然差别,将关系型数据库中的数据转存到图数据库的过程中,需解决对于关系的定义、节点唯一性以及保留原数据库约束信息的主要问题.针对上述问题,提出了一种关系型数据库向图数据库转换的方法.首先通过自定义或使用已有主键,并结合数据库表名的唯一性,解决了节点唯一性的问题;通过不同的配置方案,最大化保留了原关系型数据库的约束信息;然后提出了基于配置与中间表的边定义方法(Edge Definition Method based on Configura-tion and Intermediate Table,EDCIT),针对多种类型的数据库提供不同关系的映射方案,解决了转换过程中对于关系的定义.最终,通过对多个数据集进行实验,并使用Gremlin语句对转换后的数据进行测试,验证了转换后的数据具有完整性和可靠性. 相似文献
15.
Given n points, called terminals, in the plane ℝ2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ2 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 ℝ2, usually, the Euclidean or the L
1 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 2
n time for the L
1 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
2 metric. 相似文献
16.
Vinícius Leal do Forte Flávio Marcelo Tavares Montenegro José André de Moura Brito Nelson Maculan 《International Transactions in Operational Research》2016,23(6):1185-1199
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. 相似文献
17.
18.
迷宫问题转变成图的问题的讨论 总被引:1,自引:0,他引:1
迷宫问题在《数据结构》中一般都是作为队列的应用举例,并且迷宫的存储结构以二维数组来存储,表面上似乎迷宫问题是一种特殊问题的解决方法,其实迷宫问题是一种特殊形式图的问题,因此,迷宫总量可转化为图的问题来解决。本文讨论如何将迷宫转化成图,以及如何利用图的算法来解决迷宫问题。 相似文献
19.
互联网+政务大数据具有跨领域、多协议、难融合的特点。在大数据采集汇聚过程中,存在多种协议转换的需求,要求网关能够实现统一协议适配转换,为多源异构数据汇聚和数据融合提供数据支撑。传统的协议转换方法通常针对特定的协议转换需求设计的,可扩展性较差,不适用于多种协议转换。该文拟通过研究分析协议报文结构及协议转换特点,提出一种协议转换知识图谱的构建方法。通过构建图谱的模式层以及数据层,建立含有协议报文结构和报文字段映射关系的协议转换知识图谱。并在此基础上提出一种基于知识图谱的协议转换方法,以实现不同协议之间的报文转换。同时,通过协议转换应用实例以及与已有协议转换方法的对比实验,验证了该方法的有效性。 相似文献
20.
研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明:压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1~2个数量级. 相似文献