I need to find an algorithm which can calculate the shortest path through a certain number of points in space

[littlesphaeroid]

In this case he probably doesn't need to return to the start point, so the problem is simplified:

http://stackoverflow.com/questions/7763432/what-is-the-difference-between-travelling-salesman-and-fi...

Also, the number of points is probably small, so the computation time should be quite quick for the shortest path.

[FM82]

Yes, the "Travelling salesman problem" is exactly what i search for. Thank you very much. Now i only need to study hard....!

[jcarmody]

Brute-force will be sufficient for the movement of a camera.

[FM82]

I don't think brute force will be applicable. With only 10 points in space i must check (10-1)!/2=181.440 different paths.

[GerdW]

Hi FM,

with just 180k possible paths you can employ brute force…

[FM82]

It was only an example, if the user begin to add points where to move the camera (my software must be programmable) i fear i can get stuck in the optimization routine.

---

GerdW ha scritto:

Hi FM,

with just 180k possible paths you can employ brute force…

---

[Bob_Schor]

Consider your requirements.  Do you need absolutely the shortest path, or an "efficient tour" (i.e. "one of the shorter paths")?  Do you have a fixed starting point, or is it arbitrary (in which case there may be different "shortest paths")?  Can you visit a point more than once on a tour?

I suspect that if conditions are relaxed a little, adding a new point becomes computationally much simpler.  For example, if the sequence p(i) (where i goes from 1 to N, number of points) is your current "good" path, take your new point, put it between successive p(i) and p(i+1), and see which of the N paths is shortest.  Note that this will (almost certainly) degrade if you do it multiple times, but to add, say, 3 points to a tour of 10, I'd guess it wouldn't be too bad.

Bob Schor