Динамическое программирование Вопрос, выбирая 1 с в матрице 0-1 так, чтобы каждая строка и столбец содержали ровно один 1

Question

Учитывая квадратную матрицу 0-1, во сколько раз мы можем выбрать 1, чтобы каждая строка и столбец содержали ровно одну 1 ??

Я реализовал следующий код возврата для этой проблемы:

    int countways(int A[][], int& n, int row, vector<bool> columnselected ) {
         if(row == n)
              return 1;
         int result = 0;
         for( j = 0; j < n ; ++j) {
              if(A[row][j]) {
                   if(!columnselected[j]) {
                        columnselected[j] = true;
                        result+ = countways(A, n, row+1, columnselected);
                        columnselected[j] = false;
                   }
               }
         }
         return result;
     }

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

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

Answer 1

Эта задача эквивалентна нахождению числа совершенных совпадений для двудольного графа . Возьмите матрицу NxN и создайте вершину для каждой строки и вершину для каждого столбца (2N вершин). Добавьте ребро между вершиной строки и вершины столбца, если матрица содержит «1» в соответствующей строке и столбце. Это формирует двудольный граф. Обратите внимание, что поиск идеального совпадения на этом графике эквивалентен выбору «1», так что каждая строка и столбец содержат ровно 1 «.

Из Википедия :

Проблема определения количества совершенных совпадений в заданном график #P завершен (см. постоянный). Тем не менее, замечательная теорема Кастелейн утверждает, что число идеальных совпадений в плоскости график может быть вычислен точно за полиномиальное время с помощью FKT алгоритм. Кроме того, для двудольных графов, проблема может быть приблизительно решается за полиномиальное время. [ 8 ] То есть для любого ε> 0, есть вероятностный алгоритм полиномиального времени, который определяет, с высокой вероятностью число совершенных совпадений M в пределах погрешность не более εM.

Примечание. Вы можете определить, является ли ответ нулевым или нет за полиномиальное время.

---

Таким образом, идеальное решение за полиномиальное время невозможно, но мы можем улучшить асимптотическое время выполнения вашей функции (с O (N * N!) До O (N * 2 ^ N)) с помощью memoization . Только переменная «columnselected» должна быть «памяткой». (Изменение «columnselected» на целое число в битовой маске вместо вектора также должно улучшить производительность и иметь более простую реализацию).

Answer 2

Если я правильно понимаю ваш вопрос, не является ли эта проблема тем же, что и присвоение уникальных рангов каждому столбцу? Например, если в [p, q] есть 1, это означает, что q-му столбцу присвоен ранг p.

Таким образом, для матрицы NxN решение должно быть N! (факториал N)

Вы также можете использовать индукцию P (N) = n * P (N-1), поскольку, когда вы помещаете 1 где-нибудь в матрице NxN, строка и столбец блокируются им - так что у вас остается ( N-1) x (N-1) матрица.

РЕДАКТИРОВАТЬ: мое понимание проблемы было неправильно. Но вот новая попытка с подходом динамического программирования

---

Давайте сначала создадим DAG, например так: узлы этого графа являются квадратами квадратов (p, q, size) - квадратами, закрепленными в row = p, col = q с элементами размера x размера. Да, они могут обернуться. Для простоты вычислений пусть q всегда равно 0.

Для матрицы {{abc}, {def}, {ghi}} узлы будут

{a}, {d}, {g}: квадраты с размером 1: корневые узлы

{ab, de}, {de, gh}, {gh, ab}: квадраты размером 2

{{abc}, {def}, {ghi}}: только квадрат размера N, то есть сама матрица: листовой узел

Направленные края указывают от квадратов размером n до n + 1 И, если маленький квадрат может содержаться в большем. Например, {d} указывает на {ab, de} и {de, gh} Важное замечание: между размером n и размером n + 2 не должно быть никаких граней

Traversal

Основание: присвоить веса квадратам размера 1: Квадрат (p, 0,1) = 1 тогда и только тогда, когда M (p, 0) == 1

Шаг: Для квадратов размера N, посетите детей, то есть квадратов размера N + 1. Внесите свой вес ребенку, если угол, к которому он растет, равен 1, иначе - нет.

Листовой узел будет иметь ваш ответ.

Это решение, по сути, является подходом обхода снизу вверх и позволит избежать дублирования вычислений подзадач.

Answer 3

Боюсь, что вам лучше всего изменить алгоритм Кнута X, более подробно объясненный в http://en.wikipedia.org/wiki/Exact_cover. Ключом является использование структуры данных, аналогичной используемой в алгоритме X.

Я почти уверен, что описанная вами проблема эквивалентна точному покрытию, что делает ее NP-полной.Следовательно, «эффективное» решение недоступно, но алгоритм X будет хорошо на практике.