bmat ← ##.assign costs ⍝ Hungarian method cost assignment. [assign] is a classic algorithm implemented in the D style. H.W.Kuhn published a pencil and paper version in 1955, which was followed by J.R.Munkres' execut- able version in 1957. The algorithm is sometimes referred to as the "Hungarian method". The method indicates an optimal assignment of a set of resources to a set of requirements, given a "cost" of each potential match. Examples might be the allocation of workers to tasks; the supply of goods by factories to warehouses; or the matching of brides with grooms. The function takes a cost matrix as argu- ment and returns a boolean assignment matrix result. The following table shows an optimal assignment of factories F, G, H to ware- houses W, X, Y, given that the cost of transportation from F to W is 72 units, F to X is 99 units, ···, G to W is 23 units, ··· and so on. W X Y ┌────┬────┬────┐ F │[72]│ 99 │ 88 │ Minimum-cost assignment marked [.]: ├────┼────┼────┤ G │ 23 │ 30 │[35]│ Factory F supplies warehouse W, ├────┼────┼────┤ ·· G ·· ·· ·· ·· Y, H │ 51 │[59]│ 84 │ ·· H ·· ·· ·· ·· X. └────┴────┴────┘ Notice that if the problem requires maximizing a benefit, rather than minimizing a cost, then a negative cost matrix is used. See below for an example. Technical notes: Munkres' algorith may be described in words as follows: Step 0: Ensure the costs matrix has at least as many rows as columns, by appending extra 0-item rows if necessary. Go to Step 1. Step 1: Subtract the smallest item in each row from the row. Go to Step 2. Step 2: Select a set of "independent" zeros in the matrix and mark them with a star (*). To do this, star leading zeros in each row and column, ignoring rows and columns already containing stars; repeat this process until apart from ignored rows and columns, no more zeros remain. Go to Step 3. Step 3: Draw a line through (cover) each column containing a starred zero. If all col- umns are covered, the starred zeros represent an optimal assignment. In this case, return a boolean matrix with the positions of the stars, as result. Other- wise, go to Step 4. Step 4: Find an uncovered zero. If there is none, go to Step 6 passing the smallest un- covered value as a parameter. Otherwise, mark the zero with a prime (') and call it P0. If there is a starred zero (S1) in the row containing P0, cover this row and uncover the column containing S1, then repeat Step 4. Otherwise, (if there is no starred zero in P0's row) go to Step 5. Step 5: Find a path through alternating primes and stars. Starting with the uncovered prime (P0) found in Step 4, find a star S1 (if any) in its column. Then find a prime P2 (there must be one) in S1's row, followed by a star S3 (if any) in P2's column, ··· and so on until a prime (Pn) is found that has no star in its column. In the series P0, S1, P2, S3, ··· Pn, unstar each starred zero Si and star each primed zero Pj. Finally, unprime all primed zeros in the matrix, un- cover all rows and columns. Go to Step 3. Step 6: Add the minimum cost value passed from Step 4 to each twice-covered (row and column covered) item, and subtract it from each uncovered item. Preserving all stars, primes and covering lines, go to Step 4. The approach uses a rather convoluted "stepping algorithm", which can be repres- ented as a flowchart: step0 after step:0, go to step:1. ↓ │ step1 after step:1, go to step:2. ↓ │ step2 after step:2, go to step:3. ↓ │ ┌→step3───→ after step:3, go to step:4 or exit. │ │ ┌─│─→─↓─←───┐ │ │ │ ↑ │ │ step4─→─┤ after step:4, go to step:4 or step:5 or step:6. ↑ ↑ │ ↓ │ │ ↓─←─┐ │ │ │ │ │ │ │ └─step5─┘ │ after step:5, go to step:5 or step:3. ↑ ┌─←───┘ │ ↓ │ step6 after step:6, go to step:4. │ ↓ └──←──┘ The algorithm is implemented by coding each step as a separate sub-function, and tail-calling from one step to the next. This is as close as we come to branching in D! Notice that nearly all of the primitive and defined functions in [##.assign] deal in matrices - a tribute to APL's native array-handling. The state is represented by 3 matrices at each step: costs: the current cost matrix. zeros: marked zeros: 0-not a zero, 1-unmarked zero, 2-starred, 3-primed. covers: 0-uncovered item, 1-item covered by horizontal (row covering) line, 2-item covered by vertical (column covering) line, 3-item covered by both horizontal and vertical lines. In addition, step 5 takes a boolean matrix left argument, indicating the posit- ion of the first primed zero. Using the example cost matrix from above, the following trace shows the state of play between each step ─[n]─. ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │72 99 88│ │ 0 27 16│ │*0 27 16│ │*0│ 27 16│ │*0│ 27 16│ │23 30 35├[1]┤ 0 7 12├[2]┤ 0 7 12├[3]┤ 0│ 7 12├[4]┤ 0│ 7 12├[6]─·· │51 59 84│ │ 0 8 33│ │ 0 8 33│ │ 0│ 8 33│ │ 0│ 8 33│(7) └──────────┘ └──────────┘ └──────────┘ └──────────┘ └──────────┘ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │*0│ 20 9│ │*0│ 20 9│ │*0 20 9│ │*0│ 20│ 9│ │*0│ 20│ 9│ ··┤ 0│ 0 5├[4]┤ 0│['0] 5├[5]┤ 0 *0 5├[3]┤ 0│ *0│ 5├[4]┤ 0│ *0│ 5├[6]─·· │ 0│ 1 26│ │ 0│ 1 26│ │ 0 1 26│ │ 0│ 1│ 26│ │ 0│ 1│ 26│(5) └──────────┘ └──────────┘ └──────────┘ └──────────┘ └──────────┘ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │*0│ 20│ 4│ │*0│ 20 4│ │*0│ 19 3│ │*0│ 19 3│ │*0 19 3│ ··┤ 0│ *0│ 0├[4]┤ 0┼─*0──'0├[6]┤─1┼─*0──'0├[4]┤─1┼[*0]['0├[5]┤ 1 0 *0├[3]─·· │ 0│ 1│ 21│ │ 0│ 1 21│(1)│ 0│ 0 20│ │ 0│['0] 20│ │ 0 *0 20│ └──────────┘ └──────────┘ └──────────┘ └──────────┘ └──────────┘ ┌──────────┐ │ 1 0 0│ ··┤ 0 0 1│ │ 0 1 0│ └──────────┘ References: H.W.Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2 (1955), pp. 83-97. J.R.Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957) 32-38. Examples: costs ⍝ example cost matrix. 72 99 88 23 30 35 51 59 84 assign costs ⍝ minimum cost assignment. 1 0 0 0 0 1 0 1 0 assign -costs ⍝ maximum benefit assignment. 0 1 0 1 0 0 0 0 1 {+/+/⍵×assign ⍵} costs ⍝ total minimum cost. 166 {+/+/-⍵×assign ⍵} -costs ⍝ total maximum benefit. 206 costs←?6 10⍴50 ⍝ new 6×10 cost matrix. costs 7 38 23 27 11 3 34 34 47 20 26 42 2 3 27 34 1 20 4 21 35 30 47 43 27 5 33 21 36 46 39 14 3 37 17 32 38 50 19 13 50 37 38 33 4 32 45 14 22 39 24 12 14 18 9 25 45 46 4 46 assign costs ⍝ minimum cost assignment. 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 {⍵×assign ⍵} costs ⍝ cost per assignment. 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 {+/+/⍵×assign ⍵} costs ⍝ total minimum cost. 24 assign -costs ⍝ maximum benefit assignment. 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 {-⍵×assign ⍵} -costs ⍝ cost per assignment. 0 0 0 0 0 0 0 0 47 0 0 42 0 0 0 0 0 0 0 0 0 0 47 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 {+/+/-⍵×assign ⍵} -costs ⍝ total maximum benefit. 282 costs←?10 6⍴50 ⍝ new 10×6 cost matrix costs 14 1 21 2 36 47 12 10 16 45 33 8 35 20 20 25 8 30 43 30 48 28 8 50 21 8 29 13 25 24 49 7 10 16 32 7 33 32 41 13 24 20 11 2 46 22 8 48 21 7 45 5 9 4 19 13 7 40 23 18 assign costs ⍝ minimum cost assignment. 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 See also: Graphs X apportion Back to: contents Back to: Workspaces