分而治之算法：找到一个矩阵的最小值

我开始学习如何实现分治算法，但是我在这个练习中遇到了一些严重的麻烦。我已经写指找到使用分在给定的矢量的最小值的算法和方法克服：分而治之算法：找到一个矩阵的最小值

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。考虑一个n×n方阵。使用递归函数

double (minmatrix(Matrix M)) 
return minmatrix2(M, 0, 0, M.row);

计算其最小值（矩阵类型给出，并且作为可以想像M.row给出行和矩阵的列数）。使用辅助功能

double minmatrix2(Matrix M, int i, int j, int m)

这必须使用递归除法和征服算法完成。所以..我想不出一个办法。（i，j）到（i + m/2，j + m/2），从（i + m/2，j）到（i （i + m/2，j + m/2）到（i，m + 2，j + m） + 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); 
}

（功能分钟别处定义）

来源

2014-07-03 user3461126

考虑到在C或C++ 2D矩阵通常被实现为访问函数上的一维阵列的顶部。您已经知道如何对一维数组执行此操作，所以唯一的区别是您如何处理单元格。如果你这样做，你的表现本质上是最优的，因为你将一起解决相邻的细胞。

或者，考虑一个二维矩阵有两个维度N和M.只需将它沿着较大的维度反复分成两半，直到较大的维度小于X，一些合理的值停止并按顺序进行实际计算。这并不是完全最佳的，因为在处理内存时，您必须“跳过”矩阵的某些部分。

最后的想法是首先除以主要维度，然后是次要维度。在C中，这意味着按行划分，直到您有单行，然后在每行上运行您的一维数组算法。这产生大致最佳的性能。

来源

2014-07-03 13:20:53

分而治之算法：找到一个矩阵的最小值

回答

相关问题