A type of shortest path problem

[DarkForceRising]

Basically, I have 10 objects that I'm tracking with x and y coordinates. I want to find the shortest path (distance-wise) between an arbitrary starting object and any ending object. BUT I want to hit every object in between as well.

From what I've looked up, this is extremely close to the traveling salesman problem. The difference being I don't necessarily want to come back to the starting point. I just want the shortest total distance that I can find while still getting to all of them.

Are solutions to the traveling salesman problem the closest I'm going to come to this, or is there another algorithm that I'm unaware of?

I could always brute force the problem in question, but that looks all sorts of not-fun.

And yes, this may technically be mathematical more than coding, but I'm writing it in code. Which is why this is posted here.

 

[Cogman]

This isn't extremely close to the traveling salesman problem, this IS the traveling salesman problem. If you have a bunch of nodes that need to be hit and you want the shortest path to hit them all, it is the traveling salesman problem.

AFAIK there are no solutions that will give you the shortest answer to the traveling salesman problem other then brute force. But I have read that there are algorithms to determine how close you are to the shortest distance. thereby giving a "good enough" solution.

 

[esun]

With only 10 objects, brute force is probably not a bad idea. It's O(n!), which isn't too huge for n=10. According to Wikipedia (http://en.wikipedia.org/wiki/T...ling_salesman_problem), certain algorithms can work up to n=200 reasonably, but I'd guess it'd be significantly easier to write a brute force algorithm than a dynamic programming one. You might start with a brute force algorithm, then try to modify it into a dynamic programming one if you find it's too slow.

 

[degibson]

TSP = NP-Hard. Brute force or use combinatorial optimization.
AKA /agree Cogman, esun.

 

[presidentender]

Traveling salesman, he has to end up back at his starting point. This one, he doesn't.

Doesn't mean I know the solution, and for just ten objects, brute force is definitely the way to go. If you're doing it like TSP, though, you might not get a good solution. I'd just do nearest-neighbor (which, incidentally, is also a decent approximation for TSP).

 

[Markbnj]

Yeah, but coming back to the starting point is a fairly trivial addition to the requirements. It's still the TSP.