一个找点对应关系，使得所有点移动距离和最小的问题

htgo

如附件图，散乱的蓝色点为初始化位置
现：经过移动变为红色3×3 队列；
问题：如何规划每一个蓝色点移到哪个对应的红色点，使得所有蓝色点移动的距离和最短。
如果没有最优解，是否有优化解。
备注：
1. 个点，希望有一种针对 n个点的算法。满足条件初始化为固定的任意形状，目标队列也为固定的任意形状，求最优的对应关系；
2. 最龊的方法是所有的映射关系遍历，复杂度为 O(n!)，实不可取；
3. 我试过用 PCA算法进行分块对应，块中再分别映射，复杂度为O(a!b!...(n-a-b..)! ) ，a,b,...,n-a-b... 满足 a + b + ... + ( n-a-b... ) = n；

木直清风

有趣的问题,收藏下,