Re: OT: Nonlinear Approximation

[Bill Denney]

On Thu, 9 Feb 2006, Quentin Spencer wrote:

> Like you said, this is basically the travelling salesman problem, but if 
> I understand correctly, the difference is in how the distance is 
> measured. Instead of the traditional L2 or Euclidean norm (the sqare 
> root of the sum of the squares of the vectors, see 
> http://mathworld.wolfram.com/L2-Norm.html), you want to measure distance 
> using the L1 norm (the sum of the absolute values of the vectors, 
> http://mathworld.wolfram.com/L1-Norm.html). I'm no expert on these types 
> of problems, but this sounds like the problem that mapquest.com and 
> maps.google.com are trying to solve, except they are usually only 
> dealing with 2 points, and accompanying each possible path is also a 
> velocity metric. A quick google search on travelling salesman and 
> 1-norms showed several references to wiring printed circuit boards, 
> which I am sure has been the subject of plenty of research, so you might 
> try looking there.

I don't think it's the L1 norm.  The difference I think comes from the 
fact that there is zero movement required to move from position 1 to 
position 3, but there is one unit of movement to move from position 1 to 
position 2 or 4.  I'm not sure if I described it well before.  What I 
meant to say before is that movement after I choose position 1 the 
distance matrix looks something like (in the local region only when you 
first hit the 2 on the first column of the middle row)

2.2 1.4 1 1.4 2.2 3.2
2   1   0 1   2   3
2.2 1.4 1 1.4 2.2 3.2

the 2.2 is really sqrt(5), 1.4 is really sqrt(2) and 3.2 is sqrt(10).

Bill

--
"It's good to have money and the things that money can buy, but it's
good, too, to check up once in a while and make sure that you haven't
lost the things that money can't buy."
  -- George H. Lorimer



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------