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