Как найти минимальное количество строк, необходимое для покрытия всех нулей в двумерном массиве?

Question

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

Также мне нужно знать эти строки, чтобы сделать некоторые вычисления позже

вот объяснение:

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

на шаге 3 говорится

Используйте как можно меньше строк, чтобы покрыть все нули в матрице. Нет простого правила сделать это - в основном методом проб и ошибок.

что означает метод проб и ошибок с точки зрения вычислений? Если у меня есть, например, 2d массив из 5 строк и 5 столбцов, то

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

разве нет ничего более эффективного, чем это?

заранее спасибо

Answer 1

Вы должны реализовать алгоритм двойного соответствия здесь. У вас есть два разбиения в графе - вершины в одном из них представляют строки, а вершины в другом представляют столбцы в таблице. Между строкой_i и столбцом_j есть ребро, если в ячейке есть 1 (i,j). Затем вы создаете максимальное двустороннее соответствие. После последней итерации алгоритма двудольного сопоставления вам нужно выяснить, какие вершины соединены через инкрементальный путь с источником для вашего сопоставления. Инкрементальный путь - это путь, использующий только ребра с положительной емкостью. Вы должны иметь изображение, как:

         row_1                  col_1
        /                             \
       / - row_2                col_2 -\
source  - ....     some_edges           \ sink
       \                                / 
        \ - row_n                col_n /
                                 .... /
                                 col_m

После того, как вы найдете максимальное двойное соответствие, найдите, какие строки и столбцы доступны через ребра положительной емкости из приемника. Теперь минимальное количество строк и столбцов, которое вам нужно очистить, определяется с помощью следующего алгоритма: вы вычеркиваете все строки, которые не достижимы из источника, и все столбцы, которые достижимы, и это ваше оптимальное решение.

Надеюсь, этот ответ поможет вам.

Answer 2

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

http://en.wikipedia.org/wiki/Hungarian_algorithm

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

Answer 3

Метод проб и ошибок означает сложность O((n+m)!).

Самое большее, вам нужно будет выбрать только min(n,m) строк, так как выбор всех строк или столбцов охватит все 0.

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