Re: OT: Nonlinear Approximation

[Quentin Spencer]

Bill Denney wrote:

> So this is a bit off topic, but I've looked for a while and I think 
> that I just don't know the right way to search for this, and someone 
> on the list may know a better way to do it.
>
> I've got a device with four tips that can access points on a 2d 
> surface like
>
> 1 2 3 4
> .......
>
> where by that I mean it hits the first dot then it hits the third dot 
> then the fifth then the 7th.  If I want to hit the first then the 
> second, I have to move one unit to the left.  If I want to hit the 
> first then the first on the next row, I have to move one row down and 
> two units left. After the 4th access then the first tip is used again 
> (so it will be to the left by seven from wherever the 4th hit is).
>
> Now, what I have is a matrix of spots that I need to hit and I want to 
> move through the points as quickly as possible.  This is generally the 
> travelling salesman problem I think, but it's nonlinear.
>
> Essentially, I think that this is best broken up into two problems:
>
> 1) find the sets of 4 hits to do at a time then
> 2) connect those sets by a best path.
>
> My first attempt was a simple greedy search, and it (predictably) 
> didn't work too well.  Does anyone have any suggestions on how to best 
> accomplish this or any resources to look into for it?


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.

-Quentin



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