Из интервью: удаление строк и столбцов в матрице n × n для максимизации суммы оставшихся значений

Question

Учитывая матрицу вещественных чисел n × n. Вам разрешено удалять любое количество (от 0 до n) строк и любое количество (от 0 до n) столбцов, после чего вычисляется сумма оставшихся записей. Придумайте алгоритм, который определяет, какие строки и столбцы нужно удалить, чтобы максимизировать эту сумму.

Answer 1

Проблема в NP-hard . (Таким образом, вы не должны ожидать алгоритм полиномиального времени для решения этой проблемы. Тем не менее, могут быть алгоритмы (не полиномиального времени), которые немного лучше, чем грубая сила.) Идея доказательства NP-твердости заключается в том, что если бы мы могли решить эту проблему, то мы могли бы решить проблему клики в общем графе. (Задача максимальной клики - найти самый большой набор попарно соединенных вершин в графе.)

В частности, для любого графа с n вершинами сформируем матрицу A с элементами a[i][j] следующим образом:

• a[i][j] = 1 для i == j (диагональные записи)
• a[i][j] = 0, если на графике присутствует ребро (i, j) (и i≠j)
• a[i][j] = -n-1 если ребро (i, j) не присутствует на графике.

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

1. Заявка : В любом оптимальном решении нет строки i и столбца j, для которых ребро (i, j) отсутствует на графике. Доказательство: поскольку a[i][j] = -n-1 и сумма всех положительных записей не превышает n, выбор (i, j) приведет к отрицательной сумме. (Обратите внимание, что удаление всех строк и столбцов даст лучшую сумму, равную 0.)

2. Заявка : В (некотором) оптимальном решении набор сохраненных строк и столбцов одинаков. Это потому, что, начиная с любого оптимального решения, мы можем просто удалить все строки i, для которых столбец i не был сохранен, и наоборот. Обратите внимание, что поскольку единственными положительными значениями являются диагональные, мы не уменьшаем сумму (и по предыдущему требованию мы также не увеличиваем ее).

Все это означает, что если граф имеет максимальную клику размером k, то наша матричная задача имеет решение с суммой k, и наоборот. Следовательно, если бы мы могли решить нашу начальную задачу за полиномиальное время, то проблема клики также была бы решена за полиномиальное время. Это доказывает, что исходная проблема NP-hard . (На самом деле, легко увидеть, что версия решения исходной проблемы - есть ли способ удаления некоторых строк и столбцов, чтобы сумма составляла не менее 1057 * - была в NP, поэтому (версия решения) Первоначальная проблема на самом деле NP-полная .)

Answer 2

Ну, метод грубой силы выглядит примерно так:

• Для n строк имеется 2 ⁿ подмножеств.
• Для n столбцов существует 2 ⁿ подмножеств.
• Для матрицы n x n имеется 2 ²ⁿ подмножеств.

0 элементов является допустимым подмножеством, но, очевидно, если у вас 0 строк или 0 столбцов, общее количество равно 0, так что на самом деле есть 2 ^2n-2 + 1 подмножеств, но это ничем не отличается.

Таким образом, вы можете отработать каждую комбинацию методом грубой силы как алгоритм O ( ⁿ ). Быстро. :)

Было бы быстрее выяснить, каково максимально возможное значение, и вы делаете это, складывая все положительные числа в сетке. Если эти числа образуют действительную подматрицу (то есть вы можете создать этот набор, удалив строки и / или столбцы), тогда ваш ответ.

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

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

Также, если все числа не положительны, ответом является максимальное значение, поскольку вы можете уменьшить матрицу до матрицы 1 x 1 с этим значением 1 по определению.

Вот идея: построить 2 ⁿ -1 n x m матриц, где 1 <= m <= n. Обработайте их один за другим. Для каждой матрицы n x m вы можете рассчитать: </p>

1. максимально возможная максимальная сумма (как указано выше); и
2. Если числа не являются положительными, что позволяет вам быстро ответить.

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

Обычно это называется техникой обрезки .

Более того, вы можете начать с того, что наибольшее число в матрице n x n является начальной максимальной суммой, поскольку очевидно, что это может быть матрица 1 x 1.

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

Answer 3

Мы можем улучшить обобщенное решение методом грубой силы Cletus, смоделировав его как ориентированный граф. Начальная матрица является начальным узлом графа; все его листья - это матрицы, в которых отсутствует одна строка или столбец и т. д. Это график, а не дерево, потому что у узла для матрицы без первого столбца и строки будут два родителя - узлы с отсутствующим только первым столбцом или строкой.

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

Конечно, это все еще перебор, но мы устранили дублирующие случаи, когда мы удаляем одни и те же строки в разных порядках.

Вот пример реализации в Python:

def maximize_sum(m):
  frontier = [(m, 0, False)]
  best = None
  best_score = 0

  while frontier:
    current, startidx, cols_done = frontier.pop()
    score = matrix_sum(current)
    if score > best_score or not best:
      best = current
      best_score = score
    w, h = matrix_size(current)
    if not cols_done:
      for x in range(startidx, w):
        frontier.append((delete_column(current, x), x, False))
      startidx = 0
    for y in range(startidx, h):
      frontier.append((delete_row(current, y), y, True))
  return best_score, best

А вот пример матрицы 280Z28:

>>> m = ((1, 1, 3), (1, -89, 101), (1, 102, -99))
>>> maximize_sum(m)
(106, [(1, 3), (1, 101)])

Answer 4

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

Answer 5

Чтобы попробовать это простым способом:

Нам нужно подмножество действительных набора записей {A00, A01, A02, ..., A0n, A10, ..., Ann}, макс. сумма.

Сначала вычислите все подмножества (набор мощности).

A valid подмножество является членом набора мощности, который для каждых двух содержащихся записей Aij и A (i + x) (j + y) содержит также элементы A (i + x) j и Ai (j + y) (оставшиеся углы прямоугольника, охватываемого Aij и A (i + x) (j + y)).

Aij ...
 .       .   
 .       .
    ... A(i+x)(j+y)     

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

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

Answer 6

Рассчитать сумму каждой строки и столбца. Это можно сделать в O (m) (где m = n ^ 2)

Хотя есть строки или столбцы, сумма которых равна отрицанию, удалите строку или столбец с наименьшей суммой, которая меньше нуля. Затем пересчитайте сумму каждой строки / столбца.

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

Это даст оптимальный максимальный результат. Время выполнения O (mn) или O (n ^ 3)

Answer 7

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

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

3. Я думаю, что есть эвристический подход, но я не могу его прибить:

   если есть одно отрицательное число, вы можете взять матрицу такой, какая она есть, удалить столбец отрицательного числа или удалить его строку; Я не думаю, что другие "ходы" приводят к более высокой сумме. Для двух отрицательных чисел возможны следующие варианты: удалить ни одно, либо удалить одно, удалить другое или удалить оба (если акт удаления выполняется путем перемещения строки или столбца).

   Теперь предположим, что матрица имеет только одно положительное число, а все остальные <= 0. Вы явно хотите удалить все, кроме положительной записи. Для матрицы только с 2 положительными входами и остальными <= 0 возможны следующие варианты: ничего не делать, уменьшать до одного, уменьшать до другого или уменьшать до обоих (в результате получается матрица 1x2, 2x1 или 2x2) . </p>

   В общем, этот последний вариант распадается (представьте матрицу с 50 положительными и 50 отрицательными значениями), но в зависимости от ваших данных (мало отрицательных или мало положительных) это может обеспечить сокращение.

Answer 8

• Создание векторного ряда RowSums n-на-1 и векторного столбца ColumnSums n-на-1. Инициализируйте их для сумм строк и столбцов исходной матрицы. O (N²)
• Если какая-либо строка или столбец имеет отрицательную сумму, удалите edit: ту, у которой минимум , и обновите суммы в другом направлении, чтобы отразить их новые значения. О (п)
• Стоп, когда ни в одной строке или столбце сумма не равна нулю.

Это итерационная вариация, улучшающая другой ответ. Он работает за время O (n²), но не работает в некоторых случаях, упомянутых в других ответах, что является пределом сложности для этой проблемы (в матрице есть n² записей, и даже для того, чтобы найти минимум, вам нужно проверить каждую ячейку один раз) .

Редактировать: Следующая матрица не имеет отрицательных строк или столбцов, но также не развернута, и мой алгоритм не улавливает ее.

1     1     3        goal     1    3
1   -89   101        ===>     1  101
1   102   -99

Следующая матрица имеет отрицательные строки и столбцы, но мой алгоритм выбирает неправильные для удаления.

 -5     1    -5      goal     1
  1     1     1      ===>     1
-10     2   -10               2

                     mine
                     ===>     1     1     1

Answer 9

Скажем, n = 10.

Грубая сила (все возможные наборы строк x все возможные наборы столбцов) занимает

2 ^ 10 * 2 ^ 10 = ~ 1 000 000 узлов.

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

сумма положительных записей является верхней границей для каждого узла в поддереве

как метод обрезки. В сочетании с жадным алгоритмом для дешевого создания хороших начальных границ это дало ответы в среднем около 80 000 узлов.

---

но есть и лучший способ! позже я понял, что

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

Так что мы можем просто перебрать все возможные варианты строк; это занимает 2 ^ 10 = 1024 узла.

При добавлении метода сокращения в среднем это сократилось до 600 узлов.

Хранение сумм столбцов и их постепенное обновление при обходе дерева наборов строк должно позволять вычислениям (сумме матрицы и т. Д.) В каждом узле быть O (n) вместо O (n ^ 2). Дать общую сложность O (n * 2 ^ n)

Answer 10

да, это NP-полная проблема.

Трудно легко найти лучшую подматрицу, но мы можем легко найти лучшую подматрицу.

Предположим, что мы даем m случайных точек в матрице в качестве "каналов". затем позвольте им автоматически расширяться по таким правилам, как:

если добавить одну новую строку или столбец в матрицу подачи, убедитесь, что сумма будет инкрементной.

, тогда мы можем сравнить m подматрицу, чтобы найти лучшую.