给定两组三维点,一个源集和一个目标集。每组上的点数是任意的(可能为零)。任务是为每个目标点分配一个或不分配一个源点,以使所有距离的总和最小。如果源点多于目标点,则忽略附加点。
这个问题有一个蛮力的解决方案,但是由于点的数量可能很大,所以不可行。我听说这个问题在具有相同大小的 2D 中很容易,但遗憾的是这里没有给出这些先决条件。
我对近似值和精确解都感兴趣。
编辑:哈哈,是的,我想这听起来确实像家庭作业。事实上,它不是。我正在编写一个程序来接收大量汽车的位置,并且我正在尝试将它们映射到它们各自的停车单元。:)