Fastest path to walk over all given nodes

I'm coding a simple game and currently doing the AI part. NPC gets a list of his 'interest points' which he needs to visit. Each point has a coordinate on the map. I need to find a fastest path for开发者_运维百科 the character to visit all of the given points.

As far as I understand it, the task could be described as 'finding fastest traverse path in a strongly connected weighted undirected graph'.

I'd like to get either the name of some algorithm to calculate that or if there is no name - some keypoints on programming it myself.

Thanks in advance.

---

This is very similar to the Travelling Salesman problem, although I'm not going to try to prove equivalency offhand. The TSP is NP-complete, which means that solving the problem exactly may be impractical, depending on the number of interest points. There are approximation algorithms that you may find more useful.

---

See previous post regarding tree traversals:

Tree traversal algorithm for directory structures with a lot of files

---

I would use algorithm like: ant algorithm.

---

Not directly on point but what I did in an MMO emulator was to store waypoint indices along with the rest of the pathing data. If your requirement is to demonstrate solutions to TSP then ignore this. If not, it's worth consideration IMO.

In my case it was the best solution as otherwise the server could have potentially hundreds of mobs (re)spawning and along with all the other AI logic, would have to burn cycles computing route logic.