最小距离

Question

3

有一组9个学生和3所学校，每所学校最多可以分配3名学生。每所学校和学生都有它们的坐标。现在我们必须分配学生，以便所有学生到学校的距离之和最小。

我在面试中被问到这个问题。有人能为此提供一个算法吗？

最初我尝试了贪心方法，但并不起作用。然后我尝试应用动态编程方法，但无法想出最优子结构。

- Avinash

3

手头的问题被称为二分图匹配。 - Rob Audenaerde

你能推荐一些关于二分图匹配的好读物吗？ - Avinash

这本书很好，但可能过于理论化："Matching Theory" by M.D. Plummer, L. Lovász。 - Evgeny Kluev

2个回答

1

如果问题规模足够小，尝试使用穷举搜索怎么样？

因此，(9选3) * (6选3) = 1680

- sampson-chen

我正在寻找一种高效的解决方案。 - Avinash

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

每所学校有3个位置，所有3所学校共有9个位置。你需要在9个位置和9名学生之间找到最佳匹配。

这个分配问题可以用匈牙利算法来解决。