以最小代价将 N 个特工安置到 M 个避难所的算法
Algorithm to place N agents into M shelters with minimal cost
TL;DR：简短的问题描述：
我正在寻找一种有效的算法来优化如何通过最小化代理人需要移动的距离将位于 2D space 中的 N 个代理人放置到 M 个避难所中。
每个避难所只能容纳1名特工。如果 N > M（特工多于可用避难所），则某些特工不会被安置到避难所（所有特工都一样）。
（可选的简化：虽然代理可以在 2D 中自由定位 space，但避难所始终排列在方形网格上。没有代理位于避难所的凸包之外。）
这就是您需要知道的全部内容。但是，如果您认为这个问题没有有效的解决方案，那么这里是...
问题的更具体（对我来说最相关）的版本：
正好有 9 个避难所，排列在正方形网格上（距离为 d）。所有 N 个代理都位于中央避难所周围（在以中央避难所为中心的大小为 d*d 的盒子中）。但是，在这种情况下，中央避难所始终是空的，但所有其他避难所在开始时可能可用或不可用（空）。
对于这种情况，我需要一种算法来解决任意多个代理 N（通常 N < 9）和任意可用庇护所（全部 9 个，或者在极端情况下仅中央庇护所）的问题。
该算法应该是高效的，因为我需要快速解决其中的许多问题。
示例：
这是一个示例，其中 N=3 个特工（黑点）和 M=5 个可用避难所（绿点）。红点表示不可用的避难所。 ]1 我用字母表示避难所，用数字表示特工。
到目前为止我做了什么：
我确信这个问题有一个特定的名称并且已经 solved/studied，但我找不到它的名称或任何解决方案。我需要快速解决其中的许多问题，并且我总是想要最佳解决方案（如果不可能，一个几乎最佳的解决方案也足够了）。这是我目前 tried/thought 的内容：
- 蛮力：我知道可以用蛮力找到问题的最佳解决方案，方法是检查所有可能的选项，计算每个选项的总行程，然后选择总行程距离最小的选项。如果M和N很大，这可能涉及很多计算。
- 一个快速但非常非最优的解决方案如下：对于每个智能体 i，计算到中心节点 E 的距离。从到 E 的距离最小的智能体 i 开始，将 i 分配到它最近的避难所（在这个案例：E）。然后将下一个代理分配到其最近的避难所，考虑到 E 现在不再可用，等等，直到所有代理都被分配或停止，如果没有更多的空闲避难所可用。这有效，速度很快，但当然会产生非最佳结果（在示例图像中：2->E，1->B，3->F，而最佳解决方案应该是 3->E，2->F , 1->B)
- 我正在研究的另一个想法是首先找到承受最大“压力”的代理，即他们所有的好选择都在很远的地方。从压力最大的代理开始，将其分配到最近的避难所。继续所有其他代理。但是，我不确定如何正确定义这个问题的“压力”，因为它可能应该是到前几个避难所的距离的组合。另外，我不确定这是否会导致最优解，但可能会导致几乎最优解。
- 我试图将此问题视为某种加权排列，也就是说，我需要 select N 个避难所并将它们映射到 N 个代理，但每个映射都是有代价的。我需要最小化总成本，但我不知道该怎么做。
- 此外，我正在考虑某种模拟退火，或某种形式的推拉算法，其中每个避难所都吸引代理，或者代理根据距离被吸引到避难所。虽然这听起来很有趣，但我认为这在计算上效率不高。
我很高兴收到任何意见，特别是如果这个问题已经有了合适的名称和解决方案。我也很高兴有一个简单且计算速度快的算法，可以实现几乎最优的解决方案。
正如评论中所建议的（再次感谢！），这确实是由 this post 回答的。
具体来说，这是一个分配问题，由匈牙利算法解决，将代理人视为工人，将庇护所视为任务，并将工人 i 执行任务 j 的成本是代理 i 和庇护所 j 之间的曼哈顿距离。
python package munkres实现了这个算法，对于9-shelter问题速度非常快。如果避难所的数量多于特工的数量，程序包会自动处理。对于代理人多于庇护所的情况，我对删除随机代理人感到满意，直到代理人的数量等于庇护所的数量。所以我的问题就解决了。
TL;DR：简短的问题描述：
我正在寻找一种有效的算法来优化如何通过最小化代理人需要移动的距离将位于 2D space 中的 N 个代理人放置到 M 个避难所中。
每个避难所只能容纳1名特工。如果 N > M（特工多于可用避难所），则某些特工不会被安置到避难所（所有特工都一样）。
（可选的简化：虽然代理可以在 2D 中自由定位 space，但避难所始终排列在方形网格上。没有代理位于避难所的凸包之外。）
这就是您需要知道的全部内容。但是，如果您认为这个问题没有有效的解决方案，那么这里是...
问题的更具体（对我来说最相关）的版本：
正好有 9 个避难所，排列在正方形网格上（距离为 d）。所有 N 个代理都位于中央避难所周围（在以中央避难所为中心的大小为 d*d 的盒子中）。但是，在这种情况下，中央避难所始终是空的，但所有其他避难所在开始时可能可用或不可用（空）。
对于这种情况，我需要一种算法来解决任意多个代理 N（通常 N < 9）和任意可用庇护所（全部 9 个，或者在极端情况下仅中央庇护所）的问题。
该算法应该是高效的，因为我需要快速解决其中的许多问题。
示例：
这是一个示例，其中 N=3 个特工（黑点）和 M=5 个可用避难所（绿点）。红点表示不可用的避难所。
到目前为止我做了什么：
我确信这个问题有一个特定的名称并且已经 solved/studied，但我找不到它的名称或任何解决方案。我需要快速解决其中的许多问题，并且我总是想要最佳解决方案（如果不可能，一个几乎最佳的解决方案也足够了）。这是我目前 tried/thought 的内容：
- 蛮力：我知道可以用蛮力找到问题的最佳解决方案，方法是检查所有可能的选项，计算每个选项的总行程，然后选择总行程距离最小的选项。如果M和N很大，这可能涉及很多计算。
- 一个快速但非常非最优的解决方案如下：对于每个智能体 i，计算到中心节点 E 的距离。从到 E 的距离最小的智能体 i 开始，将 i 分配到它最近的避难所（在这个案例：E）。然后将下一个代理分配到其最近的避难所，考虑到 E 现在不再可用，等等，直到所有代理都被分配或停止，如果没有更多的空闲避难所可用。这有效，速度很快，但当然会产生非最佳结果（在示例图像中：2->E，1->B，3->F，而最佳解决方案应该是 3->E，2->F , 1->B)
- 我正在研究的另一个想法是首先找到承受最大“压力”的代理，即他们所有的好选择都在很远的地方。从压力最大的代理开始，将其分配到最近的避难所。继续所有其他代理。但是，我不确定如何正确定义这个问题的“压力”，因为它可能应该是到前几个避难所的距离的组合。另外，我不确定这是否会导致最优解，但可能会导致几乎最优解。
- 我试图将此问题视为某种加权排列，也就是说，我需要 select N 个避难所并将它们映射到 N 个代理，但每个映射都是有代价的。我需要最小化总成本，但我不知道该怎么做。
- 此外，我正在考虑某种模拟退火，或某种形式的推拉算法，其中每个避难所都吸引代理，或者代理根据距离被吸引到避难所。虽然这听起来很有趣，但我认为这在计算上效率不高。
我很高兴收到任何意见，特别是如果这个问题已经有了合适的名称和解决方案。我也很高兴有一个简单且计算速度快的算法，可以实现几乎最优的解决方案。
正如评论中所建议的（再次感谢！），这确实是由 this post 回答的。
具体来说，这是一个分配问题，由匈牙利算法解决，将代理人视为工人，将庇护所视为任务，并将工人 i 执行任务 j 的成本是代理 i 和庇护所 j 之间的曼哈顿距离。
python package munkres实现了这个算法，对于9-shelter问题速度非常快。如果避难所的数量多于特工的数量，程序包会自动处理。对于代理人多于庇护所的情况，我对删除随机代理人感到满意，直到代理人的数量等于庇护所的数量。所以我的问题就解决了。