分治算法:求矩阵的最小值
我开始学习如何实现分而治之的算法，但是我在这个练习中遇到了一些严重的问题。我编写了一种算法，它使用分而治之的方法在给定的向量中找到最小值：
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);(给出了矩阵类型，正如您可以想象的那样，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 )
回答 1
Stack Overflow用户
发布于 2014-07-03 05:20:53
考虑到C或C++中的2D矩阵通常是作为一维数组之上的访问器函数实现的。您已经知道如何对一维数组执行此操作，因此唯一的区别是如何处理单元格。如果您这样做，您的性能将在本质上是最佳的，因为您将寻址相邻的单元。
或者，考虑一个二维矩阵有二维N和M，只要沿着较大维数反复地将其分解成一半，直到较大维数小于X，一些合理的值就可以停止并按顺序进行实际计算。这并不完全是最优的，因为在寻址内存时，您必须“跳过”矩阵的部分内容。
最后一个想法是先除以主要维度，然后再除以次要维度。在C中，这意味着除以行，直到有一行，然后在每一行上运行您的一维数组算法。这产生了大致最优的性能。
https://stackoverflow.com/questions/24554549
复制
腾讯云开发者
