需要算法将经理分配给商店
Need Algorithm to Allocating Managers to Stores
假设您有“n”位经理和“n”家商店，所有这些都随机分布在一个地理区域中。我需要能够将每个经理分配给一家商店。经理们将每天从家中前往指定的商店。一般来说，我想尽量减少每天行驶的距离。这可以用两种方式解释：
最小化每日平均出行距离（也就是最小化总出行距离。
最小化单个经理的最大行进距离
这是已知问题吗？有没有明显的算法可以解决它？看起来和旅行商问题很像，但又不太一样。
两者都可以多项式求解
我将快速介绍定义最佳分配的两种方法，如问题中所述。请注意，我不会对旅行时间做出任何假设，例如三角不等式。当然，这样的 属性 很可能在实践中成立，并且可能有更好的算法使用这些属性。
最小化总距离
对于这个例子，我们将经理和商店视为一个加权完全二分图。然后我们想要一个最小化权重总和的匹配。
这叫做Balanced Assignment Problem, which is a specific case of minimum/maximum matching. Because the graph is bipartite, this can be solved polynomially. Wikipedia lists a couple of algorithms for solving this problem, most notably the Hungarian algorithm。
最小化最大距离
如果我们希望最小化最大距离，我们可以通过二分查找的方式找到解决方案。具体来说，我们对最大距离进行二分搜索，并尝试找到不违反此最大距离的匹配。
对于任何给定的最大距离 x，当且仅当 d(M, S) < x 时，我们创建在经理 M 和商店 S 之间具有边的二分图。然后我们尝试用任何二分匹配算法在这个二分图上创建一个完全匹配，通过成功和失败完成二分查找允许匹配的最小x，从而最小化最大距离。
假设您有“n”位经理和“n”家商店，所有这些都随机分布在一个地理区域中。我需要能够将每个经理分配给一家商店。经理们将每天从家中前往指定的商店。一般来说，我想尽量减少每天行驶的距离。这可以用两种方式解释：
最小化每日平均出行距离（也就是最小化总出行距离。
最小化单个经理的最大行进距离
这是已知问题吗？有没有明显的算法可以解决它？看起来和旅行商问题很像，但又不太一样。
两者都可以多项式求解
我将快速介绍定义最佳分配的两种方法，如问题中所述。请注意，我不会对旅行时间做出任何假设，例如三角不等式。当然，这样的 属性 很可能在实践中成立，并且可能有更好的算法使用这些属性。
最小化总距离
对于这个例子，我们将经理和商店视为一个加权完全二分图。然后我们想要一个最小化权重总和的匹配。
这叫做Balanced Assignment Problem, which is a specific case of minimum/maximum matching. Because the graph is bipartite, this can be solved polynomially. Wikipedia lists a couple of algorithms for solving this problem, most notably the Hungarian algorithm。
最小化最大距离
如果我们希望最小化最大距离，我们可以通过二分查找的方式找到解决方案。具体来说，我们对最大距离进行二分搜索，并尝试找到不违反此最大距离的匹配。
对于任何给定的最大距离 x，当且仅当 d(M, S) < x 时，我们创建在经理 M 和商店 S 之间具有边的二分图。然后我们尝试用任何二分匹配算法在这个二分图上创建一个完全匹配，通过成功和失败完成二分查找允许匹配的最小x，从而最小化最大距离。