Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 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) отсутствует в графике.

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

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

Это обычно называют техникой обрезки.

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

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

Ответ 3

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

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

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

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

Ответ 4

Попробуйте сделать это простым способом:

Нам нужно действительное подмножество множества элементов {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)).

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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

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

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

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

Ответ 8

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

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

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

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

Ответ 9

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

Ответ 10

Big Edit: Я, честно говоря, не думаю, что есть способ оценить матрицу и определить ее максимально, если она не будет полностью положительной.

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

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

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

Ie: r1, r1

Перевел

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

  • Возвращается, если сумма матрицы является теоретическим максимумом

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

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

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

      1. Рассчитайте сумму этой строки и столбца элемента.

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

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

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

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

Возвращает сохраненную сумму и список перемещения.

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

Ответ 11

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

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

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

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

  • Проделайте ту же процедуру для строк, что приведет к переключению одной из строк.

Итерации для 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).

Ответ 12

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

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

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

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

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

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

Ответ 13

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

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

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

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

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

Ответ 14

Скажем, n = 10.

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

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

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

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

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

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

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

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

Добавление метода обрезки показало это в среднем до 600 узлов.

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

Ответ 15

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

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", чтобы вынуть (поэтому все столбцы и строки SUM что-то до конечного результата)

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

Ответ 16

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