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

Question

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

Answer 1

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;
}

Answer 2

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

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

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

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

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

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

Answer 3

Это проблема оптимизации и может быть решена приблизительно с помощью итерационного алгоритма, основанного на имитации отжига :

Обозначение: C - количество столбцов.

Для J итераций:

1. Посмотрите на каждый столбец и вычислите абсолютную выгоду его переключения (выключите, если он в данный момент включен, или включите, если он в данный момент выключен). Это дает вам значения C, например, -3, 1, 4. Жадное детерминированное решение просто выберет последнее действие (переключите последний столбец, чтобы получить преимущество 4), потому что оно локально улучшает цель. Но это может привести нас к локальному оптимуму. Вместо этого мы вероятностно выбираем одно из трех действий с вероятностями, пропорциональными выгодам . Чтобы сделать это, преобразуйте их в распределение вероятностей, поместив их через сигмовидную функцию и нормализуя. (Или используйте exp () вместо sigmoid ()?) Так что для -3, 1, 4 вы получите 0,05, 0,73, 0,98 от сигмоида и 0,03, 0,42, 0,56 после нормализации. Теперь выберите действие в соответствии с распределением вероятностей, например, последний столбец с вероятностью 0,56, второй столбец с вероятностью 0,42 или первый столбец с малой вероятностью 0,03.

2. Выполните ту же процедуру для строк, что приведет к переключению одной из строк.

Итерация для J итераций до сходимости.

Мы также можем на ранних итерациях сделать каждое из этих вероятностных распределений более равномерным, чтобы на раннем этапе мы не были привязаны к неправильным решениям. Таким образом, мы бы повысили ненормированные вероятности до степени 1 / T, где T является высоким на ранних итерациях и медленно уменьшается до тех пор, пока не достигнет 0. Например, 0,05, 0,73, 0,98 сверху, повышенный до 1/10, приводит к 0,74 , 0,97, 1,0, что после нормализации составляет 0,27, 0,36, 0,37 (так что оно намного более однородно, чем исходные 0,05, 0,73, 0,98).

Answer 4

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

2    1

3    -10

Строка (0) = 3 Ряд (1) = -7 Col (0) = 5 Col (1) = -9

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

Cost to take row      Cost to take column
       3                      5

      -7                      -9

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

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

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

Answer 5

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

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

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

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

То есть: 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. Если возвращаемое значение рекурсивного вызова превышает сохраненную сумму, замените его и сохраните возвращенный список перемещения.

4. Вернуть сохраненную сумму и переместить список.

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

Answer 6

Я не могу действительно создать алгоритм поверх моей головы, но для меня он «пахнет», как динамическое программирование, если он служит отправной точкой.