algorithm - 最佳 A* 启发式：多个目标和代理

我有一个问题，包括一个带有墙壁、目标和代理的方形迷宫。代理只能水平/垂直移动。在每一步，每个代理从 1 个方格移动。

我必须实现一个 A* 算法来解决这个问题，我很难找到一个好的启发式来解决它。

每次我阅读有关最佳启发式的文档时，它总是涉及只有一个代理和多个目标的迷宫，而与多个代理无关。

我尝试尝试的启发式方法如下：

对于每个目标，我取离代理最近的 Manathan 距离，然后对结果求和。

在这种情况下，如果剩下两个目标和三个智能体，总和只需要两个智能体，不考虑最远的智能体，总和将小于剩下三个智能体和三个目标的情况。

根据可接受启发式的定义，我怀疑我的是否可以接受。

我觉得它是合理的，因为它考虑了每一种食物，而不仅仅是一种，但我认为我错过了一个重要的观点。

有人有提示或有趣的方法可以考虑吗？

标签： algorithmgraph-algorithmmazeheuristics

A* 仅适用于一名代理。您需要为每个代理运行单独的搜索实例。

如果有很多代理并且只有几个目标，并且您的图表是无向的，您可以从目标搜索到代理（假设您只需要最近的代理）然后反转结果。

如果您需要使用大量代理进行路径查找，则应使用不同的算法。有很多选择；此处要查找的关键字是“swarm pathfinding”、“crowd flow”和“boids”。通常，您将为整个地图创建一个矢量场，并将其与某种回避算法相结合。