Steiner tree method for O (nlogn) under 4-geometry

Steiner tree method for O (nlogn) under 4-geometry

  • CN 1,558,350 A
  • Filed: 01/14/2004
  • Published: 12/29/2004
  • Est. Priority Date: 01/14/2004
  • Status: Active Application
First Claim
Patent Images

1. 4-the steiner tree method of O under the geometry (nlogn) is characterized in that:

  • it is instrument with the computing machine, at first constructs minimum spanning tree under the 4-geometry, and replacing method construct in conjunction with minimum spanning tree and limit again, to go out Steiner be steiner tree;

    Steiner tree method under this 4-geometry specifically is made up of following steps successively;

    (1) the .4-geometry generates the structure of figure, and it is a kind of figure that has comprised minimum spanning tree on one group of point on given plane;

    for the every bit among the figure that we considered is the summit, can be the center with this summit s, and the plane is divided into 8 zones, i.e. R 1-R 8, the outline that the equidistant point set of 4-geometry of all and this summit s is constituted promptly includes the octagonal periphery in described 8 zones;

    Again following operation is carried out on each summit;

    in each region R iIn, only needing to couple together this summit with apart from its nearest summit, the set on resulting limit is just comprising minimum spanning tree, and it contains following steps successively;

    (1.1). the structure vertex set is arranged, and is being the region R at center with this summit so that find for each summit iOther summits that this summit of middle distance is nearest;

    promptly region R iIn all summits according to the non-reduction of discharging row of the distance of certain image point, each in promptly arranging always is less than or equal to item of its back, region R is pressed in the setting of described image point iDecide and appoint;

    (1.2). the scan vertex collection, upgrade the interconnection on vertex set and limit;

    with each summit be the region R that the center is divided iIn, successively from region R 1

    R 4Scan all summits in the above-mentioned vertex set of arranging by nondecreasing sequence, after certain summit p had been scanned, in ensuing scanning process, first appeared at the R of described summit p iSummit in the zone is exactly the R of ordering at described p iThe nearest summit of summit p that the zone middle distance has been scanned, i.e. nearest neighbor point;

    Be scanned for those but also do not find the summit of nearest neighbor point, promptly so-called holding point then is stored in dynamic set A iIn;

    Summit of every scanning is just in the holding point set A iAll be in same R with that summit that should just scan middle searching iHolding point in the zone if having, just links to each other described that summit with the holding point that all these satisfy condition, again all these holding points that satisfy condition from the holding point set A iIn leave out, then described that summit is joined the holding point set A iIn;

    (1.3). all press the R of oneself when all summits 1

    R 4After the zone is scanned, to each R on each summit iThe scanning in zone finishes at this point, and the set on all limits is just comprising our needed minimum spanning tree among the 4-geometry generation figure that obtains thus;

    (2). on the basis of above-mentioned generation figure, use Kruskal method construct minimum spanning tree, and construct corresponding binary tree simultaneously, suitable summit-Bian is prepared against the usefulness that is optimized to joining in the query request;

    (2.1). the limit that generates among the figure is listed as according to the non-reduction of discharging of the length of the length of side;

    (2.2). therefrom select some limits by following Kruskal method and constitute minimum spanning tree;

    the tree T of hypothesis generation earlier limit number at the beginning is zero, again according to non-reduction of discharging row, consider every limit successively, if two end points on the limit of being considered are not communicated with in generating tree T as yet, then this limit will be contained in and generate among the tree T, otherwise, will be excluded, after limits all among the generation figure all is considered, just obtain generating the minimum spanning tree of tree T;

    (2.3). set up the binary tree corresponding with above-mentioned minimum spanning tree;

    A limit ab in the minimum spanning tree, it is end points (a, b) Biao Shi an interior node corresponding to two summits with this limit in the binary tree;

    A summit in the minimum spanning tree is corresponding to a leafy node in the binary tree;

    (3). utilize the minimum common ancestor'"'"'s method of off-line of Tarjan to produce the summit to pairing longest edge, be that summit-Bian is right;

    described longest edge is by the longest one in all limits on a pair of summit in the minimum spanning tree, it also be in the binary tree in the pairing minimum spanning tree of node should in the pairing limit of node, it also can be the longest one in two limits in adjacent two pairing minimum spanning trees of interior node;

    (4). with 4-geometry limit replacement method and obtain the steiner tree of OST-E method construct in conjunction with above-mentioned minimum spanning tree;

    promptly solve and connect the problem of summit-Bian to longest edge in the deletion loop, back, its step is as follows;

    (4.1). seek earlier summit-Bian suitable in minimum spanning tree or the binary tree to after, optimize again;

    every limit in the minimum spanning tree, only consider those minimum spanning trees its summit that links to each other that neutralizes;

    (4.2). right for each summit-Bian, binary tree according to correspondence, find first end points that links to each other with summit described in (4.1) in two end points on described limit, and then find the pairing limit of minimum common ancestor'"'"'s node of this end points and described summit corresponding node in binary tree of having found out, this edge is prepared to delete the loop from described summit to described limit as " limit of pre-deletion ";

    (4.3). more on this basis, prepare " shortest path is connected " carried out with described limit in described summit;

    (4.4). calculate all suitable summit-Bian centerings the summit is connected to the line length value that Bian Suoneng shortens, promptly adopt formula;

    the limit-shortest path of the line length value that can shorten=pre-deletion connects, carry out the non-order that subtracts series arrangement as Optimizing operation (i.e. deletion " limit of pre-deletion " is also carried out " shortest path connection ") according to this " the line length value that can shorten " again, a summit-Bian could delete " limit of pre-deletion " and carry out " shortest path is connected " to realize result'"'"'s improvement with " limit of pre-deletion " having only when limit wherein when existing;

    (5). the step of above-mentioned (1) →

    (4) can repeatedly be carried out, and continues to optimize the gained result;

View all claims

    Thank you for your feedback