我有一个问题，由一个有墙、目标和代理的方形迷宫组成。代理只能水平/垂直移动。在每一步，每个智能体从 1 个方格移动。
我必须实现 A* 算法来解决问题，但我很难找到一个很好的启发式算法来解决它。
每次我阅读有关最佳启发式方法的文档时，它总是涉及一个只有一个代理和多个目标的迷宫，但与多个代理无关。
我尝试试验的启发式方法如下:
对于每个目标，我采用距代理最近的 Manathan 距离并对结果求和。
在这种情况下，如果还剩下两个目标和三个智能体，则只求和两个智能体，不考虑最远的智能体，总和将小于三个智能体和三个目标的情况。
根据可接受启发式的定义，我怀疑我的启发式是否可接受。
我觉得这是合理的，因为它考虑了每一种食物，而不仅仅是一种，但我认为我遗漏了一个重要的观点。
有人可以考虑一些技巧或有趣的方法吗？
最佳答案
A* 仅适用于一个代理。您需要为每个代理运行一个单独的搜索实例。
如果有很多代理而只有几个目标，并且你的图是无向的，你可以从目标搜索到代理而不是(假设你只需要最近的代理)然后反向结果。
如果您需要对很多很多 代理进行路径查找，您应该使用不同的算法。有很多选择；此处要查找的关键字是“群体寻路”、“人群流动”和“群体”。通常，您将为整个 map 创建一个矢量场，并将其与某种回避算法相结合。
关于algorithm - 最佳 A* 启发式 : multiple targets and agents，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52996201/