遍历所有给定节点的最快路径
我正在编写一个简单的游戏，目前正在做人工智能部分。 NPC 获得他需要访问的“兴趣点”列表。每个点在地图上都有一个坐标。我需要找到一条最快的路径让角色访问所有给定点。
据我了解，该任务可以描述为“在强连接的加权无向图中找到最快的遍历路径”。
我想获得一些算法的名称来计算它，或者如果没有名称 - 我自己编程的一些要点。
提前致谢。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这与旅行推销员问题非常相似，尽管我不会尝试证明等价性随手。 TSP 是 NP 完全的，这意味着精确地解决问题可能不切实际，具体取决于兴趣点的数量。您可能会发现一些更有用的近似算法。
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.
不是直接针对点，而是我在 MMO 模拟器中所做的是将航点索引与其余路径数据一起存储。如果您的要求是演示 TSP 解决方案，请忽略此内容。如果没有，我认为值得考虑。
就我而言，这是最好的解决方案，否则服务器可能会产生数百个生物（重新）生成，并且与所有其他人工智能逻辑一起，将不得不消耗循环计算路线逻辑。
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.