algorithm - 分组坐标的特例

Question

我正在尝试编写一个程序，让学生乘坐汽车拼车参加事件。我有每个学生的地址，并且可以对每个地址进行地理编码以获得坐标(地址足够接近，我可以简单地使用坐标之间的欧几里得距离。)一些学生有车并且可以驾驶其他学生。我怎样才能有效地将学生分组在车里？我知道分组通常使用 K-Mean 等算法完成，但我只能找到将 N 个点分组为 M 个任意大小的组的算法。我的小组具有特定的规模和定位。我可以从哪里开始？一个简单的贪心算法将确保分配的第一辆汽车具有最短接客距离，但我想平均水平会很高。

Answer 1

假设您正在尝试最小化行进的总距离。显然，旅行商问题是您问题的一个特例，因此您的问题是 NP-hard 问题。这使我们进入了启发式/近似算法领域。

这个问题还需要更多的规范，例如给定的汽车可以容纳多少学生。可以说，你想要多少就多少。

你如何将它作为以最终目的地为根的最小生成树来解决。然后每个有车的学生负责收集其所有子节点。因此，总行进距离最多是生成树总长度的 2 倍，即那里的 2 倍边界。当然这是荒谬的，因为在这种情况下，根节点旁边的节点将驾驶一辆大型公共(public)汽车而不是汽车。

然后你开始玩打包游戏，你会贪婪地把车装满。

我知道这不是解决方案，但这可能有助于您更好地说明问题。