Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tre...Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.展开更多
In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on t...In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on the select path, an improved MPH-based delay-constrained Steiner tree algorithm is presented in this paper. With the new algorithm a destination node can join the existing multicast tree by selecting the path whose cost is the least;if the path’s delay destroys the delay upper bound, the least-cost path which meets the delay upper bound can be constructed through the least-cost path, and then is used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree can be constructed and the delay upper bound isn’t destroyed. Experimental results through simulations show that the new algorithm is superior to DCMPH_1 algorithm in the performance of spanning tree and the space complexity.展开更多
We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary...We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.展开更多
In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r_(1),r_(2)…,r_(n)}of n te...In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r_(1),r_(2)…,r_(n)}of n terminals in R^(2)and some stock pieces of materials with fixed length L,we are asked to construct a Steiner tree T interconnecting all terminals in X,and each edge in T must be constructed by a part of that stock piece of material.The objective is to minimize the cost of constructing such a Steiner tree T,where the cost includes three components,(1)The cost of Steiner points needed in T;(2)The construction cost of constructing all edges in T and(3)The cost of stock pieces of such materials used to construct all edges in T.We can obtain two main results.(1)Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem,we present a simple 4-approximation algorithm in time O(n log n)to solve this new problem;(2)Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem,we design a 3-approximation algorithm in time O(n^(3))to resolve this new problem.展开更多
A special case of the bottleneck 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 ro...A special case of the bottleneck 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 root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.展开更多
This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design bo...This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.展开更多
In this paper,we study the prize-collecting k-Steiner tree(PCkST) problem.We are given a graph G=(V,E) and an integer k.The graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called termina...In this paper,we study the prize-collecting k-Steiner tree(PCkST) problem.We are given a graph G=(V,E) and an integer k.The graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called terminals are also given.A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in R.Excluding a vertex from the tree incurs a penalty cost,and including an edge in the tree incurs an edge cost.We wish to find a feasible solution with minimum total cost.The total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in F.We present a simple approximation algorithm with the ratio of 5.9672 for the PCkST.This algorithm uses the approximation algorithms for the prize-collecting Steiner tree(PCST) problem and the k-Steiner tree(kST) problem as subroutines.Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.展开更多
Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interc...Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c＋e]while taking risk（c＋e xe）/（c＋e c e）of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p＋v]for its inclusion in T while taking risk（yv p v）/（p＋v p v）of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.展开更多
An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning ...An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning treesproduced by the algorithm are only 0.8% away from the optimal ones.展开更多
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art sol...Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.展开更多
Through careful analysis on the cross-section of sisal fibers, it is found that the middle lamellae between the cell walls have clear geometric characteristics: between the cell walls of three neighboring cells, the m...Through careful analysis on the cross-section of sisal fibers, it is found that the middle lamellae between the cell walls have clear geometric characteristics: between the cell walls of three neighboring cells, the middle lamellae form a three-way junction with 120° symmetry. If the neighboring three-way junctions are connected, a network of Steiner tree with angular symmetry and topological invariability is formed. If more and more Steiner trees are connected, a network of Steiner rings is generated. In another word, idealized cell walls and the middle lamellae are dominated by the Steiner geometry. This geometry not only depicts the geometric symmetry, the topological invariability and minimal property of the middle lamellae, but also controls the mechanics of sisal fibers.展开更多
The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by effici...The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by efficient algorithms up to now.Due to the extensive applications in real world,it is quite important to find some heuristics for it.The stochastic diffusion search algorithm is a newly population-based algorithm whose operating mechanism is quite different from ordinary intelligent algorithms,so this algorithm has its own advantage in solving some optimization problems.This paper has carefully studied the stochastic diffusion search algorithm and designed a cellular automata stochastic diffusion search algorithm for the Euclidean Steiner minimum tree problem which has low time complexity.Practical results show that the proposed algorithm can find approving results in short time even for the large scale size,while exact algorithms need to cost several hours.展开更多
A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree...A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.展开更多
最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求...最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。展开更多
In this paper,Steiner minimal trees for point sets with special structure are studied. These sets consist of zigzag lines and equidistant points lying on them.
基金supported by the National High-Tech R&D Program(863Program)No.2015AA01A705the National Natural Science Foundation of China under Grant No.61202079+1 种基金the China Postdoctoral Science Foundation under Grant No.2014T70031the Fundamental Research Funds for the Central Universities of China No.2015JBM111
文摘Fog Computing is a new platform that can serve mobile devices in the local area. In Fog Computing, the resources need to be shared or cached in the widely deployed Fog clusters. In this paper, we propose a Steiner tree based caching scheme, in which the Fog servers, when caching resources, first produce a Steiner tree to minimize the total path weight(or cost) such that the cost of resource caching using this tree could be minimized. Then we give a running illustration to show how the Fog Computing works and we compare the traditional shortest path scheme with the proposed one. The outcome shows that the Steiner tree based scheme could work more efficiently.
文摘In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on the select path, an improved MPH-based delay-constrained Steiner tree algorithm is presented in this paper. With the new algorithm a destination node can join the existing multicast tree by selecting the path whose cost is the least;if the path’s delay destroys the delay upper bound, the least-cost path which meets the delay upper bound can be constructed through the least-cost path, and then is used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree can be constructed and the delay upper bound isn’t destroyed. Experimental results through simulations show that the new algorithm is superior to DCMPH_1 algorithm in the performance of spanning tree and the space complexity.
基金supported by the National Natural Science Foundation of China(Nos.11861075 and 12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE160006)+2 种基金Key Project of Yunnan Provincial Science and Technology Department and Yunnan University(No.2018FY001014)Program for Innovative Research Team(in Science and Technology)in Universities of Yunnan Province(No.C176240111009)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province.Su-Ding Liu is also supported by the Graduate Research and Innovation Project of Yunnan University(No.2020Z66).
文摘We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.
基金supported by the National Natural Science Foundation of China(Nos.11861075 and 12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE160006)+1 种基金supported by Fundamental Research Funds for the Central Universities(No.buctrc202219)supported by Project of Yunling Scholars Training of Yunnan Province(No.K264202011820).
文摘In this paper,we address the problem of constructing a Steiner tree in the Euclidean plane R^(2)using stock pieces of materials with fixed length,which is modelled as follows.Given a set X={r_(1),r_(2)…,r_(n)}of n terminals in R^(2)and some stock pieces of materials with fixed length L,we are asked to construct a Steiner tree T interconnecting all terminals in X,and each edge in T must be constructed by a part of that stock piece of material.The objective is to minimize the cost of constructing such a Steiner tree T,where the cost includes three components,(1)The cost of Steiner points needed in T;(2)The construction cost of constructing all edges in T and(3)The cost of stock pieces of such materials used to construct all edges in T.We can obtain two main results.(1)Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem,we present a simple 4-approximation algorithm in time O(n log n)to solve this new problem;(2)Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the bin-packing problem,we design a 3-approximation algorithm in time O(n^(3))to resolve this new problem.
文摘A special case of the bottleneck 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 root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.
基金supported by National Natural Science Foundation of China under Grant Nos.71171189,71271204,11101420Knowledge Innovation Program of the Chinese Academy of Sciences under Grant No.KGCX2-RW-329
文摘This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.
基金supported by the National Natural Science Foundation of China (Nos. 12001523,11971046,12131003,and 11871081)the Scientific Research Project of Beijing Municipal Education Commission (No. KM201910005012)Beijing Natural Science Foundation Project (No. Z200002)。
文摘In this paper,we study the prize-collecting k-Steiner tree(PCkST) problem.We are given a graph G=(V,E) and an integer k.The graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called terminals are also given.A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in R.Excluding a vertex from the tree incurs a penalty cost,and including an edge in the tree incurs an edge cost.We wish to find a feasible solution with minimum total cost.The total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in F.We present a simple approximation algorithm with the ratio of 5.9672 for the PCkST.This algorithm uses the approximation algorithms for the prize-collecting Steiner tree(PCST) problem and the k-Steiner tree(kST) problem as subroutines.Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.
基金Supported in part by the National Natural Science Foundation of China under Grant No.11021161 and 10928102973 Program of China under Grant No.2011CB80800+1 种基金Chinese Academy of Sciences under Grant No.kjcx-yw-s7,project grant of"Center for Research and Applications in Plasma Physics and Pulsed Power Technology,PBCT-Chile-ACT 26"Direccio'n de Programas de Investigaci'ón,Universidad de Talca,Chile
文摘Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c＋e]while taking risk（c＋e xe）/（c＋e c e）of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p＋v]for its inclusion in T while taking risk（yv p v）/（p＋v p v）of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.
文摘An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning treesproduced by the algorithm are only 0.8% away from the optimal ones.
文摘Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 10602040, 10872114)
文摘Through careful analysis on the cross-section of sisal fibers, it is found that the middle lamellae between the cell walls have clear geometric characteristics: between the cell walls of three neighboring cells, the middle lamellae form a three-way junction with 120° symmetry. If the neighboring three-way junctions are connected, a network of Steiner tree with angular symmetry and topological invariability is formed. If more and more Steiner trees are connected, a network of Steiner rings is generated. In another word, idealized cell walls and the middle lamellae are dominated by the Steiner geometry. This geometry not only depicts the geometric symmetry, the topological invariability and minimal property of the middle lamellae, but also controls the mechanics of sisal fibers.
基金the National Natural Science Foundation of China (No.70871081)the Science and Technology Department Research Project of Henan Province(No.112102310448)the Natural Science Foundation of Henan University (No.2010YBZR047)
文摘The Euclidean Steiner minimum tree problem is a classical NP-hard combinatorial optimization problem.Because of the intrinsic characteristic of the hard computability,this problem cannot be solved accurately by efficient algorithms up to now.Due to the extensive applications in real world,it is quite important to find some heuristics for it.The stochastic diffusion search algorithm is a newly population-based algorithm whose operating mechanism is quite different from ordinary intelligent algorithms,so this algorithm has its own advantage in solving some optimization problems.This paper has carefully studied the stochastic diffusion search algorithm and designed a cellular automata stochastic diffusion search algorithm for the Euclidean Steiner minimum tree problem which has low time complexity.Practical results show that the proposed algorithm can find approving results in short time even for the large scale size,while exact algorithms need to cost several hours.
基金the National Natural Science Foundation of China (70471065)the Shanghai Leading Academic Discipline Project (T0502).
文摘A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.
文摘最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。
基金Supported by NSF of China(1 970 1 0 2 8) and National973Fundamental Research Project
文摘In this paper,Steiner minimal trees for point sets with special structure are studied. These sets consist of zigzag lines and equidistant points lying on them.
