57
司机乘客匹配中的距离和最小问题-朝闻道
source link: http://blog.51cto.com/yixianwei/2111980
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
这个是在工作中遇到的一个实际的算法问题，问题描述如下，当前有m个司机，n个乘客，每个司机和每个乘客的距离由经纬度可以计算得到，如何匹配可以使其去接乘客的距离和最小？（只能一个司机接一个乘客）带权二分图方法一般对KM算法的描述，基本上可以概括成以下几个步骤：（1）初始化可行标杆（2）用匈牙利算法寻找完备匹配（3）若未找到完备匹配则修改可行标杆（4）重复（2）（3）直到找到相等子图的完备匹配关于该算法
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK