Discussion :

[potimarara]

bonjour,
je souhaite lister avec un temps de calcul le plus faible possible la totalité des sous-matrices carrées d'une matrice de dimension n*n.
quelqu'un a t-il une idée?
merci d avance

bonne journée
yoann

[millie]

lister avec un temps de calcul le plus faible possible

Quand tu dis lister. Tu souhaites également une recopie mémoire de toutes les matrices ?

Ou une liste d'indication du style : (Entier x, Entier y, Entier tailleX, Entier tailleY) suffirait ? (ce qui serait nettement plus rapide)


Pour indication en cas de recopie, la taille que tu prendrais en mémoire serait de :
somme(i=0 à n-1, (i+1)² * (n-i)²) qui est minoré par n^3

Rien que pour une matrice de 1000 * 1000 ( environ 1 mo) prenderai plus de 1go.

EDIT : Après, calcul, on peut montrer que la somme vaut :
1/3*n^3+1/3*n^2+1/6*n^4+2/15*n+1/30*n^5 donc : O(n^5)

Dans le second cas, ça devient assez simple.

Il suffit de faire aller x de 1 à n et y de 1 à n
et tailleX de 1 à n-x et tailleY de 1 à n-y.

[potimarara]

par "lister" j'entends calculer toutes les sous-matrices carrées... je ne veux ensuite conserver en mémoire que les sous-matrices identité (mais ça c'est un autre pb).

[millie]

je ne veux ensuite conserver en mémoire que les sous-matrices identité (mais ça c'est un autre pb).

En fait, non, pas tout à fait. Si tu veux un algorithmique optimal, autant prendre en compte cette propriété. Ce qui fait que si la sous matrice ne commence par exemple pas par 1 en 1,1, alors ce n'est pas la peine de construire la sous matrice.

Par exemple, comme tu souhaites uniquement chercher des matrices carrés.
Tu peux coder ta sous matrice avec 2 entiers, position horizontale, position verticale et taille.

Tu peux ainsi utiliser une fonction : estUneSousMatriceIdentite qui te permet de savoir immédiatement si cette matrice est une matrice identité.

Donc t'auras une algo du style (ya surement une faute dans les indices, ça dépend où commence ta matrice) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
Pour x= 1 à n
 Pour y = 1 à n
  Pour taille = 1 à min(n-x, n-y)
    Si estUneSousMatriceIdentite(M, x,y, taille) alors
      ajouterListe((x,y,taille))

[potimarara]

parfait!
effectivement je peux me limiter à une triple boucle imbriquée vu que je recherche des matrices carrées.
merci bien, je ne suis pas informaticien, et je peine à chaque fois que je dois y avoir recours.
bonne soirée

[millie]

Ca dépend de comment tu souhaites utiliser tes matrices identités.

Mais tu peux simplifier encore plus. Si par exemple tu ne souhaites connaître uniquement leur taille. Alors, dans la liste, tu peux juste mettre la taille.

Et donc utiliser un tableau T de taille n initialisé à 0.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Pour x= 1 à n
 Pour y = 1 à n
  Pour taille = 1 à min(n-x, n-y)
    Si estUneSousMatriceIdentite(M, x,y, taille) alors
      T[taille]++

Ainsi, il suffirait de parcourir le tableau ensuite pour connaitre à chaque fois le nombre de matrice identité d'une certaine taille. Mais ça dépend de à quoi ça va te servir.


Edit : il y a une optimisation ultime ::::: lol
Tu décrementes la taille. Si un moment, c'est une sous matrice identité, alors tu peux compter exactement le nombre de sous matrice identité qui se trouve dedans. Ce qui fait que tu n'as plus besoin de parcourir tout l'intervalle 1 à min(n-x, n-y). Mais bon, ça complique et ça n'est pas forcement utile.

[potimarara]

en fait ce qui m interesse c'est de recuperer les indices x et y des sous-matrices identité de dimension max... c'est une bidouille qui vient s'insérer dans un code déjà assez retors.
ta réponse me va très bien.

[millie]

Bien, c'est cool.


Pense à l'icone : en bas pour indiquer que c'est bon.

[Jean-Marc.Bourguet]

en fait ce qui m interesse c'est de recuperer les indices x et y des sous-matrices identité de dimension max... c'est une bidouille qui vient s'insérer dans un code déjà assez retors.
ta réponse me va très bien.

En pseudo C++, un algo en nb_cols*nb_rows. Mémoire auxilliaire: 4*nb_rows (mais si les deux sont différents, tu peux évidemment transposer). Tel qu'écrit, la condition au limite n'est pas traitée explicitement, une bordure de 2 autour de la matrice devrait faire l'affaire.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for (i = 0; i < nb_cols; ++i) {
  for (j = 0; j < nb_rows; ++j) {
    if (mat(i, j) == 1) {
      unit(j) = 1 + max(old_unit(j), max(zero_vert(j), zero_hor(j-1)));
      if (unit(j) > max_unit) {
        max_unit = unit(j);
        maxs.clear();
      }
      if (unit(j) == max_unit) {
        maxs.push(make_pair(i, j));
      }
    }
    if (mat(i, j) == 0) {
      ++zero_vert(j);
      zero_hor(j) = zero_hor(j-1) + 1;
    } else {
      zero_vert(j) = 0;
      zero_hor(j) = 0;
    }
  }
  old_unit = unit;
}