Worst Case Greedy Walk

[Andrew Tomazos]

I've reduced down a problem I am having in a project I am working on
to the following...

Given an integer n > 1

Let S(n) be a set of n points in the euclidean unit square:

ie { {x1, y1}, {x2, y2}, ..., {xn, yn} } all xi and yi are real
numbers between 0 and 1 inclusive

such that the total distance of the path traveled by starting at the
first point and moving directly to the nearest unvisited point (until
they have all been visited) is maximized

S(2) is { {0,0}, {1,1} } total distance traveled is sqrt(2), we travel
from {0,0} to {1,1} diagonally across the square.

S(3) is { {0,0}, {0,1}, {1,0} } total distance travelled is 1 +
sqrt(2), we travel up side of square from {0,0} to {0,1} for distance
of 1, then across square to {1,1}

S(4) is { {0,0}, {0,1}, {1,0}, {1,1} } total distance travelled is 3,
we travel up from {0,0} to {0,1} then across to {1,1} then down to
{1,0}

S(5) (I suspect, but am not sure) is { {0.5,0.5}, {0,0}, {0,1}, {1,0},
{1,1} } total distance travelled is 3 + sqrt(0.5)

The goal would be to efficiently compute S(n) for arbitrary n

Is there any way to calculate this set directly in some sort of closed
form, or failing that can you think of a linear algorithm? polynomial?
approximation?

Does this problem reduce to some well-known problem? How?

What approach would you recommend?

Thanks for your time. Any thoughts appreciated.

Regards,
Andrew.

[William Elliot]

On Mon, 31 Oct 2011, Andrew Tomazos wrote:

> I've reduced down a problem I am having in a project I am working on
> to the following...
>
> Given an integer n > 1
>
> Let S(n) be a set of n points in the euclidean unit square:
>
> ie { {x1, y1}, {x2, y2}, ..., {xn, yn} } all xi and yi are real
> numbers between 0 and 1 inclusive
>

No. { a,b } is the set which contains only a and b.
(a,b) is an ordered pair (a first, b second) which is commonly
used for points of the real place writing (a,b) for the point
coordinates a on the x-axis and b on the y axis.

> such that the total distance of the path traveled by starting at the
> first point and moving directly to the nearest unvisited point (until
> they have all been visited) is maximized

That is ambiguous. What if there is more than one "nearest" point?

For example:

{ (0,0), (a,a), (1,1), (0,1), (1,0) } length 1 + 2.sqr 2

{ (0,0), (a,a), (0,1), (1,1), (1,0) } length 2 + sqr 2

> S(2) is { {0,0}, {1,1} } total distance traveled is sqrt(2), we travel
> from {0,0} to {1,1} diagonally across the square.
>
> S(3) is { {0,0}, {0,1}, {1,0} } total distance travelled is 1 +
> sqrt(2), we travel up side of square from {0,0} to {0,1} for distance
> of 1, then across square to {1,1}
>
> S(4) is { {0,0}, {0,1}, {1,0}, {1,1} } total distance travelled is 3,
> we travel up from {0,0} to {0,1} then across to {1,1} then down to
> {1,0}
>
> S(5) (I suspect, but am not sure) is { {0.5,0.5}, {0,0}, {0,1}, {1,0},
> {1,1} } total distance travelled is 3 + sqrt(0.5)
>
> The goal would be to efficiently compute S(n) for arbitrary n
>
> Is there any way to calculate this set directly in some sort of closed
> form, or failing that can you think of a linear algorithm? polynomial?
> approximation?
>
> Does this problem reduce to some well-known problem? How?
>

I'm reminded of the equilibrium configurations of n electrons on a
sphere. Perhaps your problem is similar to the equilibrium
configurations of n electrons confined to a square.

> What approach would you recommend?
>
> Thanks for your time. Any thoughts appreciated.
>

Proper names and derivatives of proper names like "Euclidean"are spelled
with an initial capital letter.

> Regards,
> Andrew.
>

[Chris Uppal]

Andrew Tomazos wrote:

> such that the total distance of the path traveled by starting at the
> first point and moving directly to the nearest unvisited point (until
> they have all been visited) is maximized

I suspect you may have missed something important out of the statement of the
problem. As it stands, I think you can get a path length arbitrarily close to
(n-1) * sqrt(2) for even n, by clustering the points arbitrarily close to (0,0)
and (1,1) such that each step of the traversal crosses the square.

If the positions of the points are fixed by some external constraint (which you
haven't told us) then clearly the optimal algorithm will depend on the details
of those constraints.

-- chris

[James Dow Allen]

On Nov 1, 2:21 pm, "Chris Uppal" <chris.up...@metagnostic.REMOVE-

THIS.org> wrote:
> Andrew Tomazos wrote:
> > such that the total distance of the path traveled by starting at the
> > first point and moving directly to the nearest unvisited point (until
> > they have all been visited) is maximized

That two points might be equally distant doesn't seem an important
objection: with aleph-1 distinct distances to choose from it doesn't
seem "special pleading" to forbid configurations with any equal
distances.

>
> ... As it stands, I think you can get a path length arbitrarily close to

> (n-1) * sqrt(2) for even n, by clustering the points arbitrarily close to (0,0)
> and (1,1) such that each step of the traversal crosses the square.

Did you overlook "NEAREST unvisited point" ?


When doing a fun puzzle like this, one wants to start with the
most "elegant" or "natural" shape. Would surface of a sphere
be better than the interior of a square? Interior of a circle?

James

[Andrew Tomazos]

On Nov 1, 5:24 am, William Elliot <ma...@rdrop.com> wrote:
>> such that the total distance of the path traveled by starting at the
>> first point and moving directly to the nearest unvisited point (until
>> they have all been visited) is maximized
>
> That is ambiguous.  What if there is more than one "nearest" point?

Ok, in that case the algorithm can choose. More formally make the set
of n points an n-tuple of points, and in the case of two or more
nearest unvisited points than the earlier one in the list is visited.
-Andrew.

[Andrew Tomazos]

On Nov 1, 8:21 am, "Chris Uppal" <chris.up...@metagnostic.REMOVE-

THIS.org> wrote:
> Andrew Tomazos wrote:
> > such that the total distance of the path traveled by starting at the
> > first point and moving directly to the nearest unvisited point (until
> > they have all been visited) is maximized
>
> I suspect you may have missed something important out of the statement of the
> problem.  As it stands, I think you can get a path length arbitrarily close to
> (n-1) * sqrt(2) for even n, by clustering the points arbitrarily close to (0,0)
> and (1,1) such that each step of the traversal crosses the square.

The points are not visited in the set order, they are visited "nearest
first" order.

In your example the walk would :
1) wander an arbitrarily small distance visiting the points clustered
at (0,0)
2) then jump sqrt(2) to near (1,1)
3) then walk another arbitrarily small distance around the points near
(1,1)

for a total of sqrt(2) + small distance traveled.
-Andrew.

[Andrew Tomazos]

On Nov 1, 8:45 am, James Dow Allen <jdallen2...@yahoo.com> wrote:
> When doing a fun puzzle like this, one wants to start with the
> most "elegant" or "natural" shape.  Would surface of a sphere
> be better than the interior of a square?  Interior of a circle?

If you have a solution over any convex set of any metric space, it
will most likely be helpful.
-Andrew.

[mike fee]

In article <68cedc9e-e144-42fb-957c-d5c93899c283
@s30g2000yqd.googlegroups.com>, and...@tomazos.com says...

I would hazard a guess (without proof at this stage) that for n^2
points, the best distribution will be to arrange them in a regular nxn
grid, with length n + 1, and of course for any large n the limiting path
length will be a tiny bit more than sqrt(n).

One point - the solution is different for the two situations:
a) identify a first point and then find the nearest-neighbour shortest
path to the otrher n-1 points.
b) find the shortest nearest neighbour path between n points.

Is situation b) to far from what you want to solve to be useful, as I
think it has mor eregularities than situation a)?

Mike

[Graham Cooper]

a (square) spiral


Herc

[Graham Cooper]

...that deforms into a circular spiral as you zoom in!

the end point complicates the traversal it will slide towards (0.5,
0.5)

Difficult problem to optimise though, each point would have to be
optimised w.r.t. every other point after n > 5. But the square spiral
approximation would be simple.

The number of points along each side might be optimal at p>2,
say you draw a midpoint *p=3

1--2--3
-
9- -
- 4
8 -
- -
7-6-5


then you can wind the spiral arcs closer together resulting in longer
segments overall.

e.g.
8-9 < 1-9



Herc

[Steve Thompson]

Too obvious? What about triangles?





Steve Thompson

[William Elliot]

You're clipping the essential problem statement which will
sooner or later result in vague and useless replies.

Please include essential content _within_ your reply. See
http://oakroadsystems.com/genl/unice.htm

When maximizing S(n) am I allowed both the choice of positions
and of order? I'd think so, if I recall the problem correctly.

[quasi]

In this subthread, I'll pose a few other "greedy-walk" type
problems relating to the Traveling Salesman Problem (TSP).
While I know very little about TSP, I suspect that problems
along the lines of the ones I pose below are likely to have
been studied, and if so, a reference would be of interest.

I'll pose 3 problems ...

Given a set S of n points in the plane, n > 2, with all
distinct pairwise distances (each point has a unique nearest
neighbor).

By a "full cycle on S" we mean a closed path which starts
at a vertex of S, visits all other points of S exactly once,
and then returns to the starting point.

Two full cycles on S will be considered the same if and only
if they have the same starting point and visit the same points
in the same order. By this version of "sameness", there are
exactly n! full cycles on S.

By the length of a full cycle on S we mean the sum of the
n distances from each point to the next point in the cycle.

Problem (1): Of all the full cycles on S, how many distinct
total distances are possible?

Since for each full cycle, there are 2n full cycles (including
the original one) with the same total distance (obtained by
simply changing the starting point or the direction of travel),
the full cycles on S yield at most ((n-1)!)/2 distinct total
distances. Perhaps this crude upper bound can always actually
be achieved?

Next ...

By a "greedy full cycle on S" we mean a full cycle on S such
that each of the n-1 points visited before the final return
is chosen "greedily", that is, from a given point in the
cycle, the next point to be visited is the closest yet
unvisited point of S other than the starting point, unless
there are no such points, in which case, the final visit
is a return to the starting point.

Thus, there are exactly n greedy full cycles on S.

Problem (2): Of the greedy full cycles on S, can there be
n distinct total lengths? If not, at most how many distinct
total lengths are possible?

Finally ...

Let

m(S) = the least total length of a full cycle on S.

a(S) = the least total length of a greedy full cycle on S.

b(S) = the greatest total length of a greedy full cycle on S.

Obviously, m(S) <= a(S) <= b(S).

Problem (3): Over all sets S, what are the maximum possible
values, as a function of n, of the ratios

b(S)/a(S)

b(S)/m(S)

a(S)/m(S)

??

quasi

[INFINITY POWER]

On Nov 1, 1:11 am, Andrew Tomazos <and...@tomazos.com> wrote:

> I've reduced down a problem I am having in a project I am working on
> to the following...
>
> Given an integer n > 1
>
> Let S(n) be a set of n points in the euclidean unit square:
>
> ie { {x1, y1}, {x2, y2}, ..., {xn, yn} } all xi and yi are real
> numbers between 0 and 1 inclusive
>
> such that the total distance of the path traveled by starting at the
> first point and moving directly to the nearest unvisited point (until
> they have all been visited) is maximized
>
> S(2) is { {0,0}, {1,1} } total distance traveled is sqrt(2), we travel
> from {0,0} to {1,1} diagonally across the square.

RIGHT! My simulator got 1.39

>
> S(3) is { {0,0}, {0,1}, {1,0} } total distance travelled is 1 +
> sqrt(2), we travel up side of square from {0,0} to {0,1} for distance
> of 1, then across square to {1,1}

RIGHT! I got about 2.3

>
> S(4) is { {0,0}, {0,1}, {1,0}, {1,1} } total distance travelled is 3,
> we travel up from {0,0} to {0,1} then across to {1,1} then down to
> {1,0}

RIGHT! I got 2.9

>
> S(5) (I suspect, but am not sure) is { {0.5,0.5}, {0,0}, {0,1}, {1,0},
> {1,1} } total distance travelled is 3 + sqrt(0.5)
>

NOPE! It can do slightly better about 3.82

It forms an arrow!

(0,0) (0.6, 0.6) (1,1) (0,1) (1,0)

1.41 + 1 + 1.41


I got a crude simulator working!

http://freewebs.com/namesort/matheology/spiral6.html


I'll have to simulate anneal it to get a nice spiral output!

[Chris Uppal]

Andrew Tomazos wrote:

> > [me]

> > I suspect you may have missed something important out of the statement
> > of the problem. As it stands, I think you can get a path length
> > arbitrarily close to (n-1) * sqrt(2) for even n, by clustering the
> > points arbitrarily close to (0,0) and (1,1) such that each step of the
> > traversal crosses the square.
>
> The points are not visited in the set order, they are visited "nearest
> first" order.

Ah, I see. My mistake. BTW, are the endpoints fixed in advance ? Is it OK to
start and finish inside the square rather than at opposite corners, as in your
examples ?

Interesting, but I can't think of anything clever -- I'd be inclined to try the
simulation approach the INFINITY POWER has mentioned, and see what /kinds/ of
shapes crop up.

On the other hand, it might be worth thinking of it the other way around.
Start by packing a "long" path into the unit square, and then asking how /few/
points you can distribute along it such that neareast-unvisited-neghbour
constraint forces traversal of that path. Makes me wonder if a Hilbert curve,
or other connected space-filling curve, might be fruitful (although I have no
communicable reason to expect a space-filling curve to be better than just a
zig-zag pattern, or similar).

-- chirs

[Patricia Shanahan]

On 11/2/2011 1:16 AM, Chris Uppal wrote:
...

> On the other hand, it might be worth thinking of it the other way around.
> Start by packing a "long" path into the unit square, and then asking how /few/
> points you can distribute along it such that neareast-unvisited-neghbour
> constraint forces traversal of that path. Makes me wonder if a Hilbert curve,
> or other connected space-filling curve, might be fruitful (although I have no
> communicable reason to expect a space-filling curve to be better than just a
> zig-zag pattern, or similar).

I was also thinking along the line of packing a path. The problem is
that there are several ways to do it, including zig-zag and spiral.

Each general approach leads to a family of solutions with parameters
that select a specific solution within the family. The permitted and
optimal parameter settings within a solution family depend on the number
of points. Picking that solution within family is, in general, an
integer optimization problem.

My best suggestion for tackling this problem is to start with some
simple solution families, and determine the best solution in each
family. It may be possible to show that one family is always better than
another e.g. if the number of points is greater than N.

I don't see an obvious way to prove that a solution is overall optimal,
because there may be another family that has not yet been proposed that
contains a better solution.

Patricia

[mike fee]

In article <MPG.291b24605...@news.eternal-september.org>,
m....@irl.nospam.cri.nz says...

I take some of that back. Firstly, for a mxm grid of points the path
length is m not m + 1, but for smaller numbers of points it is
significantly less than optimal.

The suggested spiral looks good for moderately small n: for 9 points I
can get D to limit to 5.1868888668 by placing the outer 4 points on the
corners of the square, the next 4 points on a square oriented at 45
degrees to the main square and cenered therein, and one point (the
starting point) in the centre. The smaller square has sides of length
sqrt(2)/(1 + sqrt(3)), which makes it just big enough that if you draw
an equilateral triangle with base along one of th esides of the smaller
square, the third point of the triangle is coincident with one of the
corners of the big square.

D = 3 + (6 + sqrt(2))p + q
p = 1/(sqrt(2)(1 + sqrt(3)))
q = sqrt(1/2 - sqrt(2)p + 2P^2)

By nesting a set of smaller and smaller scaled squares (each rotated 45
degrees from the larger one) I can get a limit for n = 4m + 1 points as
follows.

D(4m + 1) (m = 1,2...) = 3*Sum(i=0, i=m-1, k^i) + k^i*(1/sqrt(2) + k)
where k = sqrt(2)/(1 + sqrt(3)).

This looks fairly good for small n
D(5) = 3.707
D(9) = 5.187
D(13) = 5.685
D(17) = 5.943

But as n ;imits to infinity, this limits to 3*Sum(i=0, i=inf, u^i) so
lim n -> inf D(n) = 3/(1-k) = 3(1 + sqrt(3))/(1 - sqrt(2) + sqrt(3)) =
6.2194...

so by n = 49 = 4*12 + 1 = 7*7, the rectangular grid solution I proposed
earlier with D ~ 7, so D ~= sqrt(n) is still the best I can come up with
for large n.

--Mike

[quasi]

On Wed, 02 Nov 2011 01:55:06 -0500, quasi <qu...@null.set> wrote:

>In this subthread, I'll pose a few other "greedy-walk" type
>problems relating to the Traveling Salesman Problem (TSP).
>While I know very little about TSP, I suspect that problems
>along the lines of the ones I pose below are likely to have
>been studied, and if so, a reference would be of interest.
>
>I'll pose 3 problems ...
>
>Given a set S of n points in the plane, n > 2, with all
>distinct pairwise distances (each point has a unique nearest
>neighbor).

What if we change R^2 to R^k, for some fixed positive integer
k < n?

Alternatively, we can allow S to be an arbitrary n-point
metric space, not necessarily embeddable in R^(n-1).

Also, we might consider removing the requirement that the
distances are distinct. Of course, then we will get more
than n distinct greedy full cycles.

Let's consider two special case of Problem (3) above ...

First, suppose k = 1. In other words, the n points are
on the real line. Also, relax the restriction on distinct
distances. With these conditions, I think the following
claim holds:

b(S)/m(S) < 4/3 for all n.

The maximum possible value of
b(S)/m(S) -> 4/3 as n -> oo.

Next, fix n = 4, but again relax the restriction on distinct
distances. For k = 1,2,3 what are the maximum possible values
for b(S)/m(S)? What if S is an arbitrary 4-point metric space,
not necessarily embeddable in R^3?

quasi

[INFINITY POWER]

On Nov 3, 7:55 am, mike fee <m....@irl.nospam.cri.nz> wrote:
>
> The suggested spiral looks good for moderately small n: for 9 points I
> can get D to limit to 5.1868888668 by placing the outer 4 points on the
> corners of the square, the next 4 points on a square oriented at 45
> degrees to the main square and cenered therein, and one point (the
> starting point) in the centre.

The 45 degree inner square is the solution for 8 points.

Adding the inner point changes the ordering,

so 9 points is a tic tac toe grid.

9 3-4
| | |
1-2 5
| |
8-7-6

4.5

[mike fee]

In article <j8skbl$f86$1...@dont-email.me>, infi...@limited.com says...

> On Nov 3, 7:55 am, mike fee <m....@irl.nospam.cri.nz> wrote:
> >
> > The suggested spiral looks good for moderately small n: for 9 points I
> > can get D to limit to 5.1868888668 by placing the outer 4 points on the
> > corners of the square, the next 4 points on a square oriented at 45
> > degrees to the main square and cenered therein, and one point (the
> > starting point) in the centre.
>
> The 45 degree inner square is the solution for 8 points.

I have now found a better solution for 8 points with length 5.49457530507706
Points (in order are):
0 0.500000000000212 0.0620125868347103
1 0.749480003012391 0.499740000898155
2 0.500000000000118 0.999999998784209
3 1 0.999999694281932
4 0.134064321353551 0.499849922867556
5 0 1.30257475757742E-13
6 0 1
7 1 6.5650916142215E-14
which is significantly different in shape to my earlier proposed 45
degree inner square.

>
> Adding the inner point changes the ordering,
>
> so 9 points is a tic tac toe grid.
>
> 9 3-4
> | | |
> 1-2 5
> | |
> 8-7-6
>
> 4.5

The Best solution I can get for 9 points is length 5.84847524115759
Points in order:
0 0.498914751824775 0.503500406346059
1 0.499999999999895 0.868358201455564
2 0.863765096747505 0.500928592534846
3 0.500000000000176 0.133087359118337
4 1 4.46505279805424E-14
5 0.133997871619142 0.500004096241968
6 0 1
7 1 1
e

This is more like the 45 degree centre circle with n extra point in the
middle, but the path jumps back and fourth between inner and outer
points.

I have used annealing to solve and, although I haven't had a lookj in
detail at solutions, a small change in length can be the result of a
very large change in positions of points and path-shape. Looks like th
solution space in 2n dimensions gets complicated for n larger than 4-5.
Even for small n, the solution isn't usually the obvious one. For
example, for 4 points I was certain it would be 00, 01, 11, 10 with a
length of 3, but you can do far better with 00, (k,k), 10, 01
wher ek is a tad less than 1/sqrt(2)... this had length 3.1795+

>
> I got a crude simulator working!
> http://freewebs.com/namesort/matheology/spiral6.html
>

Mike

[INFINITY POWER]

On Nov 7, 2:09 pm, mike fee <m....@irl.nospam.cri.nz> wrote:
> In article <j8skbl$f8...@dont-email.me>, infin...@limited.com says...

Mike, those paths jump to next points a lot further than the 'closest
unvisited point'.

e.g. for your 8 points traversal

0-5 = 0.5
0-7 = 0.5
0-1 > 0.5 *next point should be closest point

3-6 = 1
3-4 > 1 *next point should be closest point


The algorithm just to test a solution is cubic complexity O(n^3)

For all starting points 0
For all remaining points m
For all remaining points n
Find next shortest path: n to n+1

My sim is only O(n^2) as I just use the 1 fixed starting point which is less
than optimal with a random search as n approaches double digits, though the
starting point tends towards the center, since the best solutions always
have a final large 'criss cross' on the last few points.

Herc

[mike fee]

In article <j996jq$obp$1...@dont-email.me>, infi...@limited.com says...

> On Nov 7, 2:09 pm, mike fee <m....@irl.nospam.cri.nz> wrote:

> > I have now found a better solution for 8 points with length
> > 5.49457530507706
> > Points (in order are):
> > 0 0.500000000000212 0.0620125868347103
> > 1 0.749480003012391 0.499740000898155
> > 2 0.500000000000118 0.999999998784209
> > 3 1 0.999999694281932
> > 4 0.134064321353551 0.499849922867556
> > 5 0 1.30257475757742E-13
> > 6 0 1
> > 7 1 6.5650916142215E-14
> > which is significantly different in shape to my earlier proposed 45
> > degree inner square.
> >
>

> Mike, those paths jump to next points a lot further than the 'closest
> unvisited point'.
>
> e.g. for your 8 points traversal
>
> 0-5 = 0.5
> 0-7 = 0.5
> 0-1 > 0.5 *next point should be closest point

I get all of 0-1, 0-5, and 0-7 to be approximately 0.50383...
to 5 decimal places (on the crappy calculator on my desk), so at worst
0-1 is not jumping "a lot" further than 0-5, or 0-7. In the limiting
solutions, the nearest neighbour is often only infinitesmally closer
than the next nearest, so I may have a few round off errors in some
solutions, but I still believe my solutions are 'approximately' valid.

I will re-check with extended floats to see if it makes a significant
difference.

Mike

[mike fee]

In article <j996jq$obp$1...@dont-email.me>, infi...@limited.com says...

> On Nov 7, 2:09 pm, mike fee <m....@irl.nospam.cri.nz> wrote:
> >
> > I have used annealing to solve and, although I haven't had a lookj in
> > detail at solutions, a small change in length can be the result of a
> > very large change in positions of points and path-shape. Looks like th
> > solution space in 2n dimensions gets complicated for n larger than 4-5.
> > Even for small n, the solution isn't usually the obvious one. For
> > example, for 4 points I was certain it would be 00, 01, 11, 10 with a
> > length of 3, but you can do far better with 00, (k,k), 10, 01
> > wher ek is a tad less than 1/sqrt(2)... this had length 3.1795+
> >

> The algorithm just to test a solution is cubic complexity O(n^3)
>
> For all starting points 0
> For all remaining points m
> For all remaining points n
> Find next shortest path: n to n+1
>
> My sim is only O(n^2) as I just use the 1 fixed starting point which is less
> than optimal with a random search as n approaches double digits, though the
> starting point tends towards the center, since the best solutions always
> have a final large 'criss cross' on the last few points.
>

New best solutions for n = 1 to 9

1 0
2 1.4142135623731
3 2.4142135623731
4 3.17958042710326
5 3.93185165257809
6 4.50920192176745
7 5.01119231481624
8 5.49475975594929
9 5.84911191941696

For n=8 the solution I reached was

0 0.0624999978186131 0.499999999999983
1 0.499999998836468 0.250000002327221
2 0.999999999999452 0.499999999999788
3 0.999999999999789 0
4 0.499999999999729 0.866025403783882
5 0 0.99999999999996
6 0 4.88110995602417E-14
7 1

with nearesr neighbour distances (Pi-Pj) (i=0...6,j=i+1...7) of

0.503891108997772 0.937500002180839 1.06250000192456 0.570421640651583
0.503891108998069 0.503891108998026 1.06250000192476
0.559016994374292 0.559016996456218 0.616025401456662 0.901387816284188
0.559016994374996 0.901387817575044
0.499999999999788 0.619656837463311 1.11803398874948 1.11803398874929
0.500000000000212
0.999999999999548 1.41421356237292 0.999999999999789 1
0.517638090204914 0.999999999999341 0.517638090205447
0.999999999999911 1
1.41421356237306

Herc, note that in each step the i-i+1 step is the shortest.

Mike

[mike fee]

In article <MPG.292326795...@news.eternal-september.org>,
m....@irl.nospam.cri.nz says...

>
> For n=8 the solution I reached was
>
> 0 0.0624999978186131 0.499999999999983
> 1 0.499999998836468 0.250000002327221
> 2 0.999999999999452 0.499999999999788
> 3 0.999999999999789 0
> 4 0.499999999999729 0.866025403783882
> 5 0 0.99999999999996
> 6 0 4.88110995602417E-14

> 7 1 1
>
So the most nominally exact solution (where the path can choose which of
two equally distant nearest neighbours to go to next) that I can find
for n=8 would be:

0 (1/16,1/2)
1 (1/2,1/4)
2 (1,1/2)
3 (1,0)
4 (1/2,sqrt(3)/2)
5 (0,1)
6 (0,0)
7 (1,1)

with path length Sqrt(65)/16 + sqrt(5)/4 + 1/2 + 1 + sqrt(2-sqrt(3)) + 1
+ sqrt(2) = 5.494759756

cheers,
Mike

[Robert Maas, http://tinyurl.com/uh3t]

> From: mike fee <m....@irl.nospam.cri.nz>

> I get all of 0-1, 0-5, and 0-7 to be approximately 0.50383...
> to 5 decimal places (on the crappy calculator on my desk), so at worst
> 0-1 is not jumping "a lot" further than 0-5, or 0-7. In the limiting
> solutions, the nearest neighbour is often only infinitesmally closer
> than the next nearest, so I may have a few round off errors in some
> solutions, but I still believe my solutions are 'approximately' valid.
> I will re-check with extended floats to see if it makes a significant
> difference.

That's a dumb way to do this kind of problem. Since the rational
numbers are dense in the real numbers, for this problem it suffices
to find rational-coordinate solutions. In fact the specific values
you are testing are exact rationals, for example
0.499849922867556 = 499849922867556/1000000000000000
Given that all coordinates are rational, you can use exact rational
arithmetic to exactly compute square of distance between any two
points, then directly compare square-of-distance to find smallest
such (from last-visited point to unvisited points). No need to
*approximately* compute square-roots at all when verifying that
somebody has indeed correcty selected the nearest unvisited point.

Of course you should use either Common Lisp or some other language
which has exact rational arithmetic built-in, or use some add-on
exact-rational-arithmetic library if you can find one.

The only place you'd need to compute *approximate* square root is
when computing the total path length, and in that case you should
use interval arithmetic instead of shot-in-dark floating-point, to
make sure that your printout doesn't lie about the low-order digit,
and also to compare two different sets of points to verify that one
really does yield a longer path length. If interval arithmetic with
a particular computational precision doesn't show that one set of
points is definitely longer than another, i.e. the error-intervals
overlap, then you know to recompute with better precision, until
the error-intervals no longer overlap.

Suggestion: Continued fractions are a good way to compute
square-root of rational to arbitrary precision, with each iteration
yielding an interval with exact-rational endpoints, thus making it
relatively easy to add up the intervals for the segments within the
path using exact rational arithmetic, as well as comparing the
error-contributions from each segment to see which is contributing
the largest error-interval hence which needs to be iterated one
more continued-fraction step to most effectively shrink the total
error-interval.

Google-groups-search-key: imtrgfdi

[INFINITY POWER]

LOL! have you ever used this approach to "defeat rounding error"?

You might find you need unbounded length (infinitely big) integer
coefficients for rationals to be more precise than rounded reals.

Mike's solutions are all wrong anyway, his next closest point is not closest
at all as I explained.

He basically travels along the hypotenuse ignoring the 2 closer side points,
but he ignored me pointing this out so his solutions are still way too
large.

I added a temperature to the annealing javascript program. But I didn't
finish the outer loop to test all starting points, Point 1, as I suspect
solutions over 15 points would take a chunk of computer time in a compiled
language.





NEW VERSION

http://freewebs.com/namesort/matheology/LONGEST-WALK-CENTER.html


<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<TITLE>Longest Walk Inside a Unit Square</TITLE>
</HEAD>
<BODY bgcolor="#000000" text="#FFFFFF" link="#FFFFFF" vlink="#FFFFFF">


<b>LENGTH: </b><b id="lenseg"></b><br>

<b>POINTS: </b>
<select onchange="points = this.options[this.selectedIndex].value;init()">
<option value=2>2</option>
<option value=3>3</option>
<option value=4>4</option>
<option value=5>5</option>
<option value=6>6</option>
<option value=7>7</option>
<option value=8>8</option>
<option value=9>9</option>
<option value=10>10</option>
<option value=12>12</option>
<option value=16>16</option>
<option value=20>20</option>
<option value=25>25</option>
<option value=30>30</option>
<option value=40>40</option>
<option value=50>50</option>
<option value=75>75</option>
<option value=100>100</option>
</select>

<br>
<b>TEMP: </b>
<select onchange="temp = this.options[this.selectedIndex].value;">
<option value=100000>1000</option>
<option value=100 selected=true>100</option>
<option value=20>20</option>
<option value=10>10</option>
<option value=5>5</option>
<option value=2>2</option>
<option value=1>1</option>
<option value=0>0</option>
</select>




<SCRIPT LANGUAGE="JavaScript">
if (document.getElementById){


// Plenty of black gives a better sparkle effect.

showerCol=new
Array('#000000','#ff0000','#ffffff','#000000','#00ff00','#ff00ff','#ffffff','#ffa500','#000000','#fff000');
launchCol=new Array('#ffff00','#ff00ff','#00ffff','#ffffff','#ff8000');
runSpeed=10; //setTimeout speed.

// *** DO NOT EDIT BELOW ***




steps = 1000
points = 101

spiralx=new Array()
spiraly=new Array()

newx = new Array()
newy = new Array()

sortx = new Array()
sorty = new Array()

sorted = new Array()

lengthspiral = 0

temp = 100

var yPos=200;
var xPos=200;
var explosionSize=200;
var launchColour='#ffff80';
var timer=null;
var dims=1;
var evn=360/14;
firework=new Array();
var ieType=(typeof window.innerWidth != 'number');
var ieRef=((ieType) && (document.compatMode) &&
(document.compatMode.indexOf("CSS") != -1))
?document.documentElement:document.body;
thisStep=0;
step=1;


function init() {
for (i=0; i < 101; i++){
spiralx[i] = 0
spiraly[i] = 0
newx[i] = 0
newy[i] = 0

firework[i].top = -100 +"px";
firework[i].left = -100 +"px";
}

lengthspiral = -1
}



for (i=0; i < points; i++){
document.write('<div id="sparks'+i+'"
style="position:absolute;top:0px;left:0px;height:8px;width:8px;font-size:8px;color:#000000;background-color:'+launchColour+'">&nbsp;<b>'+(i+1)+'</b><\/div>');
firework[i]=document.getElementById("sparks"+i).style;
}

document.write('<div id="topl"
style="position:absolute;top:100px;left:300px;height:1px;width:1px;font-size:1px;color:#000000;background-color:#FFFF00"><\/div>');
document.write('<div id="topr"
style="position:absolute;top:100px;left:507px;height:1px;width:1px;font-size:1px;color:#000000;background-color:#FFFF00"><\/div>');
document.write('<div id="botl"
style="position:absolute;top:309px;left:300px;height:1px;width:1px;font-size:1px;color:#000000;background-color:#FFFF00"><\/div>');
document.write('<div id="botr"
style="position:absolute;top:309px;left:507px;height:1px;width:1px;font-size:1px;color:#000000;background-color:#FFFF00"><\/div>');




function winDims(){
winH=(ieType)?ieRef.clientHeight:window.innerHeight;
winW=(ieType)?ieRef.clientWidth:window.innerWidth;
bestFit=(winW >= winH)?winH:winW;
}
winDims();
window.onresize=new Function("winDims()");










function Fireworks(){

oldl = lengthspiral
lengthspiral = 0
lengthsp = 0

for (i=0; i < points; i++){


newx[i] = spiralx[i] + Math.round(Math.random()*4)-2;
newy[i] = spiraly[i] + Math.round(Math.random()*4)-2;

if (newx[i] > 100) { newx[i] = 100 }
if (newx[i] < -100) { newx[i] = -100 }
if (newy[i] > 100) { newy[i] = 100 }
if (newy[i] < -100) { newy[i] = -100 }

sorted[i] = false

}


nextp = 0
sortx[0] = newx[nextp]
sorty[0] = newy[nextp]
sorted[0] = true

for (i=1; i < points; i++){

curp = nextp
smallest = 10000000
small2 = 1


for (j=1; j < points; j++) {
if (!sorted[j]) {
base = newx[j] - newx[curp]
hite = newy[j] - newy[curp]
lengthseg = Math.pow(base*base + hite*hite, 0.48)
lengthseg2 = Math.pow(base*base + hite*hite, 0.5)
if (lengthseg < smallest) {
smallest = lengthseg
nextp = j
small2 = lengthseg2
}
}
}
sortx[i] = newx[nextp]
sorty[i] = newy[nextp]
sorted[nextp] = true

lengthspiral+= smallest
lengthsp+= small2
}




keep = false

if (lengthspiral > oldl) {
keep = true
document.getElementById("lenseg").innerHTML = parseInt(lengthsp) / 200

lengthspiral = lengthspiral - temp*Math.sqrt(points)/200

}
else {
lengthspiral = oldl - temp*Math.sqrt(points)/200
}




if (keep) {

for (i=0; i < points; i++){


spiralx[i] = sortx[i]
spiraly[i] = sorty[i]


firework[i].top = 200 + spiralx[i] + "px";
firework[i].left = 400 + spiraly[i] +"px";
}
}



thisStep+=step;
timer=setTimeout("Fireworks()",runSpeed);


}


window.onload=doFireworks;
}


function doFireworks(){
init()
points = 2
Fireworks()
}



//-->
</SCRIPT>
</body></HTML>



You just need to add another outer loop to test all starting points instead
of always measuring from Point 1.

That would make it a cubic algorithm per arrangement, which is getting slow
in Javascript!

--
http://MATHEOLOGY.com

[Robert Maas, http://tinyurl.com/uh3t]

> From: "INFINITY POWER" <infin...@limited.com>
> > ... Since the rational

> > numbers are dense in the real numbers, for this problem it suffices
> > to find rational-coordinate solutions. In fact the specific values
> > you are testing are exact rationals, for example
> > 0.499849922867556 = 499849922867556/1000000000000000
> > Given that all coordinates are rational, you can use exact rational
> > arithmetic to exactly compute square of distance between any two
> > points, then directly compare square-of-distance to find smallest
> > such (from last-visited point to unvisited points). No need to
> > *approximately* compute square-roots at all when verifying that
> > somebody has indeed correcty selected the nearest unvisited point.
> >
> > Of course you should use either Common Lisp or some other language
> > which has exact rational arithmetic built-in, or use some add-on
> > exact-rational-arithmetic library if you can find one.

I take it "INFINITY POWER" has no quibble with using exact
rationals to *check* the solution the other person proposed to
verify it at least satisfies the premises that the points were
sequenced per the rule that the closest unused point is always
selected next?

> > The only place you'd need to compute *approximate* square root is
> > when computing the total path length, and in that case you should
> > use interval arithmetic instead of shot-in-dark floating-point, to
> > make sure that your printout doesn't lie about the low-order digit,
> > and also to compare two different sets of points to verify that one
> > really does yield a longer path length. If interval arithmetic with
> > a particular computational precision doesn't show that one set of
> > points is definitely longer than another, i.e. the error-intervals
> > overlap, then you know to recompute with better precision, until
> > the error-intervals no longer overlap.
> >
> > Suggestion: Continued fractions are a good way to compute
> > square-root of rational to arbitrary precision, with each iteration
> > yielding an interval with exact-rational endpoints, thus making it
> > relatively easy to add up the intervals for the segments within the
> > path using exact rational arithmetic, as well as comparing the
> > error-contributions from each segment to see which is contributing
> > the largest error-interval hence which needs to be iterated one
> > more continued-fraction step to most effectively shrink the total
> > error-interval.

> LOL! have you ever used this approach to "defeat rounding error"?

In 2004 I started writing software to use rational interval
arithmetic, and created a set of printouts of various test runs.
Then I posted links to these printouts. But nobody ever showed any
interest. If you want to be the first to take a look:
http://www.rawbw.com/~rem/IntAri

> You might find you need unbounded length (infinitely big) integer
> coefficients for rationals to be more precise than rounded reals.

The method is to use a small precision to see whether two intervals
overlap or are distinct. If distinct, you are done already. If they
overlap, increase precision and recompute, thus narrowing each
interval, and check whether they still overlap or are now distinct.
Thus you have no a priori bound on precision, but you never use
much more precision that is absolutely needed to get a definitive
answer.

One problem: If you are computing exactly the same mathematical
value by two different methods, no matter how accurately you
compute the two values in parallel, the intervals will *always*
overlap, and thus the loop of trying again with more precision will
never terminate.

So you need some sort of heuristic that pauses the loop after a
while to see if maybe you can mathematicall prove the two methods
are in fact computing the exact same value. Ideally you timeshare
two processes, one of which increases precision to prove by direct
calculation that the two values are different, and one which tries
to prove mathematically that the two values are identical.
Unfortunately Goedel proved that there are some mathematical
questions that are true but unprovable. Fortunately for the problem
at hand, sums of square roots that are EQUAL are in fact PROVABLY
EQUAL. (At least I am pretty sure I read that was true. Rebuttal?)

> Mike's solutions are all wrong anyway, his next closest point is
> not closest at all as I explained.

Simply using exact rational calculations, no interval arithmetic
needed, no repeated calculations with increasing precision, just
using his exact decimal values as exact rational values (numerator
over power of ten), would directly show if he followed the rules or
not, no doubt either way in the result.

> I added a temperature to the annealing javascript program.

Note that you need only exact rational numbers as coordinates in
such a program. Given that fact, you can verify that your trial
paths follow the rules, and then use a fixed precision of interval
arithmetic when computing the sum of segment lengths. If intervals
don't overlap, you know one path is definitely better than the
other. If they do overlap, you have to retain both as possibly best
solutions for the moment, until you improve the fixed precision to
make the intervals no longer overlap. When you have more than two
possibly-best solutions, i.e. A overlaps B, and B overlaps C, it
might be that A doesn't overlap C, so that A or C can be
eliminated, leaving 2 instead of 3 possibly-best paths. When you
have appx. ten possibly-best paths, any pair overlapping, then
maybe it's time to crank up the precision to reduce the amount of
overlapping and thus eliminate some of the paths.

Google-groups-search-key: imtrgfdi