Re: Worst Case Greedy Walk

From	"INFINITY POWER" <infinity@limited.com>
Newsgroups	comp.programming, comp.theory, sci.math, comp.graphics.algorithms
Subject	Re: Worst Case Greedy Walk
Date	2011-11-02 17:49 +1000
Organization	A noiseless patient Spider
Message-ID	<j8qsnb$ugo$1@dont-email.me> (permalink)
References	<10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com>

Cross-posted to 4 groups.

Show all headers | View raw

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!

Back to comp.programming | Previous | Next — Previous 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