Алгоритм разделяй и властвуй: найди минимум матрицы
Я начинаю учиться реализовывать алгоритмы «разделяй и властвуй», но у меня возникли серьезные проблемы с этим упражнением.
Я написал алгоритм, который находит минимальное значение в данном векторе, используя метод «разделяй и властвуй»:
int minimum (int v[], int inf, int sup)
{
int med, m1, m2;
if (inf == sup)
return v[inf];
med = (inf+sup)/2;
m1 = minimum (v, inf, med);
m2 = minimum (v, med+1, sup);
if (m1 < m2)
return m1;
else
return m2;
}
И это работает. Теперь я должен выполнить то же упражнение на матрице, но я заблудился. В частности, мне сказали сделать следующее:
Пусть n = 2 ^ k. Рассмотрим квадратную матрицу nxn. Рассчитать его минимальное значение с помощью рекурсивной функции
double (minmatrix(Matrix M))
return minmatrix2(M, 0, 0, M.row);
(Тип Matrix указан, и, как вы можете себе представить, M.row дает количество строк и столбцов матрицы). Используйте вспомогательную функцию
double minmatrix2(Matrix M, int i, int j, int m)
Это должно быть сделано с использованием рекурсивного алгоритма «разделяй и властвуй».
Так что .. я не могу найти способ сделать это. Мне было предложено разбивать матрицу на 4 части каждый раз (от (i, j) до (i + m / 2, j + m / 2), от (i + m / 2, j) до (i + m, j + m / 2), от (i, j + m / 2) до (i + m / 2, j + m), от (i + m / 2, j + m / 2) до (i + m, j + m)) и попытаться реализовать код, работающий аналогично тому, который я написал для массива … но я просто не могу этого сделать. Какие-либо предложения? Даже если вы не хотите публиковать полный ответ, просто дайте мне несколько указаний. Я действительно хочу понять это.
РЕДАКТИРОВАТЬ: Хорошо, я сделал это. Я публикую код, который использовал, на тот случай, если у кого-то еще возникнут те же сомнения.
double minmatrix2(Matrix M, int i, int j, int m)
{
int a1, a2, a3, a4;
if (m == 1)
return M[i][j];
else
a1 = minmatrix2(M, i, j, m/2);
a2 = minmatrix2(M, i+(m/2), j, m/2);
a3 = minmatrix2(M, i, j+(m/2), m/2);
a4 = minmatrix2(M, i+(m/2), j+(m/2), m/2);
if (min (a1, a2) < min (a3, a4))
return min (a1, a2);
else
return min (a3, a4);
}
(функция min определена в другом месте)
Решение
Учтите, что 2D-матрица в C или C ++ часто реализуется как функции доступа поверх одномерного массива. Вы уже знаете, как это сделать для одномерного массива, поэтому единственная разница заключается в том, как вы обращаетесь к ячейкам. Если вы сделаете это, ваша производительность будет оптимальной, потому что вы будете обращаться к соседним ячейкам вместе.
В качестве альтернативы, рассмотрим, что двумерная матрица имеет два измерения N и M. Просто разбейте ее пополам вдоль большего измерения несколько раз, пока большее измерение не станет меньше X, какое-то разумное значение, чтобы остановить и выполнить фактические вычисления последовательно. Это не совсем оптимально, потому что вам придется «пропускать» части матрицы при обращении к памяти.
Последняя идея состоит в том, чтобы сначала разделить по главному измерению, а затем по второстепенному. В C это означает деление на строки до тех пор, пока у вас не появятся отдельные строки, а затем запустите алгоритм 1D-массива для каждой строки. Это дает примерно оптимальную производительность.
Другие решения