#c #algorithm
Вопрос:
Мне нужно реализовать алгоритм максимальной суммы, который использует стратегию «разделяй и властвуй» на 2D-матрице. Я знаком с подходом грубой силы, который выполняется за O(n^6) времени, и алгоритмом Кадана, который выполняется за O(n^3), но как бы можно было реализовать подход «разделяй и властвуй»? Я думал об этом весь день, и ничего не приходит в голову. Чтобы обеспечить контекст, решение грубой силы заключается в следующем:
void maxSumBruteForce() {
vector<vector<int>> matrix = genRandomMatrix();
int maxSum = INT_MIN;
printMatrix(matrix);
for (int startRow = 0; startRow < matrix.size(); startRow) {
for (int startCol = 0; startCol < matrix.size(); startCol) {
for (int endRow = startRow; endRow < matrix.size(); endRow) {
for (int endCol = startCol; endCol < matrix.size(); endCol) {
int curSum = 0;
for (int row = startRow; row <= endRow; row) {
for (int col = startCol; col <= endCol; col) {
curSum = matrix[row][col];
}
}
if (curSum > maxSum)
maxSum = curSum;
}
}
}
}
cout << "MAX SUM: " << maxSum << endl;
}
Алгоритм Кадана можно найти здесь: https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/
Я полагаю, что решение проверит четыре квадранта матрицы, а затем различные комбинации середин.
Комментарии:
1. Тактическое примечание: Вундеркинды Для вундеркиндов практически не курируют контент, поэтому вам действительно нужно быть осторожным, когда вы получаете советы с сайта. Если вы уже не знаете большую часть того, что ищете, вы, возможно, не сможете отличить правильную работу гения от веселых разглагольствований кого-то, кто настолько неправ, что не может понять, что он не прав . Я видел более дикие произведения фэнтези о Гиках для гиков, чем за 40 лет игры в Damp;D.
2. Я понимаю, к чему вы клоните, но я видел несколько сайтов, подтверждающих решение, реализованное с помощью алгоритма Кадана. Я до сих пор не смог добиться какого-либо прогресса в решении этой проблемы.
3. Кадане можно переформулировать как разделяй и властвуй: personal.utdallas.edu/~daescu/maxsa.pdf .
4. Подобные проблемы, как правило, очень эффективно решаются с помощью методов динамического программирования.
5. @DavidEisenstat Я видел, как это использовалось для задачи максимального подмножества, но моя проблема заключается в том, чтобы найти максимальный прямоугольник. Я действительно не знаю, как с этим поступить. Я также понимаю, что обычно динамическое программирование было бы правильным решением, но мне сказали реализовать решение «разделяй и властвуй», а не динамическое программирование.
Ответ №1:
Одним из способов адаптации статьи 1, которой Дэвид Эйзенстат поделился в комментариях, может быть следующее:
Если мы разделим прямоугольник на два,
-------------------
| | |
| | |
| A | B |
| | |
| | |
-------------------
либо максимальная сумма A B указана, либо она указана, либо она находится в прямоугольнике, который имеет часть A и часть B . Для вычисления последнего мы используем с каждой стороны total_sum , max_sum , max_prefix , max_suffix , для каждой O(num_rows^2) границы строки.
A
---------------
| |
|-----row_i-----|
| |
|<--total_sum-->|
| |
|max_pfx--| |
| |--max_sfx|
| |
|-----row_j-----|
| |
| |
---------------
Затем для каждого окна строк row_i до row_j , из A и B мы имеем:
total_sum_AB = total_sum_A total_sum_B
max_prefix_AB = max(max_prefix_A, total_sum_A max_prefix_B)
max_suffix_AB = max(max_suffix_B, max_suffix_A total_sum_B)
max_sum_AB = max(max_sum_A, max_sum_B, max_suffix_A max_prefix_B)
Код на Python:
def g(M, num_rows, l, r):
dp = [[None] * num_rows for _ in range(num_rows)]
if l == r:
for i in range(num_rows):
dp[i][i] = [M[i][l], M[i][l], M[i][l], M[i][l]]
for j in range(i 1, num_rows):
dp[i][j] = [M[j][l] dp[i][j-1][0], M[j][l] dp[i][j-1][1], M[j][l] dp[i][j-1][2], M[j][l] dp[i][j-1][3]]
return dp
mid = l (r - l) // 2
dp_l = g(M, num_rows, l, mid)
dp_r = g(M, num_rows, mid 1, r)
for i in range(num_rows):
for j in range(i, num_rows):
[total_sum_l, max_sum_l, max_pfx_l, max_sfx_l] = dp_l[i][j]
[total_sum_r, max_sum_r, max_pfx_r, max_sfx_r] = dp_r[i][j]
total_sum = total_sum_l total_sum_r
max_pfx = max(max_pfx_l, total_sum_l max_pfx_r)
max_sfx = max(max_sfx_r, total_sum_r max_sfx_l)
max_sum = max(max_sum_l, max_sum_r, max_sfx_l max_pfx_r)
dp[i][j] = [total_sum, max_sum, max_pfx, max_sfx]
return dp
def f(M):
num_rows = len(M)
dp = g(M, num_rows, 0, len(M[0]) - 1)
best = -float('inf')
for i in range(num_rows):
for j in range(i, num_rows):
[total_sum, max_sum, max_pfx, max_sfx] = dp[i][j]
best = max(best, max_sum, max_pfx, max_sfx)
return best
Выход:
M = [
[ 1, 2, -1, -4,-20],
[-8, -3, 4, 2, 1],
[ 3, 8, 10, 1, 3],
[-4, -1, 1, 7, -6]
]
print(f(M)) # 29
"""
[ 1, 2, -1, -4,-20],
-----------
[-8,| -3, 4, 2,| 1],
[ 3,| 8, 10, 1,| 3],
[-4,| -1, 1, 7,| -6]
-----------
"""
Разделяй и властвуй наносит ответный удар: максимум-подмножество в линейное время 1 (Овидиу Даеску и Шейн Сент-Люс, Факультет компьютерных наук, Техасский университет в Далласе)