已知N个起点的坐标和N个终点的坐标,不一一对应,有算法可以寻找到最佳适配方案吗

Kuhn-Munkres算法(二分图最大权匹配)

■网友
从优化的角度来看待这个问题,可以简单地看成一个任务分配问题(assignment problem)。就是一个简单的二分图最大权分配,匈牙利算法是解决这个问题的经典算法之一。

【已知N个起点的坐标和N个终点的坐标,不一一对应,有算法可以寻找到最佳适配方案吗】 另一个简单的化归就是求最大流。不过在我的印象里最大流算法大多对非整数权重无能……

另外既然是优化,可以化归为一个优化问题,用单纯形法(simplex algorithm)来解决。

当作优化问题来解相当于抛弃了问题的几何性质,所以我建议或许也能从计算几何角度入手。 不过个人对计算几何不是很了解。猜想可能Voronoi diagram会相关?


    推荐阅读