Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #963 > unrolled thread

Worst Case Greedy Walk

Back to article view | Back to comp.programming

Contents

  Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-10-31 08:11 -0700
    Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-10-31 21:24 -0700
      Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:41 -0700
        Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-11-01 20:32 -0700
    Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-01 07:21 +0000
      Re: Worst Case Greedy Walk James Dow Allen <jdallen2000@yahoo.com> - 2011-11-01 00:45 -0700
        Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 13:02 -0700
          Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-02 09:57 +1300
            Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-03 10:55 +1300
              Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-03 09:39 +1000
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-07 17:09 +1300
                  Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-08 04:04 +1000
                    Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 09:54 +1300
                      Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2011-11-13 11:50 -0800
                        Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-14 06:58 +1000
                          Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2012-03-29 00:28 -0700
                    Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 11:44 +1300
                      Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 14:28 +1300
      Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:46 -0700
        Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-02 08:16 +0000
          Re: Worst Case Greedy Walk Patricia Shanahan <pats@acm.org> - 2011-11-02 05:27 -0700
    Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 14:29 -0700
      Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 15:30 -0700
      Re: Worst Case Greedy Walk Steve Thompson <thomps2048@yahoo.ca> - 2011-11-01 20:56 -0400
    Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 01:55 -0500
      Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 18:24 -0500
    Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-02 17:49 +1000

Page 1 of 2  [1] 2  Next page →

#963 — Worst Case Greedy Walk

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.

[toc] | [next] | [standalone]

#965

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.
>

[toc] | [prev] | [next] | [standalone]

#969

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.

[toc] | [prev] | [next] | [standalone]

#977

[Multipart message — attachments visible in raw view] — view raw

On Tue, 1 Nov 2011, Andrew Tomazos wrote:
> 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.

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.

[toc] | [prev] | [next] | [standalone]

#966

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 

[toc] | [prev] | [next] | [standalone]

#967

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

[toc] | [prev] | [next] | [standalone]

#971

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.

[toc] | [prev] | [next] | [standalone]

#972

In article <68cedc9e-e144-42fb-957c-d5c93899c283
@s30g2000yqd.googlegroups.com>, andrew@tomazos.com says...
> 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.

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

[toc] | [prev] | [next] | [standalone]

#983

In article <MPG.291b24605be9a6a29896b2@news.eternal-september.org>, 
m.fee@irl.nospam.cri.nz says...
> In article <68cedc9e-e144-42fb-957c-d5c93899c283
> @s30g2000yqd.googlegroups.com>, andrew@tomazos.com says...
> > 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.
> 
> 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)?
> 
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

[toc] | [prev] | [next] | [standalone]

#985

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

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

[toc] | [prev] | [next] | [standalone]

#1001

In article <j8skbl$f86$1@dont-email.me>, infinity@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

[toc] | [prev] | [next] | [standalone]

#1004

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...
>
> > 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


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 

[toc] | [prev] | [next] | [standalone]

#1005

In article <j996jq$obp$1@dont-email.me>, infinity@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

[toc] | [prev] | [next] | [standalone]

#1038

> 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

[toc] | [prev] | [next] | [standalone]

#1039

On Nov 14, 5:50 am,  (Robert Maas, http://tinyurl.com/uh3t) wrote:
> > 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


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

[toc] | [prev] | [next] | [standalone]

#1385

> 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

[toc] | [prev] | [next] | [standalone]

#1006

In article <j996jq$obp$1@dont-email.me>, infinity@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

[toc] | [prev] | [next] | [standalone]

#1007

In article <MPG.29232679578070d49896b9@news.eternal-september.org>, 
m.fee@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

[toc] | [prev] | [next] | [standalone]

#970

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.

[toc] | [prev] | [next] | [standalone]

#980

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 

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming

csiph-web