我目前正在写 a web application用于创建和操作 graphs (在图论意义上，不是图表)。为此，我想实现一些“排列为...”函数，这些函数采用选定的顶点并将它们排列成特定的形状(您可以忽略边缘)。
现在编写简单的算法来将顶点排列成网格或圆形是微不足道的。不过，我想做的是找到一种通用算法，用于获取 n 实际顶点坐标和 n 目标顶点坐标，并从前者到后者，以便顶点需要移动的距离的总和或平均值(以最容易的为准)最小化。这个想法是，如果顶点已经与所需排列有些相似，那么这些函数应该主要只是“清理”现有排列，而不会从根本上改变相对位置。
例如，如果我有 12 个顶点排列成一个粗略的圆，标记为 1-12，就像时钟上的小时，我希望我的“排列为圆”算法将它们对齐到完美 圆圈与时钟上的小时数相同，顺序为 1-12。如果我有 25 个顶点排列在一个粗略 5x5 网格中，我希望我的“排列为网格”算法以相同的顺序将它们对齐到一个完美 5x5 网格。
当然，理论上我可以使用通用的约束优化/爬山算法或暴力破解排列，但两者都太低效，无法在浏览器中执行客户端。是否有更具体、已知的方法来找到二维坐标列表之间良好的“低能量”1:1 映射？
最佳答案
这就是所谓的分配问题。或者更具体地说，线性分配问题(因为对象和目的地的数量相同)。有多种算法可以解决它。最值得注意的是匈牙利算法。
参见 https://en.wikipedia.org/wiki/Assignment_problem
您的成本函数 C(i,j) 将很简单
C(i,j) = distance between points i and j
i 点是您当前的位置，j 点是您的目的地。
关于algorithm - 最小化二维坐标映射的快速算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35422370/