已知N个起点的坐标和N个终点的坐标,不一一对应,有算法可以寻找到最佳适配方案吗
Kuhn-Munkres算法(二分图最大权匹配)
■网友
从优化的角度来看待这个问题,可以简单地看成一个任务分配问题(assignment problem)。就是一个简单的二分图最大权分配,匈牙利算法是解决这个问题的经典算法之一。
【已知N个起点的坐标和N个终点的坐标,不一一对应,有算法可以寻找到最佳适配方案吗】 另一个简单的化归就是求最大流。不过在我的印象里最大流算法大多对非整数权重无能……
另外既然是优化,可以化归为一个优化问题,用单纯形法(simplex algorithm)来解决。
当作优化问题来解相当于抛弃了问题的几何性质,所以我建议或许也能从计算几何角度入手。 不过个人对计算几何不是很了解。猜想可能Voronoi diagram会相关?
推荐阅读
- 盐城■用双脚丈量熟悉又陌生的街道!盐城坐标城市定向赛激情开跑
- 坐标合肥,请问在哪里能捕捉到程序员这种生物他们大都出现在哪里呢
- 人民车市|新语言、新起点,捷达VS7 强势入局
- 方程|高考数学坐标系与参数方程知识点总结!速速收藏!
- 国家测绘局提供的标准地图采用的是啥投影坐标系(2008年7月)
- 怎么样看待起点玄幻小说快餐化和土蕃三辰等网文大神的衰败?
- 起点读书的签到抽奖能算欺诈么
- 怎样看待起点中文网把个人中心全换成php了
- 自动化脚本和多几个人一起点是等效的吗
- 怎样利用包含 xyz 坐标的 txt 文件转生成 DEM
