我正在编写一个简单的游戏，目前正在做 AI 部分。NPC 获得他需要访问的“兴趣点”列表。每个点在地图上都有一个坐标。我需要为角色找到一条最快的路径来访问所有给定的点。
据我了解，该任务可以描述为“在强连接的加权无向图中找到最快的遍历路径”。
我想获得一些算法的名称来计算它，或者如果没有名称 - 我自己编程的一些关键点。
提前致谢。
问问题
337 次
4 回答
2
这与旅行推销员问题非常相似，尽管我不会试图立即证明等价性。TSP 是 NP 完全的，这意味着根据兴趣点的数量准确地解决问题可能是不切实际的。您可能会发现一些近似算法更有用。
于 2010-12-16T22:45:01.603 回答
1
请参阅上一篇关于树遍历的文章：
于 2010-12-16T22:37:48.987 回答
1
我会使用类似的算法：蚂蚁算法。
于 2010-12-17T08:28:05.040 回答
0
不是直接在点上，而是我在 MMO 模拟器中所做的是将航点索引与其余的路径数据一起存储。如果您的要求是演示 TSP 的解决方案，请忽略这一点。如果没有，IMO 值得考虑。
在我的情况下，这是最好的解决方案，否则服务器可能有数百个生物（重新）生成，并且与所有其他 AI 逻辑一起，将不得不消耗循环计算路由逻辑。
于 2010-12-17T14:58:42.997 回答