algorithm हंगेरियन एल्गोरिदम: शून्य को कवर करने के लिए लाइनों की न्यूनतम संख्या खोजना?




matrix matching (4)

चरण 5: मैट्रिक्स में रेखा का चित्रण मैट्रिक्स की लंबाई के अधिकतम मूल्यांकन के साथ तिरछे मूल्यांकन किया जाता है।

Http://www.wikihow.com/Use-the- हंगेरी- एल्गोरिदम के आधार पर केवल चरण 1 - 8 के आधार पर।

कोड स्निपेट चलाएं और परिणाम कंसोल में देखें

कंसोल आउटपुट

horizontal line (row): {"0":0,"2":2,"4":4}
vertical line (column): {"2":2}

Step 5: Matrix
0  1  0  1  1  
1  1  0  1  1  
1  0  0  0  1  
1  1  0  1  1  
1  0  0  1  0  

Smallest number in uncovered matrix: 1
Step 6: Matrix
x  x  x  x  x  
1  1  x  1  1  
x  x  x  x  x  
1  1  x  1  1  
x  x  x  x  x

JSFiddle: http://jsfiddle.net/jjcosare/6Lpz5gt9/2/

// http://www.wikihow.com/Use-the-Hungarian-Algorithm

var inputMatrix = [
  [0, 1, 0, 1, 1],
  [1, 1, 0, 1, 1],
  [1, 0, 0, 0, 1],
  [1, 1, 0, 1, 1],
  [1, 0, 0, 1, 0]
];

//var inputMatrix = [
//      [10, 19, 8, 15],
//      [10, 18, 7, 17],
//      [13, 16, 9, 14],
//      [12, 19, 8, 18],
//      [14, 17, 10, 19]
//    ];

var matrix = inputMatrix;
var HungarianAlgorithm = {};

HungarianAlgorithm.step1 = function(stepNumber) {

  console.log("Step " + stepNumber + ": Matrix");

  var currentNumber = 0;
  for (var i = 0; i < matrix.length; i++) {
    var sb = "";
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[i][j];
      sb += currentNumber + "  ";
    }
    console.log(sb);
  }
}

HungarianAlgorithm.step2 = function() {
  var largestNumberInMatrix = getLargestNumberInMatrix(matrix);
  var rowLength = matrix.length;
  var columnLength = matrix[0].length;
  var dummyMatrixToAdd = 0;
  var isAddColumn = rowLength > columnLength;
  var isAddRow = columnLength > rowLength;

  if (isAddColumn) {
    dummyMatrixToAdd = rowLength - columnLength;
    for (var i = 0; i < rowLength; i++) {
      for (var j = columnLength; j < (columnLength + dummyMatrixToAdd); j++) {
        matrix[i][j] = largestNumberInMatrix;
      }
    }
  } else if (isAddRow) {
    dummyMatrixToAdd = columnLength - rowLength;
    for (var i = rowLength; i < (rowLength + dummyMatrixToAdd); i++) {
      matrix[i] = [];
      for (var j = 0; j < columnLength; j++) {
        matrix[i][j] = largestNumberInMatrix;
      }
    }
  }

  HungarianAlgorithm.step1(2);
  console.log("Largest number in matrix: " + largestNumberInMatrix);

  function getLargestNumberInMatrix(matrix) {
    var largestNumberInMatrix = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      for (var j = 0; j < matrix[i].length; j++) {
        currentNumber = matrix[i][j];
        largestNumberInMatrix = (largestNumberInMatrix > currentNumber) ?
          largestNumberInMatrix : currentNumber;
      }
    }
    return largestNumberInMatrix;
  }
}

HungarianAlgorithm.step3 = function() {
  var smallestNumberInRow = 0;
  var currentNumber = 0;

  for (var i = 0; i < matrix.length; i++) {
    smallestNumberInRow = getSmallestNumberInRow(matrix, i);
    console.log("Smallest number in row[" + i + "]: " + smallestNumberInRow);
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[i][j];
      matrix[i][j] = currentNumber - smallestNumberInRow;
    }
  }

  HungarianAlgorithm.step1(3);

  function getSmallestNumberInRow(matrix, rowIndex) {
    var smallestNumberInRow = matrix[rowIndex][0];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      smallestNumberInRow = (smallestNumberInRow < currentNumber) ?
        smallestNumberInRow : currentNumber;
    }
    return smallestNumberInRow;
  }
}

HungarianAlgorithm.step4 = function() {
  var smallestNumberInColumn = 0;
  var currentNumber = 0;

  for (var i = 0; i < matrix.length; i++) {
    smallestNumberInColumn = getSmallestNumberInColumn(matrix, i);
    console.log("Smallest number in column[" + i + "]: " + smallestNumberInColumn);
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[j][i];
      matrix[j][i] = currentNumber - smallestNumberInColumn;
    }
  }

  HungarianAlgorithm.step1(4);

  function getSmallestNumberInColumn(matrix, columnIndex) {
    var smallestNumberInColumn = matrix[0][columnIndex];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      smallestNumberInColumn = (smallestNumberInColumn < currentNumber) ?
        smallestNumberInColumn : currentNumber;
    }
    return smallestNumberInColumn;
  }
}

var rowLine = {};
var columnLine = {};
HungarianAlgorithm.step5 = function() {
  var zeroNumberCountRow = 0;
  var zeroNumberCountColumn = 0;

  rowLine = {};
  columnLine = {};
  for (var i = 0; i < matrix.length; i++) {
    zeroNumberCountRow = getZeroNumberCountInRow(matrix, i);
    zeroNumberCountColumn = getZeroNumberCountInColumn(matrix, i);
    if (zeroNumberCountRow > zeroNumberCountColumn) {
      rowLine[i] = i;
      if (zeroNumberCountColumn > 1) {
        columnLine[i] = i;
      }
    } else if (zeroNumberCountRow < zeroNumberCountColumn) {
      columnLine[i] = i;
      if (zeroNumberCountRow > 1) {
        rowLine[i] = i;
      }
    } else {
      if ((zeroNumberCountRow + zeroNumberCountColumn) > 2) {
        rowLine[i] = i;
        columnLine[i] = i;
      }
    }
  }

  var zeroCount = 0;
  for (var i in columnLine) {
    zeroCount = getZeroNumberCountInColumnLine(matrix, columnLine[i], rowLine);
    if (zeroCount == 0) {
      delete columnLine[i];
    }
  }
  for (var i in rowLine) {
    zeroCount = getZeroNumberCountInRowLine(matrix, rowLine[i], columnLine);
    if (zeroCount == 0) {
      delete rowLine[i];
    }
  }

  console.log("horizontal line (row): " + JSON.stringify(rowLine));
  console.log("vertical line (column): " + JSON.stringify(columnLine));

  HungarianAlgorithm.step1(5);

  //if ((Object.keys(rowLine).length + Object.keys(columnLine).length) == matrix.length) {
    // TODO:
    // HungarianAlgorithm.step9();
  //} else {
  //  HungarianAlgorithm.step6();
  //  HungarianAlgorithm.step7();
  //  HungarianAlgorithm.step8();
  //}

  function getZeroNumberCountInColumnLine(matrix, columnIndex, rowLine) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      if (currentNumber == 0 && !(rowLine[i] == i)) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInRowLine(matrix, rowIndex, columnLine) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      if (currentNumber == 0 && !(columnLine[i] == i)) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInColumn(matrix, columnIndex) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      if (currentNumber == 0) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInRow(matrix, rowIndex) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      if (currentNumber == 0) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }
}

HungarianAlgorithm.step6 = function() {
  var smallestNumberInUncoveredMatrix = getSmallestNumberInUncoveredMatrix(matrix, rowLine, columnLine);
  console.log("Smallest number in uncovered matrix: " + smallestNumberInUncoveredMatrix);

  var columnIndex = 0;
  for (var i in columnLine) {
    columnIndex = columnLine[i];
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      //matrix[i][columnIndex] = currentNumber + smallestNumberInUncoveredMatrix;
      matrix[i][columnIndex] = "x";
    }
  }

  var rowIndex = 0;
  for (var i in rowLine) {
    rowIndex = rowLine[i];
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      //matrix[rowIndex][i] = currentNumber + smallestNumberInUncoveredMatrix;
      matrix[rowIndex][i] = "x";
    }
  }

  HungarianAlgorithm.step1(6);

  function getSmallestNumberInUncoveredMatrix(matrix, rowLine, columnLine) {
    var smallestNumberInUncoveredMatrix = null;;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      if (rowLine[i]) {
        continue;
      }
      for (var j = 0; j < matrix[i].length; j++) {
        if (columnLine[j]) {
          continue;
        }

        currentNumber = matrix[i][j];
        if (!smallestNumberInUncoveredMatrix) {
          smallestNumberInUncoveredMatrix = currentNumber;
        }

        smallestNumberInUncoveredMatrix =
          (smallestNumberInUncoveredMatrix < currentNumber) ?
          smallestNumberInUncoveredMatrix : currentNumber;
      }
    }
    return smallestNumberInUncoveredMatrix;
  }
}

HungarianAlgorithm.step7 = function() {
  var smallestNumberInMatrix = getSmallestNumberInMatrix(matrix);
  console.log("Smallest number in matrix: " + smallestNumberInMatrix);

  var currentNumber = 0;
  for (var i = 0; i < matrix.length; i++) {
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[j][i];
      matrix[j][i] = currentNumber - smallestNumberInMatrix;
    }
  }

  HungarianAlgorithm.step1(7);

  function getSmallestNumberInMatrix(matrix) {
    var smallestNumberInMatrix = matrix[0][0];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      for (var j = 0; j < matrix[i].length; j++) {
        currentNumber = matrix[i][j];
        smallestNumberInMatrix = (smallestNumberInMatrix < currentNumber) ?
          smallestNumberInMatrix : currentNumber;
      }
    }
    return smallestNumberInMatrix;
  }
}

HungarianAlgorithm.step8 = function() {
  console.log("Step 8: Covering zeroes with Step 5 - 8 until Step 9 is reached");
  HungarianAlgorithm.step5();
}

HungarianAlgorithm.step9 = function(){
  console.log("Step 9...");
}


HungarianAlgorithm.step1(1);
HungarianAlgorithm.step2();
HungarianAlgorithm.step3();
HungarianAlgorithm.step4();
HungarianAlgorithm.step5();
HungarianAlgorithm.step6();

मैं हंगेरियन एल्गोरिदम को लागू करने की कोशिश कर रहा हूं लेकिन मैं चरण 5 पर फंस गया हूं। असल में, संख्याओं के n X n मैट्रिक्स को देखते हुए, मुझे न्यूनतम संख्यात्मक लंबवत + क्षैतिज रेखाएं कैसे मिल सकती हैं जैसे कि मैट्रिक्स में शून्य शामिल हैं?

इससे पहले कि कोई इस प्रश्न को डुप्लिकेट के रूप में चिह्नित करता है, वहां उल्लेखित समाधान गलत है और कोई अन्य पोस्ट किए गए कोड में भी बग में भाग गया है

मैं कोड की तलाश नहीं कर रहा हूं बल्कि अवधारणा जिसके द्वारा मैं इन पंक्तियों को आकर्षित कर सकता हूं ...

संपादित करें: कृपया सरल (लेकिन गलत) लालची एल्गोरिदम पोस्ट न करें: इस इनपुट को देखते हुए:

(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

मैं चुनता हूं, कॉलम 2 स्पष्ट रूप से (0-अनुक्रमित):

(0, 1, x, 1, 1)
(1, 1, x, 1, 1)
(1, 0, x, 0, 1)
(1, 1, x, 1, 1)
(1, 0, x, 1, 0)

अब मैं या तो पंक्ति 2 या कर्नल 1 का चयन कर सकता हूं जिनमें से दो "शेष" शून्य हैं। अगर मैं col2 का चयन करता हूं, तो मैं इस पथ के नीचे गलत समाधान के साथ समाप्त होता हूं:

(0, x, x, 1, 1)
(1, x, x, 1, 1)
(1, x, x, 0, 1)
(1, x, x, 1, 1)
(1, x, x, 1, 0)

सही समाधान 4 लाइनों का उपयोग कर रहा है:

(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)

अद्यतन करें

मैंने आपके द्वारा पोस्ट किए गए लिंक द्वारा प्रदान किए गए एक ही चरण में हंगेरियन एल्गोरिदम लागू किया है: हंगेरियन एल्गोरिदम

टिप्पणियों वाली फाइलें यहां दी गई हैं: Github

चरण 3 के लिए एल्गोरिदम (बेहतर लालची): (यह कोड ड्रॉ करने के लिए रेखा चुनने की अवधारणा को समझने के लिए बहुत विस्तृत और अच्छा है: क्षैतिज बनाम वर्टिकल। लेकिन ध्यान दें कि यह कोड कोड Github में मेरे कोड में सुधार हुआ है)

  • इनपुट मैट्रिक्स में प्रत्येक xy स्थिति के लिए क्षैतिज रूप से बनाम शून्य की अधिकतम संख्या की गणना करें और परिणाम को m2 नामक एक अलग सरणी में संग्रहीत करें।
  • गणना करते समय, क्षैतिज शून्य> लंबवत शून्य, तो गणना की गई संख्या को नकारात्मक में परिवर्तित कर दिया जाता है। (केवल उस दिशा को अलग करने के लिए जिसे हमने बाद में उपयोग के लिए चुना था)
  • m2 सरणी में सभी तत्वों के माध्यम से लूप। यदि मान सकारात्मक है, तो सरणी m3 में एक लंबवत रेखा खींचें, यदि मान ऋणात्मक है, तो m3 में क्षैतिज रेखा खींचें

एल्गोरिदम को और समझने के लिए नीचे दिए गए उदाहरण + कोड का पालन करें:

3 सरणी बनाएं:

  • एम 1: पहला सरणी, इनपुट मान रखती है
  • एम 2: दूसरा सरणी, प्रत्येक एक्स, वाई स्थिति पर maxZeroes (लंबवत, क्षैतिज) रखती है
  • एम 3: तीसरी सरणी, अंतिम लाइनें रखती है (0 सूचकांक खुला, 1 सूचकांक कवर)

2 फ़ंक्शन बनाएं:

  • hvMax (एम 1, पंक्ति, स्तंभ); क्षैतिज या ऊर्ध्वाधर शून्य की अधिकतम संख्या देता है। (सकारात्मक संख्या का मतलब लंबवत है, ऋणात्मक संख्या क्षैतिज है)
  • clearNeighbours (एम 2, एम 3, पंक्ति, कर्नल); शून्य विधि, यह क्षैतिज पड़ोसियों को साफ़ कर देगा यदि पंक्ति कॉल इंडेक्स पर मूल्य ऋणात्मक है, या सकारात्मक होने पर स्पष्ट लंबवत पड़ोसियों। इसके अलावा, यह शून्य बिट को 1 तक फ़्लिप करके एम 3 सरणी में लाइन सेट करेगा।

कोड

public class Hungarian {
    public static void main(String[] args) {
        // m1 input values
        int[][] m1 = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 1 },
                { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 0 } };

        // int[][] m1 = { {13,14,0,8},
        // {40,0,12,40},
        // {6,64,0,66},
        // {0,1,90,0}};

        // int[][] m1 = { {0,0,100},
        // {50,100,0},
        // {0,50,50}};

        // m2 max(horizontal,vertical) values, with negative number for
        // horizontal, positive for vertical
        int[][] m2 = new int[m1.length][m1.length];

        // m3 where the line are drawen
        int[][] m3 = new int[m1.length][m1.length];

        // loop on zeroes from the input array, and sotre the max num of zeroes
        // in the m2 array
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (m1[row][col] == 0)
                    m2[row][col] = hvMax(m1, row, col);
            }
        }

        // print m1 array (Given input array)
        System.out.println("Given input array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m1[row][col] + "\t");
            }
            System.out.println();
        }

        // print m2 array 
        System.out
                .println("\nm2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m2[row][col] + "\t");
            }
            System.out.println();
        }

        // Loop on m2 elements, clear neighbours and draw the lines
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                if (Math.abs(m2[row][col]) > 0) {
                    clearNeighbours(m2, m3, row, col);
                }
            }
        }

        // prinit m3 array (Lines array)
        System.out.println("\nLines array");
        for (int row = 0; row < m1.length; row++) {
            for (int col = 0; col < m1.length; col++) {
                System.out.print(m3[row][col] + "\t");
            }
            System.out.println();
        }
    }

    // max of vertical vs horizontal at index row col
    public static int hvMax(int[][] m1, int row, int col) {
        int vertical = 0;
        int horizontal = 0;

        // check horizontal
        for (int i = 0; i < m1.length; i++) {
            if (m1[row][i] == 0)
                horizontal++;
        }

        // check vertical
        for (int i = 0; i < m1.length; i++) {
            if (m1[i][col] == 0)
                vertical++;
        }

        // negative for horizontal, positive for vertical
        return vertical > horizontal ? vertical : horizontal * -1;
    }

    // clear the neighbors of the picked largest value, the sign will let the
    // app decide which direction to clear
    public static void clearNeighbours(int[][] m2, int[][] m3, int row, int col) {
        // if vertical
        if (m2[row][col] > 0) {
            for (int i = 0; i < m2.length; i++) {
                if (m2[i][col] > 0)
                    m2[i][col] = 0; // clear neigbor
                m3[i][col] = 1; // draw line
            }
        } else {
            for (int i = 0; i < m2.length; i++) {
                if (m2[row][i] < 0)
                    m2[row][i] = 0; // clear neigbor
                m3[row][i] = 1; // draw line
            }
        }

        m2[row][col] = 0;
        m3[row][col] = 1;
    }
}

उत्पादन

Given input array
0   1   0   1   1   
1   1   0   1   1   
1   0   0   0   1   
1   1   0   1   1   
1   0   0   1   0   

m2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)
-2  0   5   0   0   
0   0   5   0   0   
0   -3  5   -3  0   
0   0   5   0   0   
0   -3  5   0   -3  

Lines array
1   1   1   1   1   
0   0   1   0   0   
1   1   1   1   1   
0   0   1   0   0   
1   1   1   1   1   

पीएस: आपका उदाहरण जो आपने इंगित किया है, कभी नहीं होगा क्योंकि आप पहले लूप को अधिकतम (क्षैतिज, लंबवत) ले कर गणना कर सकते हैं और उन्हें m2 में सहेज सकते हैं। तो col1 का चयन नहीं किया जाएगा क्योंकि -3 का मतलब है क्षैतिज रेखा खींचें, और -3 क्षैतिज बनाम ऊर्ध्वाधर शून्य के बीच अधिकतम ले कर गणना की गई थी। तो तत्वों के पहले पुनरावृत्ति पर, कार्यक्रम ने दूसरी पुनरावृत्ति पर लाइनों को आकर्षित करने के तरीके की जांच की है, कार्यक्रम लाइनों को आकर्षित करता है।


@CMPS उत्तर कुछ ग्राफ पर विफल रहता है। मुझे लगता है कि मैंने एक समाधान लागू किया है जो समस्या हल करता है।

मैंने हंगेरियन एल्गोरिदम पर विकिपीडिया लेख का पालन किया और मैंने एक कार्यान्वयन किया जो हर समय काम करता प्रतीत होता है। विकिपीडिया से, यहां न्यूनतम पंक्तियों को आकर्षित करने का तरीका है:

सबसे पहले, जितना संभव हो उतना कार्य असाइन करें। कोई पंक्ति नहीं होने वाली सभी पंक्तियों को चिह्नित करें। सभी चिह्नित (अनमार्क किए गए) कॉलम को चिह्नित करें जिसमें नए चिह्नित पंक्तियों में शून्य है। नए चिह्नित कॉलम में असाइनमेंट वाली सभी पंक्तियों को चिह्नित करें। सभी गैर-निर्दिष्ट पंक्तियों के लिए दोहराएं।

यहां मेरा रूबी कार्यान्वयन है:

def draw_lines grid
    #copies the array    
    marking_grid = grid.map { |a| a.dup }

    marked_rows = Array.new
    marked_cols = Array.new

    while there_is_zero(marking_grid) do 
        marking_grid = grid.map { |a| a.dup }

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

        marked = assignment(grid, marking_grid)    
        marked_rows = marked[0]
        marked_cols.concat(marked[1]).uniq!

        marking_grid = grid.map { |a| a.dup }

        marking_grid.length.times do |row|
            if !(marked_rows.include? row) then
                cross_out(marking_grid,row, nil)
            end
        end

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

    end


    lines = Array.new

    marked_cols.each do |index|
        lines.push(["column", index])
    end
    grid.each_index do |index|
        if !(marked_rows.include? index) then
            lines.push(["row", index])
        end
    end
    return lines
end


def there_is_zero grid
    grid.each_with_index do |row|
        row.each_with_index do |value|
            if value == 0 then
                return true
            end
        end
    end
    return false
end

def assignment grid, marking_grid 
    marking_grid.each_index do |row_index|
        first_zero = marking_grid[row_index].index(0)
        #if there is no zero go to next row
        if first_zero.nil? then
            next        
        else
            cross_out(marking_grid, row_index, first_zero)
            marking_grid[row_index][first_zero] = "*"
        end
    end

    return mark(grid, marking_grid)
end


def mark grid, marking_grid, marked_rows = Array.new, marked_cols = Array.new
    marking_grid.each_with_index do |row, row_index|
        selected_assignment = row.index("*")
        if selected_assignment.nil? then
            marked_rows.push(row_index)
        end
    end

    marked_rows.each do |index|
        grid[index].each_with_index do |cost, col_index|
            if cost == 0 then
                marked_cols.push(col_index)    
            end
        end
    end
    marked_cols = marked_cols.uniq

    marked_cols.each do |col_index|
        marking_grid.each_with_index do |row, row_index|
            if row[col_index] == "*" then
                marked_rows.push(row_index)    
            end
        end
    end

    return [marked_rows, marked_cols]
end


def cross_out(marking_grid, row, col)
    if col != nil then
        marking_grid.each_index do |i|
            marking_grid[i][col] = "X"    
        end
    end
    if row != nil then
        marking_grid[row].map! {|i| "X"} 
    end
end

grid = [
    [0,0,1,0],
    [0,0,1,0],
    [0,1,1,1],
    [0,1,1,1],
]

p draw_lines(grid)

ऐसे मामले हैं जहां अमीर का कोड विफल रहता है।

निम्नलिखित एम 1 पर विचार करें:

 0  0  1

 0  1  1

 1  0  1

सबसे अच्छा समाधान पहले दो कॉलम में लंबवत रेखाएं खींचना है।

अमीर का कोड निम्नलिखित एम 2 देगा:

-2 -2  0

 2  0  0

 0  2  0

और नतीजा पहली पंक्ति में एक पंक्ति के रूप में दो लंबवत रेखाओं को आकर्षित करेगा।

ऐसा लगता है कि समस्या टाई तोड़ने का मामला है:

return vertical > horizontal ? vertical : horizontal * -1;

जिस तरह से कोड लिखा गया है, वही समान एम 1 असफल नहीं होगा:

 0  1  1

 1  0  1

 0  0  1

जहां पहली पंक्ति को नीचे ले जाया जाता है, क्योंकि क्लीयरिंग फ़ंक्शन उन कोशिकाओं तक पहुंचने से पहले 2 मानों को एम 2 से साफ़ कर देगा। पहले मामले में, -2 मान पहले हिट होते हैं, इसलिए पहली पंक्ति के माध्यम से एक क्षैतिज रेखा खींची जाती है।

मैं इसके माध्यम से थोड़ा काम कर रहा हूं, और यही मेरे पास है। टाई के मामले में, कोई मूल्य निर्धारित न करें और उन कोशिकाओं के माध्यम से एक रेखा न खींचे। इसमें ऊपर वर्णित मैट्रिक्स के मामले को शामिल किया गया है, हम इस चरण में किए जाते हैं।

जाहिर है, ऐसी स्थितियां हैं जहां 0 बजे रहेंगे जो अनदेखा हैं। नीचे एक मैट्रिक्स का एक और उदाहरण है जो अमीर की विधि में विफल हो जाएगा (एम 1):

 0 0 1 1 1
 0 1 0 1 1
 0 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

इष्टतम समाधान चार लाइनों है, उदाहरण के लिए पहले चार कॉलम।

अमीर की विधि एम 2 देता है:

 3 -2  0  0  0
 3  0 -2  0  0
 3  0  0 -2  0
 0  0 -2 -2  0
 0  0  0  0  0

जो पहले चार पंक्तियों और पहले कॉलम (एक गलत समाधान, 5 लाइन देकर) पर लाइनें खींचेगा। फिर, टाई ब्रेकर केस मुद्दा है। हम संबंधों के लिए मूल्य निर्धारित नहीं करते हैं, और प्रक्रिया को पुन: स्थापित करते हैं।

अगर हम संबंधों को अनदेखा करते हैं तो हमें एक एम 2 मिलता है:

 3 -2  0  0  0
 3  0  0  0  0
 3  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

इससे केवल पहली पंक्ति और पहला स्तंभ शामिल होता है। फिर हम 0 एम लेते हैं जो नए एम 1 देने के लिए कवर होते हैं:

 1 1 1 1 1
 1 1 0 1 1
 1 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

फिर हम प्रक्रिया तक पहुंचने तक प्रक्रिया को दोहराते रहते हैं (संबंधों को अनदेखा करते हैं)। एक नए एम 2 के लिए दोहराएं:

 0  0  0  0  0
 0  0  2  0  0
 0  0  0  2  0
 0  0  0  0  0
 0  0  0  0  0

जो दूसरे और तीसरे कॉलम के माध्यम से दो लंबवत रेखाओं की ओर जाता है। सभी 0 अब कवर किए गए हैं, केवल चार लाइनों की आवश्यकता है (यह पहले चार स्तंभों को अस्तर करने का एक विकल्प है)। उपरोक्त मैट्रिक्स को केवल 2 पुनरावृत्तियों की आवश्यकता है, और मुझे लगता है कि इनमें से अधिकतर मामलों में केवल दो पुनरावृत्तियों की आवश्यकता होगी जब तक कि संबंधों के सेट में घनिष्ठ संबंधों के सेट न हों। मैंने एक के साथ आने की कोशिश की, लेकिन इसे प्रबंधित करना मुश्किल हो गया।

अफसोस की बात है, यह काफी अच्छा नहीं है, क्योंकि ऐसे मामले होंगे जो हमेशा के लिए बंधे रहेंगे। विशेष रूप से, ऐसे मामलों में जहां 'बंधे हुए कोशिकाओं का पृथक सेट' होता है। निम्नलिखित दो उदाहरणों को आकर्षित करने के अलावा यह सुनिश्चित नहीं है कि इसका वर्णन कैसे किया जाए:

 0 0 1 1
 0 1 1 1
 1 0 1 1
 1 1 1 0

या

 0 0 1 1 1
 0 1 1 1 1
 1 0 1 1 1
 1 1 1 0 0
 1 1 1 0 0

इन दो उदाहरणों में ऊपरी-बाएं 3x3 उप-मैट्रिस मेरे मूल उदाहरण के समान हैं, मैंने उस उदाहरण में 1 या 2 पंक्तियों / कोल्स को नीचे और दाईं ओर जोड़ा है। केवल नए जोड़े गए शून्य हैं जहां नई पंक्तियां और कॉलम पार हो जाते हैं। स्पष्टता के लिए वर्णित।

मैंने वर्णित पुनरावृत्ति विधि के साथ, इन मैट्रिस को अनंत लूप में पकड़ा जाएगा। शून्य हमेशा बंधे रहेंगे (कॉल-गिनती बनाम पंक्ति-गणना)। इस बिंदु पर, यह समझदारी से समझता है कि टाई के मामले में मनमाने ढंग से एक दिशा का चयन करें, कम से कम मैं कल्पना कर सकता हूं।

एकमात्र मुद्दा जो मैं चला रहा हूं वह लूप के लिए रोक मानदंड स्थापित कर रहा है। मैं यह नहीं मान सकता कि 2 पुनरावृत्तियों पर्याप्त (या कोई भी एन) है, लेकिन मैं यह भी पता नहीं लगा सकता कि मैट्रिक्स में केवल अनंत लूप ही हैं या नहीं। मुझे अभी भी यकीन नहीं है कि इन विवादित-बंधे-सेटों को कम्प्यूटेशनल रूप से कैसे वर्णन किया जाए।

यहां तक ​​कि कोड जो मैंने अभी तक किया है, करने के लिए कोड है (MATLAB स्क्रिप्ट में):

function [Lines, AllRows, AllCols] = FindMinLines(InMat)

%The following code finds the minimum set of lines (rows and columns)
%required to cover all of the true-valued cells in a matrix. If using for
%the Hungarian problem where 'true-values' are equal to zero, make the
%necessary changes. This code is not complete, since it will be caught in 
%an infinite loop in the case of disjoint-tied-sets

%If passing in a matrix where 0s are the cells of interest, uncomment the
%next line
%InMat = InMat == 0;

%Assume square matrix
Count = length(InMat);
Lines = zeros(Count);

%while there are any 'true' values not covered by lines

while any(any(~Lines & InMat))
    %Calculate row-wise and col-wise totals of 'trues' not-already-covered
    HorzCount = repmat(sum(~Lines & InMat, 2), 1, Count).*(~Lines & InMat);
    VertCount = repmat(sum(~Lines & InMat, 1), Count, 1).*(~Lines & InMat);

    %Calculate for each cell the difference between row-wise and col-wise
    %counts. I.e. row-oriented cells will have a negative number, col-oriented
    %cells will have a positive numbers, ties and 'non-trues' will be 0.
    %Non-zero values indicate lines to be drawn where orientation is determined
    %by sign. 
    DiffCounts = VertCount - HorzCount;

    %find the row and col indices of the lines
    HorzIdx = any(DiffCounts < 0, 2);
    VertIdx = any(DiffCounts > 0, 1);

    %Set the horizontal and vertical indices of the Lines matrix to true
    Lines(HorzIdx, :) = true;
    Lines(:, VertIdx) = true;
end

%compute index numbers to be returned. 
AllRows = [find(HorzIdx); find(DisjTiedRows)];
AllCols = find(VertIdx);

end




hungarian-algorithm