Реализации алгоритмов/Венгерский алгоритм

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время.

Java

Реализация Венгерского алгоритма с временной сложность O(n³) для задачи о назначениях (минимизация стоимости). Предполагается, что матрица является квадратной. Код для проверки этого может быть легко добавлен в конструктор. Вызов code>new Hungarian(costMatrix).execute() возвращает двумерный массив, где result[i][0] и result[i][1] — индексы строки и столбца назначения i. Алгоритм работает за время O(n³) (или, по крайней мере, так должно быть) и использует O(n²) памяти, улучшаемо^[1]:

mport java.util.ArrayList;

public class Hungarian {

   private int numRows;
   private int numCols;

   private boolean[][] primes;
   private boolean[][] stars;
   private boolean[] rowsCovered;
   private boolean[] colsCovered;
   private float[][] costs;

   public Hungarian(float theCosts[][]) {
      costs = theCosts;
      numRows = costs.length;
      numCols = costs[0].length;

      primes = new boolean[numRows][numCols];
      stars = new boolean[numRows][numCols];

      // Инициализация массивов с покрытием строк/столбцов
      rowsCovered = new boolean[numRows];
      colsCovered = new boolean[numCols];
      for(int i = 0; i < numRows; i++) {
         rowsCovered[i] = false;
      }
      for(int j = 0; j < numCols; j++) {
         colsCovered[j] = false;
      }
      // Инициализация матриц
      for(int i = 0; i < numRows; i++) {
         for(int j = 0; j < numCols; j++) {
            primes[i][j] = false;
            stars[i][j] = false;
         }
      }
   }

   public int[][] execute() {
      subtractRowColMins();

      this.findStars(); // O(n^2)
      this.resetCovered(); // O(n);
      this.coverStarredZeroCols(); // O(n^2)

      while(!allColsCovered()) { 
         int[] primedLocation = this.primeUncoveredZero(); // O(n^2)

         // It's possible that we couldn't find a zero to prime, so we have to induce some zeros so we can find one to prime
         if(primedLocation[0] == -1) {  
            this.minUncoveredRowsCols(); // O(n^2)
            primedLocation = this.primeUncoveredZero(); // O(n^2)
         }

         // is there a starred 0 in the primed zeros row?
         int primedRow = primedLocation[0];
         int starCol = this.findStarColInRow(primedRow);
         if(starCol != -1) {
            // cover ther row of the primedLocation and uncover the star column
            rowsCovered[primedRow] = true;
            colsCovered[starCol] = false;
         }
         else { // otherwise we need to find an augmenting path and start over.
            this.augmentPathStartingAtPrime(primedLocation);
            this.resetCovered();
            this.resetPrimes();
            this.coverStarredZeroCols();
         }
      }

      return this.starsToAssignments(); // O(n^2)

   }

   /*
    * the starred 0's in each column are the assignments.
    * O(n^2)
    */
   public int[][] starsToAssignments() {
      int[][] toRet = new int[numCols][];
      for(int j = 0; j < numCols; j++) {
         toRet[j] = new int[]{this.findStarRowInCol(j), j}; // O(n)
      }
      return toRet;
   }

   /*
    * resets prime information
    */
   public void resetPrimes() {
      for(int i = 0; i < numRows; i++) {
         for(int j = 0; j < numCols; j++) {
            primes[i][j] = false;
         }
      }
   }


   /*
    * resets covered information, O(n)
    */
   public void resetCovered() {
      for(int i = 0; i < numRows; i++) {
         rowsCovered[i] = false;
      }
      for(int j = 0; j < numCols; j++) {
         colsCovered[j] = false;
      }
   }

   /*
    * get the first zero in each column, star it if there isn't already a star in that row
    * cover the row and column of the star made, and continue to the next column
    * O(n^2)
    */
   public void findStars() {
      boolean[] rowStars = new boolean[numRows];
      boolean[] colStars = new boolean[numCols];

      for(int i = 0; i < numRows; i++) {
         rowStars[i] = false;
      }
      for(int j = 0; j < numCols; j++) {
         colStars[j] = false;
      }

      for(int j = 0; j < numCols; j++) {
         for(int i = 0; i < numRows; i++) {
            if(costs[i][j] == 0 && !rowStars[i] && !colStars[j]) {
               stars[i][j] = true;
               rowStars[i] = true;
               colStars[j] = true;
               break;
            }
         }
      }
   }

   /*
    * Finds the minimum uncovered value, and adds it to all the covered rows then
    * subtracts it from all the uncovered columns. This results in a cost matrix with
    * at least one more zero.
    */
   private void minUncoveredRowsCols() { 
      // find min uncovered value
      float minUncovered = Float.MAX_VALUE;
      for(int i = 0; i < numRows; i++) {
         if(!rowsCovered[i]) {
            for(int j = 0; j < numCols; j++) {
               if(!colsCovered[j]) {
                  if(costs[i][j] < minUncovered) {
                     minUncovered = costs[i][j];
                  }
               }
            }
         }
      }

      // add that value to all the COVERED rows.
      for(int i = 0; i < numRows; i++) {
         if(rowsCovered[i]) {
            for(int j = 0; j < numCols; j++) {
               costs[i][j] = costs[i][j] + minUncovered;

            }
         }
      }

      // subtract that value from all the UNcovered columns
      for(int j = 0; j < numCols; j++) {
         if(!colsCovered[j]) {
            for(int i = 0; i < numRows; i++) {
               costs[i][j] = costs[i][j] - minUncovered;
            }
         }
      }
   }

   /*
    * Finds an uncovered zero, primes it, and returns an array
    * describing the row and column of the newly primed zero.
    * If no uncovered zero could be found, returns -1 in the indices.
    * O(n^2)
    */
   private int[] primeUncoveredZero() { 
      int[] location = new int[2];

      for(int i = 0; i < numRows; i++) {
         if(!rowsCovered[i]) {
            for(int j = 0; j < numCols; j++) {
               if(!colsCovered[j]) {
                  if(costs[i][j] == 0) {
                     primes[i][j] = true;
                     location[0] = i;
                     location[1] = j;
                     return location;
                  }
               }
            }
         }
      }

      location[0] = -1;
      location[1] = -1;
      return location;
   }

   /*
    * Starting at a given primed location[0=row,1=col], we find an augmenting path
    * consisting of a primed , starred , primed , ..., primed. (note that it begins and ends with a prime)
    * We do this by starting at the location, going to a starred zero in the same column, then going to a primed zero in
    * the same row, etc, until we get to a prime with no star in the column.
    * O(n^2)
    */
   private void augmentPathStartingAtPrime(int[] location) {
      // Make the arraylists sufficiently large to begin with
      ArrayList<int[]> primeLocations = new ArrayList<int[]>(numRows+numCols);
      ArrayList<int[]> starLocations = new ArrayList<int[]>(numRows+numCols);
      primeLocations.add(location);

      int currentRow = location[0];
      int currentCol = location[1];
      while(true) { // add stars and primes in pairs
         int starRow = findStarRowInCol(currentCol);
         // at some point we won't be able to find a star. if this is the case, break.
         if(starRow == -1) {break;}
         int[] starLocation = new int[]{starRow, currentCol};
         starLocations.add(starLocation);
         currentRow = starRow;

         int primeCol = findPrimeColInRow(currentRow);
         int[] primeLocation = new int[]{currentRow, primeCol};
         primeLocations.add(primeLocation);
         currentCol = primeCol;
      }

      unStarLocations(starLocations);
      starLocations(primeLocations);
   }


   /*
    * Given an arraylist of  locations, star them
    */
   private void starLocations(ArrayList<int[]> locations) {
      for(int k = 0; k < locations.size(); k++) {
         int[] location = locations.get(k);
         int row = location[0];
         int col = location[1];
         stars[row][col] = true;
      }
   }

   /*
    * Given an arraylist of starred locations, unstar them
    */
   private void unStarLocations(ArrayList<int[]> starLocations) {
      for(int k = 0; k < starLocations.size(); k++) {
         int[] starLocation = starLocations.get(k);
         int row = starLocation[0];
         int col = starLocation[1];
         stars[row][col] = false;
      }
   }


   /*
    * Given a row index, finds a column with a prime. returns -1 if this isn't possible.
    */
   private int findPrimeColInRow(int theRow) {
      for(int j = 0; j < numCols; j++) {
         if(primes[theRow][j]) {
            return j;
         }
      }
      return -1;
   }




   /*
    * Given a column index, finds a row with a star. returns -1 if this isn't possible.
    */
   public int findStarRowInCol(int theCol) {
      for(int i = 0; i < numRows; i++) {
         if(stars[i][theCol]) {
            return i;
         }
      }
      return -1;
   }


   public int findStarColInRow(int theRow) {
      for(int j = 0; j < numCols; j++) {
         if(stars[theRow][j]) {
            return j;
         }
      }
      return -1;
   }

   // looks at the colsCovered array, and returns true if all entries are true, false otherwise
   private boolean allColsCovered() {
      for(int j = 0; j < numCols; j++) {
         if(!colsCovered[j]) {
            return false;
         }
      }
      return true;
   }

   /*
    * sets the columns covered if they contain starred zeros
    * O(n^2)
    */
   private void coverStarredZeroCols() {
      for(int j = 0; j < numCols; j++) {
         colsCovered[j] = false;
         for(int i = 0; i < numRows; i++) {
            if(stars[i][j]) {
               colsCovered[j] = true;
               break; // break inner loop to save a bit of time
            }
         }
      }
   }

   private void subtractRowColMins() { 
      for(int i = 0; i < numRows; i++) {//for each row
         float rowMin = Float.MAX_VALUE;
         for(int j = 0; j < numCols; j++) { // grab the smallest element in that row
            if(costs[i][j] < rowMin) {
               rowMin = costs[i][j];
            }
         }
         for(int j = 0; j < numCols; j++) { // subtract that from each element
            costs[i][j] = costs[i][j] - rowMin;
         }
      }

      for(int j = 0; j < numCols; j++) { // for each col
         float colMin = Float.MAX_VALUE;
         for(int i = 0; i < numRows; i++) { // grab the smallest element in that column
            if(costs[i][j] < colMin) {
               colMin = costs[i][j];
            }
         }
         for(int i = 0; i < numRows; i++) { // subtract that from each element
            costs[i][j] = costs[i][j] - colMin;
         }
      }
   }

}

Примечания

↑ Shawn O'Neil An implimentation of the O(n^3) Hungarian method for the minimum cost assignment problem

Ссылки

Не все перечисленные ниже реализации удовлетворяют ограничению времени исполнения $O(n^{3})$ .

[1] Shawn O'Neil An implimentation of the O(n^3) Hungarian method for the minimum cost assignment problem

[1]