next up previous contents index
Next: 9.8.3 The Concurrent Algorithm Up: 9.8 Munkres Algorithm for Previous: 9.8.1 Introduction

9.8.2 The Sequential Algorithm

 

The input to the assignment problem is the matrix of dissimilarities from Equation 9.19. The first point to note is that the particular assignment which minimizes Equation 9.21 is not altered if a fixed value is added to or subtracted from all entries in any row or column of the cost matrix D. Exploiting this fact, Munkres' solution to the assignment problem can be divided into two parts

M1:
Modifications of the distance matrix D by row/column subtractions, creating a (large) number of zero entries.
M2:
With denoting the row indices of all zeros in column i, construction of a so-called minimal representative set, meaning a distinct selection for each i, such that .

The steps of Munkres algorithm generally follow those in the constructive proof of P. Hall's theorem on minimal representative sets.

The preceding paragraph provides a hopelessly incomplete hint as to the number theoretic basis for Munkres algorithm. The particular implementation of Munkres algorithm used in this work is as described in Chapter 14 of [Blackman:86a]. To be definite, take and let the columns of the distance matrix be associated with items from list . The first step is to subtract the smallest item in each column from all entries in the column. The rest of the algorithm can be viewed as a search for special zero entries (starred zeros ), and proceeds as follows:

Munkres Algorithm

Step 1:
Setup
  1. Find a zero Z in the distance matrix.
  2. If there is no starred zero already in its row or column, star this zero.
  3. Repeat steps 1.1, 1.2 until all zeros have been considered.
Step 2:
Count, Solution Assessment
  1. Cover every column containing a .
  2. Terminate the algorithm if all columns are covered. In this case, the locations of the entries in the matrix provide the solution to the assignment problem.
Step 3:
Main Zero Search
  1. Find an uncovered Z in the distance matrix and prime it, . If no such zero exists, go to Step 5
  2. If No exists in the row of the , go to Step 4.
  3. If a exists, cover this row and uncover the column of the . Return to Step 3.1 to find a new Z.
Step 4:
Increment Set of Starred Zeros
  1. Construct the ``alternating sequence'' of primed and starred zeros:
    : Unpaired from Step 3.2
    : The in the column of
    : The in the row of , if such a zero exists
    : The in the column of

    The sequence eventually terminates with an unpaired for some N.
  2. Unstar each starred zero of the sequence.
  3. Star each primed zero of the sequence, thus increasing the number of starred zeros by one.
  4. Erase all primes, uncover all columns and rows, and return to Step 2.
Step 5:
New Zero Manufactures
  1. Let h be the smallest uncovered entry in the (modified) distance matrix.
  2. Add h to all covered rows.
  3. Subtract h from all uncovered columns
  4. Return to Step 3, without altering stars, primes, or covers.

A (very) schematic flowchart for the algorithm is shown in Figure 9.19. Note that Steps 1,5 of the algorithm overwrite the original distance matrix.

The preceding algorithm involves flags (starred or primed) associated with zero entries in the distance matrix, as well as ``covered'' tags associated with individual rows and columns. The implementation of the zero tagging is done by first noting that there is at most one or in any row or column. The covers and zero tags of the algorithm are accordingly implemented using five simple arrays:

CC:
Covered column tags, .
CR:
Covered row tags,
ZS:
locators for columns of the matrix. If positive, ZS is the row index of the in the column of the matrix.
ZR:
locators for rows of the matrix. If positive, ZR is the column of the in the row of the matrix.
ZP:
locators for rows of the matrix. If positive, ZP is the column of the in the row of the matrix.

  
Figure 9.19: Flowchart for Munkres Algorithm

Entries in the cover arrays CC and CR are one if the row or column is covered zero otherwise. Entries in the zero-locator arrays ZS, ZR, and ZP are zero if no zero of the appropriate type exists in the indexed row or column.

With the star-prime-cover scheme of the preceding paragraph, a sequential implementation of Munkres algorithm is completely straightforward. At the beginning of Step 1, all cover and locator flags are set to zero, and the initial zero search provides an initial set of nonzero entries in ZS(). Step 2 sets appropriate entries in CC() to one and simply counts the covered columns. Steps 3 and 5 are trivially implemented in terms of the cover/zero arrays and the ``alternating sequence'' for Step 4 is readily constructed from the contents of ZS(), ZR() and ZP().

As an initial exploration of Munkres algorithm, consider the task of associating two lists of random points within a 2D unit square, assuming the cost function in Equation 9.19 is the usual Cartesian  distance. Figure 9.20 plots total CPU times for execution of Munkres algorithm for equal size lists versus list size. The vertical axis gives CPU times in seconds for one node of the Mark III hypercube. The circles and crosses show the time spent in Steps 5 and 3, respectively. These two steps (zero search and zero manufacture) account for essentially all of the CPU time. For the case, the total CPU time spent in Step 2 was about , and that spent in Step 4 was too small to be reliably measured. The large amounts of time spent in Steps 3 and 5 arise from the very large numbers of times these parts of the algorithm are executed. The case involves 6109 entries into Step 3 and 593 entries into Step 5.

Since the zero searching in Step 3 of the algorithm is required so often, the implementation of this step is done with some care. The search for zeros is done column-by-column, and the code maintains pointers to both the last column searched and the most recently uncovered column (Step 3.3) in order to reduce the time spent on subsequent re-entries to the Step 3 box of Figure 9.19.

  
Figure 9.20: Timing Results for the Sequential Algorithm Versus Problem Size

The dashed line of Figure 9.20 indicates the nominal scaling predicted for Munkres algorithm. By and large, the timing results in Figure 9.20 are consistent with this expected behavior. It should be noted, however, that both the nature of this scaling and the coefficient of are very dependent on the nature of the data sets. Consider, for example, two identical trivial lists

 

with the distance between items given by the absolute value function. For the data sets in Equation 9.22, the preliminaries and Step 1 of Munkres algorithm completely solve the association in a time which scales as . In contrast, the random-point association problem is a much greater challenge for the algorithm, as nominal pairings indicated by the initial nearest-neighbor searches of the preliminary step are tediously undone in the creation of the staircaselike sequence of zeros needed for Step 4. As a brief, instructive illustration of the nature of this processing, Figure 9.21 plots the CPU time per step for the last passes through the outer loop of Figure 9.19 for the 150150 assignment problem (recall that each pass through the outer loop increases the count by one). The processing load per step is seen to be highly nonuniform.

  
Figure 9.21: Times Per Loop (i.e., increment) for the Last Several Loops in the Solution of the Problem



next up previous contents index
Next: 9.8.3 The Concurrent Algorithm Up: 9.8 Munkres Algorithm for Previous: 9.8.1 Introduction



Guy Robinson
Wed Mar 1 10:19:35 EST 1995