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 2 of 2 — ← Prev page 1 [2]

#981

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

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

#973

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

a (square) spiral


Herc

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

#974

On Nov 2, 7:29 am, Graham Cooper <grahamcoop...@gmail.com> wrote:
> 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.
>
> > 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.
>
> a (square) spiral
>

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

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

#976

On Tue, Nov 01, 2011 at 02:29:09PM -0700, Graham Cooper wrote:
> 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.
> >
> > 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.
> 
> a (square) spiral

Too obvious?  What about triangles?





Steve Thompson

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

#978

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

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

#984

On Wed, 02 Nov 2011 01:55:06 -0500, quasi <quasi@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.

>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)
>
>??

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

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

#979

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!

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.programming

csiph-web