Name: Munkres.jl
Owner: Fugro Roames
Description: Munkres algorithm for the optimal assignment problem
Created: 2015-10-23 04:41:14.0
Updated: 2017-07-28 22:50:23.0
Pushed: 2017-05-26 08:13:19.0
Homepage: null
Size: 18
Language: Julia
GitHub Committers
| User | Most Recent Commit | # Commits |
|---|
Other Committers
| User | Most Recent Commit | # Commits |
|---|
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.
ch worker-job combination has a random cost
= rand(4,4)
wever, each worker can do a certain job with zero cost
_jobs = [3,4,1,2]
(i,j) in enumerate(best_jobs); cost[i,j] = 0; end
mpute optimal assignment given the cost
uted_best_jobs = munkres(cost)
ert best_jobs == computed_best_jobs
Example output:
a> cost = rand(4,4)
Array{Float64,2}:
55632 0.0972016 0.807122 0.806295
33324 0.280094 0.261727 0.235289
3323 0.408037 0.935853 0.62243
8281 0.147279 0.649129 0.910296
a> best_jobs = [3,4,1,2]
ement Array{Int64,1}:
a> for (i,j) in enumerate(best_jobs); cost[i,j] = 0; end
a> computed_best_jobs = munkres(cost)
ement Array{Int64,1}: