Выделение только одного значения из каждой строки и столбца матрицы

Question

Это не совсем вопрос о коде, но мне нужна помощь с логикой алгоритма.

Учитывая матрицу NxN, которая имеет хотя бы одно нулевое значение в каждой строке и столбце, как бы вы выбрали N нулей, чтобы в каждой строке и каждом столбце было ровно одно значение? Например:

0 4 6 0 2
0 8 9 5 0
4 0 9 8 5
0 8 0 1 3
8 6 0 1 3

Очевидно, что сначала вы должны выбрать нули, которые являются единичными в каждой строке или столбце. Я не уверен в том, что в нескольких строках и столбцах одинаковое количество нулей. Как выбрать оптимальные значения, чтобы ни одна строка или столбец не были пропущены?

Answer 1

Это проблема нахождения максимального соответствия в двудольном графе : строки представляют один набор вершин u_1, u_2, ..., u_N, столбцы - другой набор v_1, v_2, ..., v_N, и есть ребро u_i - v_j всякий раз, когда в позиции матрицы (i, j) есть 0.

Это может быть решено с использованием алгоритмов максимального потока, таких как Форд-Фулкерсон за O (N ^ 3) времени, или с помощью более специализированного алгоритма Хопкрофта-Карпа за O (N ^ 2.5). Фактически эти алгоритмы решают несколько более общую проблему: он найдет максимально возможный набор уникальных пар (строка, столбец), так что каждая пара имеет 0 в матрице. (В вашем случае вы знаете, что есть решение с N такими парами: это, очевидно, наилучшее из возможных.)

Answer 2

1. Выберите строку с наименьшим количеством нулей.

2. Для каждого нуля в этой строке выберите тот, столбец которого имеет наименьшее количество нулей.

3. Пометить эту строку и столбец каким-либо образом (может быть, удалить все зееры из них после сохранения индекса выбранного нуля? Это на ваше усмотрение).

   Помеченные строки и столбцы пропускаются в следующей итерации.

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

Итак, для примера проблемы, вот как можно визуализировать решение (< и ^ представляют отмеченные строки и столбцы):

0 4 6 0 2

0 8 9 5 0

4 0 9 8 5

0 8 0 1 3

8 6 0 1 3 // Строка с наименьшим количеством нулей и последним, к которому нужно получить доступ

Итерация 1:

0 4 6 0 2

0 8 9 5 0

4 0 9 8 5

0 8 0 1 3

8 6 0 1 3 <</p>

_ _ ^ _ _

Итерация 2:

0 4 6 0 2

0 8 9 5 0

4 0 9 8 5 <</p>

0 8 0 1 3

8 6 0 1 3 <</p>

_ ^ ^ _ _

Итерация 3:

0 4 6 0 2

0 8 9 5 0 <</p>

4 0 9 8 5 <</p>

0 8 0 1 3

8 6 0 1 3 <</p>

_ ^ ^ _ ^

Итерация 4:

0 4 6 0 2 <</p>

0 8 9 5 0 <</p>

4 0 9 8 5 <</p>

0 8 0 1 3

8 6 0 1 3 <</p>

_ ^ ^ ^ ^

Итерация 5:

0 4 6 0 2 <</p>

0 8 9 5 0 <</p>

4 0 9 8 5 <</p>

0 8 0 1 3 <</p>

8 6 0 1 3 <</p>

^ ^ ^ ^ ^