Julia implementation of the Hungarian algorithm for the optimal assignment problem: Given N workers and M jobs, find a minimal cost assignment of one job to each worker.
A synthetic example with a simple solution.
# Each worker-job combination has a random cost
cost = rand(4,4)
# However, each worker can do a certain job with zero cost
best_jobs = [3,4,1,2]
for (i,j) in enumerate(best_jobs); cost[i,j] = 0; end
# Compute optimal assignment given the cost
computed_best_jobs = munkres(cost)
@assert best_jobs == computed_best_jobsExample output:
julia> cost = rand(4,4)
4x4 Array{Float64,2}:
0.455632 0.0972016 0.807122 0.806295
0.933324 0.280094 0.261727 0.235289
0.53323 0.408037 0.935853 0.62243
0.08281 0.147279 0.649129 0.910296
julia> best_jobs = [3,4,1,2]
4-element Array{Int64,1}:
3
4
1
2
julia> for (i,j) in enumerate(best_jobs); cost[i,j] = 0; end
julia> computed_best_jobs = munkres(cost)
4-element Array{Int64,1}:
3
4
1
2