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-14 06:58 +1000
Organization	A noiseless patient Spider
Message-ID	<j9pb2k$u98$1@dont-email.me> (permalink)
References	(1 earlier) <j8skbl$f86$1@dont-email.me> <MPG.29222115a695e7b29896b7@news.eternal-september.org> <j996jq$obp$1@dont-email.me> <MPG.29230cc6427cda819896b8@news.eternal-september.org> <REM-2011nov13-001@Yahoo.Com>

Cross-posted to 4 groups.

Show all headers | View raw

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

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