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

This is an optimization problem and can be solved approximately by an iterative algorithm based on simulated annealing:

Notation: C is number of columns.

For J iterations:

1. Look at each column and compute the absolute benefit of toggling it (turn it off if it's currently on or turn it on if it's currently off). That gives you C values, e.g. -3, 1, 4. A greedy deterministic solution would just pick the last action (toggle the last column to get a benefit of 4) because it locally improves the objective. But that might lock us into a local optimum. Instead, we probabilistically pick one of the three actions, with probabilities proportional to the benefits. To do this, transform them into a probability distribution by putting them through a Sigmoid function and normalizing. (Or use exp() instead of sigmoid()?) So for -3, 1, 4 you get 0.05, 0.73, 0.98 from the sigmoid and 0.03, 0.42, 0.56 after normalizing. Now pick the action according to the probability distribution, e.g. toggle the last column with probability 0.56, toggle the second column with probability 0.42, or toggle the first column with the tiny probability 0.03.

2. Do the same procedure for the rows, resulting in toggling one of the rows.

Iterate for J iterations until convergence.

We may also, in early iterations, make each of these probability distributions more uniform, so that we don't get locked into bad decisions early on. So we'd raise the unnormalized probabilities to a power 1/T, where T is high in early iterations and is slowly decreased until it approaches 0. For example, 0.05, 0.73, 0.98 from above, raised to 1/10 results in 0.74, 0.97, 1.0, which after normalization is 0.27, 0.36, 0.37 (so it's much more uniform than the original 0.05, 0.73, 0.98).

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

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

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

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

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

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

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

Т.е.: r1, r1

Будет переводить

-1  1  0           1  1  1
-4  1 -4           5  7 1
 1  2  4    ===>  
 5  7  1  

1. Вернуть, если сумма матрицы является теоретическим максимумом

2. Найдите позиции всех отрицательных элементов, если не был передан пустой набор.

3. Вычислите сумму матрицы и сохраните ее рядом с пустым списком ходов.

   • Для каждого отрицательного элемента:

     2. Вычислите сумму этого строка и столбец элемента.

     3. клонируйте матрицу и удалите любую коллекцию, имеющую минимальную сумму (строку / столбец) из этого клона, обратите внимание на это действие как список перемещений.

     4. клонируйте список отрицательных элементов и удалите все, что вызвано действием, предпринятым на предыдущем шаге.

     5. Рекурсивно вызовите этот алгоритм, предоставив клонированную матрицу, обновленный список отрицательных элементов и теоретический максимум. Добавить список ходов, возвращенный к списку ходов для действия, которое произвело матрицу, переданную рекурсивному вызову.

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

     7. 12116] Вернуть сохраненную сумму и список перемещений.

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

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

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

   • 12116] Вернуть сохраненную сумму и список перемещений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

если (1) меньше текущей вычисляемой наивысшей максимальной суммы, то эту матрицу nxm можно отбросить. Если (2) истинно, то вам просто нужно простое сравнение с текущей наивысшей максимальной суммой.

Обычно это называют методом отсечения .

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

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

Возьмите каждую строку и каждый столбец и вычислите сумму. Для матрицы 2x2 это будет:

2    1

3    -10

Row (0) = 3 Ряд (1) = -7 Столбец (0) = 5 Col (1) = -9

Составьте новую матрицу

Cost to take row      Cost to take column
       3                      5

      -7                      -9

Выньте все, что вам нужно, затем начните заново.

Вы просто ищите отрицательные значения в новой матрице. Это значения, которые фактически вычитаются из общего значения матрицы. Он завершается, когда больше нет отрицательных значений "СУММ" для удаления (поэтому все столбцы и строки СУММУЮТ что-то к окончательному результату)

В матрице nxn, которая будет O (n ^ 2) Log (n) I думаю

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

Это итеративный вариант, улучшающий другой ответ. Он работает за время 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

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

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

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

Здесь ' s пример реализации на 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)])

function pruneMatrix(matrix) {
  max = -inf;
  bestRowBitField = null;
  bestColBitField = null;
  for(rowBitField=0; rowBitField<2^matrix.height; rowBitField++) {
    for (colBitField=0; colBitField<2^matrix.width; colBitField++) {
      sum = calcSum(matrix, rowBitField, colBitField);
      if (sum > max) {
        max = sum;
        bestRowBitField = rowBitField;
        bestColBitField = colBitField;
      }
    }
  }
  return removeFieldsFromMatrix(bestRowBitField, bestColBitField);
}

function calcSumForCombination(matrix, rowBitField, colBitField) {
  sum = 0;
  for(i=0; i<matrix.height; i++) {
    for(j=0; j<matrix.width; j++) {
      if (rowBitField & 1<<i && colBitField & 1<<j) {
        sum += matrix[i][j];
      }
    }
  }
  return sum;
}

Это явно NP-Complete (как указано выше). Учитывая это, если бы мне пришлось предложить лучший алгоритм, который я мог бы решить для проблемы:

• Попробуйте несколько итераций квадратичного целочисленного программирования, сформулировав задачу как: SUM_ij a_ij x_i y_j , с переменными x_i и y_j должно быть либо 0, либо 1. Для некоторых матриц, я думаю, это быстро найдет решение, для самых сложных случаев это было бы не лучше, чем грубая сила (и не намного).

• Параллельно (и с использованием большей части CPU) используйте приблизительный алгоритм поиска, чтобы генерировать все более лучшие решения. Имитация отжига была предложена в другом ответе, но, проведя исследование аналогичных задач комбинаторной оптимизации, мой опыт показывает, что запретный поиск быстрее находит хорошие решения. Это, вероятно, близко к оптимальному с точки зрения перехода между отдельными «потенциально лучшими» решениями в кратчайшие сроки, если вы используете уловку постепенного обновления стоимости отдельных изменений (см. Мою статью «Преобладание графа, поиск запретов и проблема футбольного пула ").

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

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

Остановка на определении того, что проблема, скорее всего, будет NP-Complete, не будет хорошо смотреться на собеседовании! (Если работа не связана с теорией сложности, но даже в этом случае я бы не стал). Вам нужно предложить хорошие подходы - в этом суть такого вопроса. Чтобы увидеть, что вы можете придумать под давлением, потому что в реальном мире часто приходится заниматься такими вещами.

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

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

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

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

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