algorithm - 遍历所有给定节点的最快路径

Question

我正在编写一个简单的游戏，目前正在编写 AI 部分。 NPC 得到一份他需要访问的“兴趣点”列表。每个点在 map 上都有一个坐标。我需要找到角色访问所有给定点的最快路径。

据我所知，该任务可以描述为“在强连通加权无向图中寻找最快的遍历路径”。

我想得到一些算法的名称来计算它，或者如果没有名称 - 我自己编程的一些关键点。

提前致谢。

Answer 1

这与 Travelling Salesman problem 非常相似，尽管我不打算立即证明等价性。 TSP 是 NP 完全的，这意味着根据兴趣点的数量，精确地解决问题可能是不切实际的。您可能会发现更有用的近似算法。