sap*_*sap 7 algorithm hungarian-algorithm
所以我有一个工作分配问题,没有匈牙利方法所需的传统成本.
例如:
I have 3 workers - A, B and C
I have 5 jobs - 1, 2, 3, 4 and 5
每个工人都有他可以执行的工作列表,如下所示:
worker A can work on job 1, 2, 5
worker B can work on job 1, 2
worker C can work on job 1
最终结果(因为没有成本)是我可以实现的最大分配数.在这个例子中,我最多可以完成3个任务:
worker A on job 5
worker B on job 2
worker C on job 1
匈牙利方法是解决这个问题的好方法吗？我应该只使用"虚拟"费用吗？我想也许可以使用工作偏好的指数作为成本; 这是一个好主意吗？
将成本-1分配给他们可以执行的作业,其他则为零.
然后运行匈牙利算法,它会给你答案(实际上它会返回-answer).
不要用一些大数字,它可能会导致溢出(除非你非常小心地实施匈牙利).
实际上,它是二分图中的最大匹配,并且有很多方法可以解决这个问题,请参阅维基页面:
http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs
PS:Hopcroft-Karp算法比匈牙利语更快,也更简单.值得一试.一些编译方法比这两种方法更快,但不建议首先学习这些算法.
PSS:stackoverflow中的ID是解决此问题的方法.这是一种网络流量方式.它被称为最短参数路径(sap).见:http://coral.ie.lehigh.edu/~ted/files/ie411/lectures/Lecture11.pdf
| 归档时间： |
|
| 查看次数： |
1224 次 |
| 最近记录： |