Macar Algoritması: 0 elementi minimum hatlarla nasıl kaplayabiliriz?

Question

Java'da Macar algoritmasını uygulamaya çalışıyorum. Bir NxN maliyet matrisim var. Adım adım this kılavuzunu takip ediyorum. Bu yüzden costMatrix [N] [N] ve kaplanmış satırları ve kapalı cols'leri takip etmek için 2 diziye sahibim - rowCover [N], rowColumn [N] (1, kapsanan anlamına gelir, 0 anlamında değil)

0'ları nasıl kapatabilirim Minimum hat sayısı ile? Beni doğru yöne yönlendiren var mı?

Herhangi bir yardım/öneri takdir edilecektir.

Answer 1

Kontrol Wikipedia article (section Matrix Interpretation) içinde algoritmasının 3 adım, onlar kapsayacak şekilde çizgilerin asgari tutarı hesaplamak için bir yol açıklamak Tüm 0 '

Güncelleme: aşağıdaki minimum sayıda elde etmek başka bir yoludur

import java.util.ArrayList; 
import java.util.List; 

public class MinLines { 
    enum LineType { NONE, HORIZONTAL, VERTICAL } 

    private static class Line { 
     int lineIndex; 
     LineType rowType; 
     Line(int lineIndex, LineType rowType) { 
      this.lineIndex = lineIndex; 
      this.rowType = rowType; 
     }  
     LineType getLineType() { 
      return rowType; 
     } 

     int getLineIndex() { 
      return lineIndex; 
     } 
     boolean isHorizontal() { 
      return rowType == LineType.HORIZONTAL; 
     } 
    } 

    private static boolean isZero(int[] array) { 
     for (int e : array) { 
      if (e != 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

    public static List<Line> getMinLines(int[][] matrix) { 
     if (matrix.length != matrix[0].length) { 
      throw new IllegalArgumentException("Matrix should be square!"); 
     } 

     final int SIZE = matrix.length; 
     int[] zerosPerRow = new int[SIZE]; 
     int[] zerosPerCol = new int[SIZE]; 

     // Count the number of 0's per row and the number of 0's per column   
     for (int i = 0; i < SIZE; i++) { 
      for (int j = 0; j < SIZE; j++) { 
       if (matrix[i][j] == 0) { 
        zerosPerRow[i]++; 
        zerosPerCol[j]++; 
       } 
      } 
     } 

     // There should be at must SIZE lines, 
     // initialize the list with an initial capacity of SIZE 
     List<Line> lines = new ArrayList<Line>(SIZE); 

     LineType lastInsertedLineType = LineType.NONE; 

     // While there are 0's to count in either rows or colums... 
     while (!isZero(zerosPerRow) && !isZero(zerosPerCol)) { 
      // Search the largest count of 0's in both arrays 
      int max = -1; 
      Line lineWithMostZeros = null; 
      for (int i = 0; i < SIZE; i++) { 
       // If exists another count of 0's equal to "max" but in this one has 
       // the same direction as the last added line, then replace it with this 
       // 
       // The heuristic "fixes" the problem reported by @JustinWyss-Gallifent and @hkrish 
       if (zerosPerRow[i] > max || (zerosPerRow[i] == max && lastInsertedLineType == LineType.HORIZONTAL)) { 
        lineWithMostZeros = new Line(i, LineType.HORIZONTAL); 
        max = zerosPerRow[i]; 
       } 
      } 

      for (int i = 0; i < SIZE; i++) { 
       // Same as above 
       if (zerosPerCol[i] > max || (zerosPerCol[i] == max && lastInsertedLineType == LineType.VERTICAL)) { 
        lineWithMostZeros = new Line(i, LineType.VERTICAL); 
        max = zerosPerCol[i]; 
       } 
      } 

      // Delete the 0 count from the line 
      if (lineWithMostZeros.isHorizontal()) { 
       zerosPerRow[lineWithMostZeros.getLineIndex()] = 0; 
      } else { 
       zerosPerCol[lineWithMostZeros.getLineIndex()] = 0; 
      } 

      // Once you've found the line (either horizontal or vertical) with the greater 0's count 
      // iterate over it's elements and substract the 0's from the other lines 
      // Example: 
      //       0's x col: 
      //   [ 0 1 2 3 ] -> 1 
      //   [ 0 2 0 1 ] -> 2 
      //   [ 0 4 3 5 ] -> 1 
      //   [ 0 0 0 7 ] -> 3 
      //    | | | | 
      //    v v v v 
      // 0's x row: {4} 1 2 0 

      //   [ X 1 2 3 ] -> 0 
      //   [ X 2 0 1 ] -> 1 
      //   [ X 4 3 5 ] -> 0 
      //   [ X 0 0 7 ] -> 2 
      //    | | | | 
      //    v v v v 
      //   {0} 1 2 0 

      int index = lineWithMostZeros.getLineIndex(); 
      if (lineWithMostZeros.isHorizontal()) { 
       for (int j = 0; j < SIZE; j++) { 
        if (matrix[index][j] == 0) { 
         zerosPerCol[j]--; 
        } 
       } 
      } else { 
       for (int j = 0; j < SIZE; j++) { 
        if (matrix[j][index] == 0) { 
         zerosPerRow[j]--; 
        } 
       }      
      } 

      // Add the line to the list of lines 
      lines.add(lineWithMostZeros); 
      lastInsertedLineType = lineWithMostZeros.getLineType(); 
     } 
     return lines; 
    } 

    public static void main(String... args) { 
     int[][] example1 = 
     { 
      {0, 1, 0, 0, 5}, 
      {1, 0, 3, 4, 5}, 
      {7, 0, 0, 4, 5}, 
      {9, 0, 3, 4, 5}, 
      {3, 0, 3, 4, 5} 
     }; 

     int[][] example2 = 
     { 
      {0, 0, 1, 0}, 
      {0, 1, 1, 0}, 
      {1, 1, 0, 0}, 
      {1, 0, 0, 0}, 
     }; 

     int[][] example3 = 
     { 
      {0, 0, 0, 0, 0, 0}, 
      {0, 0, 0, 1, 0, 0}, 
      {0, 0, 1, 1, 0, 0}, 
      {0, 1, 1, 0, 0, 0}, 
      {0, 1, 0, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0} 
     }; 

     List<int[][]> examples = new ArrayList<int[][]>(); 
     examples.add(example1); 
     examples.add(example2); 
     examples.add(example3); 

     for (int[][] example : examples) { 
      List<Line> minLines = getMinLines(example); 
      System.out.printf("Min num of lines for example matrix is: %d\n", minLines.size()); 
      printResult(example, minLines); 
      System.out.println(); 
     } 
    } 

    private static void printResult(int[][] matrix, List<Line> lines) { 
     if (matrix.length != matrix[0].length) { 
      throw new IllegalArgumentException("Matrix should be square!"); 
     } 

     final int SIZE = matrix.length; 
     System.out.println("Before:"); 
     for (int i = 0; i < SIZE; i++) { 
      for (int j = 0; j < SIZE; j++) { 
       System.out.printf("%d ", matrix[i][j]); 
      } 
      System.out.println(); 
     } 

     for (Line line : lines) { 
      for (int i = 0; i < SIZE; i++) { 
       int index = line.getLineIndex(); 
       if (line.isHorizontal()) { 
        matrix[index][i] = matrix[index][i] < 0 ? -3 : -1; 
       } else { 
        matrix[i][index] = matrix[i][index] < 0 ? -3 : -2; 
       } 
      } 
     } 

     System.out.println("\nAfter:"); 
     for (int i = 0; i < SIZE; i++) { 
      for (int j = 0; j < SIZE; j++) { 
       System.out.printf("%s ", matrix[i][j] == -1 ? "-" : (matrix[i][j] == -2 ? "|" : (matrix[i][j] == -3 ? "+" : Integer.toString(matrix[i][j])))); 
      } 
      System.out.println(); 
     } 
    } 
} 

önemli bir parçası matris 0's girişleri kapsayacak hatları ile List döndürür getMinLines yöntemdir: 0's kapak hatları. örnek baskılar matrisler için:

Min num of lines for example matrix is: 3 
Before: 
0 1 0 0 5 
1 0 3 4 5 
7 0 0 4 5 
9 0 3 4 5 
3 0 3 4 5 

After: 
- + - - - 
1 | 3 4 5 
- + - - - 
9 | 3 4 5 
3 | 3 4 5 

Min num of lines for example matrix is: 4 
Before: 
0 0 1 0 
0 1 1 0 
1 1 0 0 
1 0 0 0 

After: 
| | | | 
| | | | 
| | | | 
| | | | 

Min num of lines for example matrix is: 6 
Before: 
0 0 0 0 0 0 
0 0 0 1 0 0 
0 0 1 1 0 0 
0 1 1 0 0 0 
0 1 0 0 0 0 
0 0 0 0 0 0 

After: 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - - 
- - - - - -  

bu sana bu soruyu uzun zaman önce çözüldüğünü biliyoruz

Answer 2

uygulamak için bir destek, zor olmamalı Macar algoritması kalanını vermek umuyor, ancak 3. adım için uygulamamı paylaşmak istiyorum, burada minimum satırlar, tüm sıfırlar kaplanacak şekilde çizilmelidir.

İşte bu adım için benim algoritması nasıl çalıştığına dair kısa bir açıklama yapalım: bütün hücreler üzerinde

• Döngü, bir değeri sıfır hücre, biz onun tarafından bir çizgi geçen çizmek gerekir ve komşuları
• Çizginin hangi yöne çekileceğini bilmek için, dik ve yatay olarak sıfırları sayacak ve tamsayı döndüren maxVH() adında bir yöntem oluşturdum. Tamsayı pozitif ise, dikey çizgi çizin, aksi takdirde sıfır veya negatif ise yatay çizgi çizin.
• colorNeighbors() yöntemi çizgileri çizer ve bunları da sayar. Ayrıca, hattın dikey olarak geçtiği elemanlara 1 yerleştirilecektir. Hattın yatay olarak geçtiği elemanlarda -1. 2 kesişen çizginin geçtiği elemanlarda (yatay ve dikey).

Bu 3 yönteme sahip olmanın avantajı, iki kez kapsanan elemanları bildiğimiz, hangi elemanların kaplandığını ve kapsanmadığını bildiğimizdir. Ek olarak, çizgiler çizilirken, satır sayacı artar. Macar Algoritması + Örnek tam olarak uygulanması için

: Github

Kodu + Detaylı Yorumlar adım 3 için:

/** 
    * Step 3.1 
    * Loop through all elements, and run colorNeighbors when the element visited is equal to zero 
    * */ 
    public void coverZeros(){ 
     numLines = 0; 
     lines = new int[values.length][values.length]; 

     for(int row=0; row<values.length;row++){ 
      for(int col=0; col<values.length;col++){ 
       if(values[row][col] == 0) 
        colorNeighbors(row, col, maxVH(row, col)); 
      } 
     } 
    } 

    /** 
    * Step 3.2 
    * Checks which direction (vertical,horizontal) contains more zeros, every time a zero is found vertically, we increment the result 
    * and every time a zero is found horizontally, we decrement the result. At the end, result will be negative, zero or positive 
    * @param row Row index for the target cell 
    * @param col Column index for the target cell 
    * @return Positive integer means that the line passing by indexes [row][col] should be vertical, Zero or Negative means that the line passing by indexes [row][col] should be horizontal 
    * */ 
    private int maxVH(int row, int col){ 
     int result = 0; 
     for(int i=0; i<values.length;i++){ 
      if(values[i][col] == 0) 
       result++; 
      if(values[row][i] == 0) 
       result--; 
     } 
     return result; 
    } 

    /** 
    * Step 3.3 
    * Color the neighbors of the cell at index [row][col]. To know which direction to draw the lines, we pass maxVH value. 
    * @param row Row index for the target cell 
    * @param col Column index for the target cell 
    * @param maxVH Value return by the maxVH method, positive means the line to draw passing by indexes [row][col] is vertical, negative or zero means the line to draw passing by indexes [row][col] is horizontal 
    * */ 
    private void colorNeighbors(int row, int col, int maxVH){ 
     if(lines[row][col] == 2) // if cell is colored twice before (intersection cell), don't color it again 
      return; 

     if(maxVH > 0 && lines[row][col] == 1) // if cell colored vertically and needs to be recolored vertically, don't color it again (Allowing this step, will color the same line (result won't change), but the num of line will be incremented (wrong value for the num of line drawn)) 
      return; 

     if(maxVH <= 0 && lines[row][col] == -1) // if cell colored horizontally and needs to be recolored horizontally, don't color it again (Allowing this step, will color the same line (result won't change), but the num of line will be incremented (wrong value for the num of line drawn)) 
      return; 

     for(int i=0; i<values.length;i++){ // Loop on cell at indexes [row][col] and its neighbors 
      if(maxVH > 0) // if value of maxVH is positive, color vertically 
       lines[i][col] = lines[i][col] == -1 || lines[i][col] == 2 ? 2 : 1; // if cell was colored before as horizontal (-1), and now needs to be colored vertical (1), so this cell is an intersection (2). Else if this value was not colored before, color it vertically 
      else   // if value of maxVH is zero or negative color horizontally 
       lines[row][i] = lines[row][i] == 1 || lines[row][i] == 2 ? 2 : -1; // if cell was colored before as vertical (1), and now needs to be colored horizontal (-1), so this cell is an intersection (2). Else if this value was not colored before, color it horizontally 
     } 

     // increment line number 
     numLines++; 
//  printMatrix(lines); // Monitor the line draw steps 
    }//End step 3