maf*_*afu 8 mapping algorithm math mathematical-optimization
给定两组三维点,源和目标集.每组上的点数是任意的(可以是零).任务是为每个目标点分配一个或没有源点,以便所有距离的总和最小.如果源位置多于目标点,则忽略其他点.
这个问题有一个强力解决方案,但由于点数可能很大,所以不可行.我听说这个问题在2D中具有相同的设置大小很容易,但遗憾的是这些先决条件在这里没有给出.
我对近似和精确解决方案感兴趣.
编辑:哈哈,是的,我想这听起来像家庭作业.实际上,事实并非如此.我正在编写一个接收大量汽车位置的程序,我正试图将它们映射到各自的停车位.:)
我突然想到了空间排序，然后是模拟退火。
将空间网格化并将集合排序到空间单元中。
解决每个单元内的 O(NM) 问题，然后解决单元邻域内的 O(NM) 问题，以此类推，以获得尝试匹配。
最后，运行大量的模拟退火循环，在其中随机改变匹配，以探索附近的空间。
这是启发式的，可以为您提供一个好的答案，尽管不一定是最好的，并且由于初始网格排序，它应该相当有效。