arrays - 算法将乘客分类到最近的车辆中，直到车辆满员

Question

我有一个类似于装箱问题的问题，但问题不同：

• 有 x 辆车，可以在 2D 平面中的任何位置
• 每辆车的载客量为 y
• 有 z 个乘客，可能在 2D 平面中的任何位置

我想编写一个算法来将乘客分类到车辆中，在以下限制内：

1. 乘客必须转移到离他们最近的车辆
2. 如果车辆达到容量，则没有更多的乘客可以移动到它上面

我想要一个伪代码算法，因为我还不确定我是否会在 JavaScript、PHP 或 SQL 中实现它。我的第一次尝试是这样的：

1. 为每位乘客分配一个从 0 开始并以 1 递增的数字 ID
2. 为每辆车分配一个从 0 开始并以 1 递增的数字 ID
3. 为与车辆 ID 具有相同名称/ID 的每辆车创建一个数组
4. 对于每个乘客，计算它与所有车辆之间的距离
5. 将结果存储在乘客/车辆数组中：[passengerID, distance to vehicleID1, distance to vehicleID2, etc.]
6. 对 z 名乘客重复这些步骤：
   • 遍历数组并找到最小的距离值。这应该是离车辆最近的乘客
   • 将乘客 ID 添加到车辆数组
   • 从乘客/车辆数组中删除该乘客项目
   • 检查添加到的车辆阵列的乘员。如果长度等于容量，则取消乘客/车辆数组中乘客距离值的每个实例

在执行结束时，如果乘客数量少于车辆总容量，我们应该有一个空的乘客/车辆数组，或者如果乘客数量超过所有车辆的容量，则该数组中会留下一些元素。我们还应该为每辆汽车拥有与其容量相同数量的元素的数组，或者如果乘客数量少于车辆容量，则可能更少。

我很确定上述方法会起作用，但我觉得可能有更有效的方法。我特别关心计算每个乘客和车辆之间的距离，因为这在计算上会很昂贵。

谁能指出我更有效的解决方案？

非常感谢，阿杰

标签： arraysalgorithmperformancesorting

Answer 1

这不是装箱问题，这是个好消息，因为装箱是 NP 难题。

相反，它是一个最小权重二分匹配问题（也称为“分配问题”），其中权重是距离。一个顶点集为每个客户提供一个元素。另一个对每个车辆座椅都有一个顶点。每个可行的车辆-客户配对都有一个优势。边缘的重量是两者之间的距离。

请注意，分配问题算法的许多介绍都解决了最大权重匹配问题。不用担心。要解决最小权重问题，只需对权重取反即可。经典解决方案是Hungarian Algorithm，其顶点数为 O(n^3)。但是，您的问题是一个称为欧几里得二分匹配的特殊版本。对于这种情况，存在渐近更快的算法。这是一份调查报告。我不知道这些在实践中更快。匈牙利算法很简单，开销非常低。

在实践中，解决几千个顶点不是问题，但 PHP、javascript 或 SQL 并不是此类计算密集型算法的最佳工具。如果您必须选择三者之一，请使用 javascript 并确保它位于具有出色 JIT 编译器的环境中。

找到最小重量匹配将对应于以最小化从客户到他们的车辆的总距离的方式将人员放入车辆中。