4

I am working on a nearfieldscanner and need to find a way to get the shortest path for the scannerhead.

Suppose I want to use 13 points at once.

  • Then I take the current position (point0) from the scanner and look for the nearest point (Point1).
  • Now Point1 becomes the current position and I look for the nearest point to point1 -(point2).
  • Now point2 becomes the current point and so on...

Offcourse this isn't really the shortest path.

The scanner has to be able to handle 25points or more at once so permutations are not an option. It takes 0.45s to travel 1cm and the surface is mostly 10x15cm.

The main goal is to win time and make the scan faster.

This has to be done in C# or Matlab.

Is this possible?

j0k
  • 22,600
  • 28
  • 79
  • 90
Tommy Dorné
  • 41
  • 1

1 Answers1

0

There is no mathematical "solution" except for brute forcing all possible combinations.
http://en.wikipedia.org/wiki/Travelling_salesman_problem

You can try different algorithms to find a "good" solution (genetic algorithm, etc), but you will never be able to tell, if you found the BEST solution.

On SO see What is an NP-complete in computer science? for example

EDIT SOMETIMES you can determine IF you have the BEST solution (except after trying all). But these are some rare special cases. If the "length" of your path equals the sum of the shortest distance of each point, you have found the optimum. Like all your points lying on a line and you go 1-2-3-n. But usually you can only find something that is NOT the best solution without knowing if there would be a better one.

EDIT2 As an idea: If the main goal is not to "waste" any time, I'd do it like this: Select the first point, you want the scanner to move to. Start moving the scanner. WHILE the scanner moves (different thread), calculate the path with the NN algorithm. Now run a Monte Carlo algo on the path to find something better. When the scanner reaches the first point, stop the MC algo (Scanner needs to signal the MoveCompletetion!) and take the first point from the path as new Scanner target. Repeat the previous steps until you reached the last point.
By this, you are only using the time for calculating that the scanner needs for moving anyway. And since you always use the NN path as base, you'll never be worse, but sometimes (often?) be better. The algorithm could easily be done in parallel and therefore get better results on multicore machines.

Community
  • 1
  • 1
igrimpe
  • 1,775
  • 11
  • 12
  • If the input size is small enough for a brute force solution, then you can tell if you found the best solution. – Sebastian Negraszus Nov 26 '12 at 10:33
  • @SebastianNegraszus Right. But then we are at the stage that the OP already ruled out: trying all permutations. – igrimpe Nov 26 '12 at 10:56
  • Brute forcing all possible combinations will take way to much time for 25points. I'm starting to think that my nearest neighbour (NN) algorithm (or so-called greedy algorithm) is going to give me the best results? Most algorithms take to much time or need a starting and ending point, while i only have a starting point. Again, the main goal is to win time and make the scan faster. It's no use finding the absolute shortest path if the total measurement time is going to take longer then with the NN algorithm. – Tommy Dorné Nov 26 '12 at 12:24
  • @TommyDorné: I've updated my answer. I would give it a try ;) – igrimpe Nov 26 '12 at 13:56
  • That's a good idea! I'll give it a try. But i'll have to use a timer instead, because there's no way to get the MoveCompletetion signal... It's an old modified CNC machine. Thanks for the help! – Tommy Dorné Nov 26 '12 at 14:19
  • This is incorrect. There are very efficient approaches that find exact solutions for TSPs. Have a look at http://www.math.uwaterloo.ca/tsp/concorde.html – SebastianK Jun 24 '20 at 17:06