Венгерский алгоритм: поиск минимального количества строк для обнуления нулей?

Ответ 1

Обновление

Я реализовал венгерский алгоритм в тех же шагах, которые вы указали по ссылке: Венгерский алгоритм p >

Здесь файлы с комментариями: Github

Алгоритм (улучшенный жадный) для шага 3: (Этот код очень подробный и полезный для понимания концепции выбора линии для рисования: горизонтальная и вертикальная. Но обратите внимание, что этот код шага улучшен в мой код в Github)

• Рассчитайте максимальное количество нулей вертикально и горизонтально для каждой позиции xy во входной матрице и сохраните результат в отдельном массиве с именем m2.
• При вычислении, если горизонтальные нули > вертикальные нули, то расчетное число преобразуется в отрицательное. (просто чтобы определить, какое направление мы выбрали для последующего использования)
• Прокрутите все элементы массива m2. Если значение положительное, нарисуйте вертикальную линию в массиве m3, если значение отрицательное, нарисуйте горизонтальную линию в m3

Следуйте приведенному ниже примеру +, чтобы лучше понять алгоритм:

Создать 3 массива:

• m1: Первый массив, содержит входные значения
• m2: Второй массив, содержит maxZeroes (вертикальный, горизонтальный) в каждой позиции x, y
• m3: Третий массив, содержит окончательные строки (0 индекс не раскрыт, 1 проиндексирован)

Создать 2 функции:

• hvMax (m1, строка, столбец); возвращает максимальное количество нулей по горизонтали или по вертикали. (Положительное число означает вертикальное, отрицательное число означает горизонтальное)
• clearNeighbours (m2, m3, row, col); void, он очистит горизонтальные соседи, если значение в индексах столбцов строки отрицательное или четкие вертикальные соседи, если они положительные. Более того, он установит строку в массиве m3, перевернув нулевой бит в 1.

код

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   

PS: Ваш пример, на который вы указали, никогда не произойдет, потому что, поскольку вы можете увидеть первый цикл, выполните вычисления, взяв max (горизонтальный, вертикальный) и сохраните их в m2. Таким образом, col1 не будет выбран, потому что -3 означает горизонтальную линию рисования, а -3 вычисляли, беря максимум между горизонтальными и вертикальными нулями. Итак, на первой итерации у элементов программа проверила, как рисовать линии, на второй итерации программа рисует линии.

Ответ 2

Жадные алгоритмы могут не работать в некоторых случаях.

Во-первых, можно переформулировать свою проблему следующим образом: учитывая двудольный граф, найдите минимальное покрытие вершин. В этой задаче имеется 2n узлов, n для строк и n для столбцов. Существует ребро между двумя узлами, если элемент на пересечении соответствующего столбца и строки равен нулю. Крышка вершины представляет собой набор узлов (строк и столбцов), так что каждое ребро падает на некоторый node из этого набора (каждый ноль покрывается строкой или столбцом).

Это хорошо известная проблема и может быть решена в O (n ^ 3) путем нахождения максимального совпадения. Подробнее о wikipedia

Ответ 3

Есть случаи, когда код Амира не работает.

Рассмотрим следующее m1:

 0  0  1

 0  1  1

 1  0  1

Лучшим решением является рисование вертикальных линий в первых двух столбцах.

Код Амира даст следующие m2:

-2 -2  0

 2  0  0

 0  2  0

И результат будет рисовать две вертикальные линии AS WELL AS - строка в первой строке.

Мне кажется, что проблема заключается в развязывании:

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

Из-за того, как написан код, очень похожий m1 НЕ МОЖЕТ:

 0  1  1

 1  0  1

 0  0  1

Если первая строка перемещается в нижнюю часть, так как функция очистки очистит значения -2 от m2 до того, как эти ячейки будут достигнуты. В первом случае первые два значения попадают, поэтому горизонтальная линия проходит через первую строку.

Я немного поработал над этим, и это то, что у меня есть. В случае галстука не устанавливайте значения и не рисуйте линию через эти ячейки. Это касается случая упомянутой выше матрицы, мы делаем это на этом этапе.

Ясно, что бывают ситуации, когда остаются 0s, которые не обнаружены. Ниже приведен еще один пример матрицы, которая потерпит неудачу в методе Амира (m1):

 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

Оптимальное решение - четыре строки, например. первые четыре столбца.

Метод Амира дает m2:

 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 строк). Опять же, проблема тай-брейка - проблема. Мы решаем это, не устанавливая значение связей и не повторяя процедуру.

Если мы игнорируем связи, получаем m2:

 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

Это приводит к покрытию только первой строки и первого столбца. Затем мы вынимаем 0s, которые покрываются, чтобы дать новый m1:

 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

Это приводит к двум вертикальным линиям через второй и третий столбцы. Все 0s теперь покрыты, они нуждаются только в четырех строках (это альтернатива выравниванию первых четырех столбцов). В приведенной выше матрице требуется только 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

Верхние левые 3-х подматрицы в этих двух примерах идентичны моему первоначальному примеру, я добавил 1 или 2 строки/столбцы к этому примеру внизу и справа. Единственные вновь добавленные нули, где пересекаются новые строки и столбцы. Описание для ясности.

С помощью описанного итерационного метода эти матрицы будут пойманы в бесконечном цикле. Нули всегда будут привязаны (кол-счет против числа строк). На данный момент имеет смысл просто произвольно выбирать направление в случае галстука, по крайней мере, из того, что я могу себе представить.

Единственная проблема, с которой я столкнулся, - это установить критерии остановки для цикла. Я не могу предположить, что достаточно 2 итераций (или любого n), но я также не могу понять, как определить, имеет ли в нем только бесконечные петли. Я все еще не уверен, как вычислить эти непересекающиеся множества вычислительно.

Вот код, который я делал до сих пор (в MATLAB script):

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

Ответ 4

Шаг 5: Чертеж линии в матрице оценивается по диагонали с максимальными оценками длины матрицы.

На основе http://www.wikihow.com/Use-the-Hungarian-Algorithm только с шагами 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

Выполните назначение, используя шаги, упомянутые ниже:

• назначить строку, если она имеет только один 0, иначе временно пропустить строку
• зачеркнуть 0 в назначенном столбце
• Сделайте то же самое для каждого столбца

Выполнив назначение, используя вышеуказанные шаги, выполните следующие шаги, чтобы получить минимальное количество строк, которые охватывают все 0

• Шаг 1 - Отметьте неназначенный ряд
• шаг 2 - если отмеченная строка имеет 0, то отметьте галочкой соответствующий столбец
• Шаг 3 - Если отмеченный столбец имеет назначение, отметьте галочкой соответствующую строку
• Шаг 4 - Повторите шаги 2 и 3, пока тикание больше не будет возможно
• Шаг 5 - Нарисуйте линии через не отмеченные строки и отмеченные столбцы

Для вашего случая: (0-индексация для строк и столбцов)

• пропустить строку 0, так как она имеет два 0
• назначьте строку 1 и вычеркните все 0 в столбце 2
• пропустить строку 2, так как она имеет два непересекающихся 0
• пропустить строку 3, так как она не имеет перекрещенных 0
• пропустить строку 4, так как она имеет 2 непересекающихся 0

• назначить столбец 0
• пропустите столбец 1, так как он имеет два непересекающихся 0 (в строке 2 и строке 4)
• пропустите столбец 2, так как он уже назначен 0
• назначьте столбец 3 и вычеркните 0 в строке 2
• назначьте столбец 4 и вычеркните 0 в строке 4
• присвоенные 0 показаны как '_', а 'x' показывает перечеркнутые 0

(_ 1 x 1 1), (1 1 _ 1 1), (1 xx _ 1), (1 1 x 1 1), (1 xx 1 _)

• Матрица выглядит так, как показано выше после выполнения заданий

Теперь выполните 5 шагов, упомянутых выше, чтобы получить минимальное количество строк, которые охватывают все 0

• Отметьте строку 3, поскольку она еще не назначена
• Поскольку строка 3 имеет 0 в столбце 2, отметьте столбец 2
• Поскольку столбец 2 имеет присвоение в строке 1, отметьте строку 1
• Теперь нарисуйте линии через не отмеченные строки (т.е. Строки 0,2,4) и отмеченные столбцы (т.е. Столбец 2).
• Эти 4 строки покроют все 0

Надеюсь это поможет:)

PS: Для случаев, когда первоначальное назначение невозможно из-за множества 0 в каждой строке и столбце, это можно обработать, взяв одно произвольное назначение (для случаев, когда несколько значений 0 присутствуют в каждой строке и столбце, очень вероятно, что более чем одно возможное назначение приведет к оптимальному решению)

Ответ 6

@CMPS не удается выполнить на нескольких графиках. Я думаю, что я реализовал решение, которое решает проблему.

Я следовал статье Википедии о венгерском алгоритме, и я сделал реализацию, которая, кажется, работает все время. Из Википедии здесь приведен метод рисования минимального количества строк:

Сначала назначьте как можно больше задач.     Отметьте все строки, не имеющие назначений.     Отметьте все (немаркированные) столбцы, имеющие нули в новых отмеченных строках.     Отметьте все строки, имеющие назначения в новых столбцах.     Повторите для всех не назначенных строк.

Вот моя реализация Ruby:

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)