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

Groups > comp.programming > #1004

Re: Worst Case Greedy Walk

Cross-posted to 4 groups.

Show all headers | View raw

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 

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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

csiph-web