Most Hamiltonian circuit families grow polynomially
DraftStatement (i) A method exists for obtaining a set of optimal 'traveling salesman' routes that is a member of a family that grows no faster than 0(In2)2n. (ii) However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.
Remark 1
We operate on a euclidean plane using nodes (cities) that can be specified with cartesian coordinates. We ignore graphs where all points lie on a line.
We adopt the convention that a route begins and ends at an origin city.
Remark 2
We assume that every road linking two cities is straight. This assumption is justified by the fact that a graph composed of curvilinear roads can be deformed into another one that preserves distances -- provided the roads don't cross outside the cities. This proviso is one of the criteria adopted below.
Proof
(i) Our aim is to show that a pretzel circuit can always be replaced by a shorter simple loop (Hamiltonian circuit).
We begin by showing that route backtrackings and crossings are unnecessary.
It is straightforward that if a route covers the same link twice, a shorter route can be drawn.
Suppose a node p is inside a field of nodes and the route enters p from the left, proceeds to x and then backtracks to p exiting toward the right.
x n p mFor non-trivial cases, there must exist some node m to the immediate right of p and some node n to the immediate left. Since mpx is not straight, it is longer than mx. Hence mxpn is shorter than mpxpn.
Similar reasoning holds if p is outside a field.
We show that a route that intersects at a city can be replaced by a shorter route.
Consider any two two-dimensional fields of n nodes and have them intersect at point p.
[F I E L D 1] m n p q r [F I E L D 2]The optimal route for the new field F1 U F2 will not cross at p because of the option mpq linking F1 and F2 and nr linking the fields, with nr < npr; or because of the option npr and mq.
So then no route drawn on a graph need cross at a city.
We now show that a route that intersects outside a city can be replaced by a shorter route.
We have some field of four nodes.
a d b x cThe route acdba crosses at a non-nodal point we call x. Because bxc is not straight, bxc is longer than bc and hence abxcdxa is longer than abcda.
Now we take another four-node field F2 and attach it to the graph above. But we consider only two-point attachments, as we already know that one-point attachments are not optimal. So it is evident that if F2's route does not intersect x, the composite graph's route is shorter than if the alternative holds. An induction proof can be used for any number of fields, of course.
Now suppose we have a ray segment that holds more than two nodes (ignoring origin) adjacent to another ray with at least two.
a b c O f dHow might we link these rays with an un-loop? Suppose cfdba. We will find that more than one link between two adjacent rays is wasteful. The proof is left for the reader.
Also, we know that backtracking is wasteful and so we would not enter the vertical ray at b. In fact our route enters a ray at top or bottom node and leaves at bottom or top. Intermediate nodes can be ignored.
We will not always require that our rays have more than one non-origin node.
(ii)
Our aim is to show a means of obtaining the set of simple loops on any (non-trivial) field of nodes.
We take a field of n nodes and select any node as origin of a set of rays, with each ray drawn through one or more nodes in the field such that all nodes are intersected by rays.
Now our route must begin at origin and link every ray before returning to origin. At origin, we pick any ray to begin and (b = bottom node, t = top node) our path on that ray is determined: 0bt. However, after that there exists a choice. For ray 2 our path may be bt or tb and likewise for subsequent rays. Now if there are 2 nodes per ray, there are n/2 rays and there are about 2n/2 acceptable paths.
Repeating this procedure for every node in the field, it will be seen that we have established the set of all n-gons, regular or irregular, that can be drawn on the field. Since any route that is not an n-gon is not a simple loop, such a route intersects itself at least once, which we know can be replaced by a shorter circuit.
The set of simple loops would then have an upper limit of n(2n/2), though it is evident that n is much too high since changes of reference frame will slide nodes out of ray alignment and there is no reason to expect that an equal number of new alignments will occur.
Now suppose we have a field with all rays intersecting two nodes. If we add a point to that field but place it on a ray, the ray's interior point drops out and there is no significant change.
This tends to show that though a set of 0 2n may occur, it is very unlikely to occur on the next step. But, at this point, we do not rule out the possibility of a set of fields corresponding to an exponential growth rate 0(In2)2m for m < n.
However, in most cases, a field's upper limit of acceptable routes is given by the number of rays per origin times the number of nodes in the field, or n2(n-1), which gives 3n2 - 2n, or 0n2, as the rate of change.
Remark 3
It seems apparent that a computer program needs to identify the nodes that form edges of the regular or irregular polygons associated with each node as origin and then to measure only edge distances. Hence we can expect that, for a random field of n nodes, the program will very likely, but perhaps not certainly, run efficiently.
Remark 4
It may be that, for some families of loops, a hard rate continues from n through infinity; or that a hard rate alternates with an efficient rate over infinity; or that the hard rate always zeroes out. The third statement would prove that NP=P.
Assuming that for most sets of fields P-time computer programs can be derived from our method, it may be that encypherment experts may wish to consider their options.
No comments:
Post a Comment