Algorithme Diviser pour régner: trouver le minimum d'une matrice

Question

Je commence à apprendre à implémenter des algorithmes de division et de conquête, mais j'ai de sérieux problèmes avec cet exercice. J'ai écrit un algorithme qui trouve la valeur minimale dans un vecteur donné en utilisant la méthode diviser pour mieux régner:

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

Et ça marche. Maintenant, je dois faire le même exercice sur une matrice, mais je me perds. Spécifiquement, on m'a dit de faire ce qui suit: Soit n = 2^k. Considérons une matrice carrée nxn. Calculer sa valeur minimale en utilisant une fonction récursive

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

(est donné le type de matrice, et comme vous pouvez l'imaginer M.row donne le nombre de lignes et de colonnes de la matrice). Utiliser une fonction auxiliaire

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

Ceci doit être fait en utilisant un algorithme récursif de division et de conquête. Alors .. je ne peux pas trouver une façon de le faire. On m'a suggéré de diviser la matrice en 4 parties chaque fois (de (i, j) à (i + m/2, j + m/2), de (i + m/2, j) à (i + m, j + m/2), de (i, j + m/2) à (i + m/2, j + m), de (i + m/2, j + m/2) à (i + m, j + m)) et essayer d'implémenter un code fonctionnant de la même manière que celui que j'ai écrit pour le tableau .. mais je semble juste incapable de le faire. Aucune suggestion? Même si vous ne voulez pas poster une réponse complète, donnez-moi quelques indications. Je veux vraiment comprendre cela.

EDIT: Très bien, j'ai fait ça. Je poste le code que j'ai utilisé juste au cas où quelqu'un d'autre aurait le même doute.

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 fonction définie par ailleurs)

Answer 1

considérer qu'une matrice 2D en C ou C++ est souvent mis en œuvre en tant que fonctions d'accès au-dessus d'un tableau 1D. Vous savez déjà comment faire cela pour un tableau 1D, donc la seule différence est de savoir comment vous adressez les cellules. Si vous faites cela, votre performance sera intrinsèquement optimale car vous allez vous adresser aux cellules voisines ensemble. Alternativement, considérons qu'une matrice 2D a deux dimensions N et M. Il suffit de la diviser en deux dans la plus grande dimension jusqu'à ce que la plus grande dimension soit inférieure à X, une valeur raisonnable pour arrêter et faire le calcul réel séquentiellement. Ce n'est pas tout à fait optimal car vous devrez "sauter" des parties de la matrice lorsque vous adresserez de la mémoire.

Une idée finale consiste à diviser par la dimension principale d'abord, puis la dimension mineure. En C, cela signifie diviser par des lignes jusqu'à ce que vous ayez des lignes simples, puis exécutez votre algorithme de tableau 1D sur chaque ligne. Cela produit des performances à peu près optimales.