Discussion :

[AJMont]

Bonjour,

je cherche un moyen mathématique de réduire une matrice à sa sous-matrice unité maximale.
Voyons par l'exemple:

Une matrice carrée symétrique composée de 0 et de 1:
[[1, 0, 1, 1, 1]
[0, 1, 1, 0, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 0, 1, 1, 1]]
dans cet exemple la réduction se fait par la suppression de la ligne/colonne 2, donnant:
[[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]]

Ce cas est simple, mais je tente de réaliser ceci sur des matrices ayant des dimensions bien plus grandes et plus complexe que de supprimer juste une ligne/colonne...
Dans le cas optimum je souhaiterais connaitre les indices des colonnes/lignes restantes (dans le cas ci dessus: 1,3,4,5).

J'ai essayé par la combinatoire mais j'arrive a des Tera de données et des heures de calculs avec une matrice (162,162) qui dans mon cas est toujours une "petite" matrice.

Avez vous une solution?

[Invité]

salut,

avec un peu de retard et une réponse au ton négatif

si on suppose que ta matrice est symétrique, alors elle représente une matrice de relation.
...
tu peux transposer ce problème au intersecting family sets.
suppose chaque colonne de ta matrice un set.
et chaque coefficient qui vaut 1, disant que ce set est en relation avec le set en ligne

Trouver un gros carré de 1, ca signifie trouver des sets tels que tous soient en relation entre eux.
Le but étant évidemment de trouver le plus gros carré...

Tu peux regarder du côté de la sériation
www.sandia.gov/~bahendr/papers/seriation.ps
(tu permutes les colonnes/lignes, mais c'est la même chose que les supprimer)

Enfin pe qu'il y a un algo qui donne la solution optimale en un temps pas trop gros, et si oui j'aimerais vraiment le connaitre aussi!!
Pour ton cas, si en plus on suppose pas la matrice symétrique, bonne chance!

edit: j'enlève la ref à Blocki, ca n'a rien à voir avec le problème courant (pas la même somme pour chaque ligne, la matrice présente est moins contrainte)

[AJMont]

J'ai trouvé ça http://www.geeksforgeeks.org/maximum...binary-matrix/, c'est une approche qui me parait concluante si je la couple à un bout de code qui générera toute les permutations de la matrice initiale pour garder le meilleur résultat.

je pense essayer dès que j'aurais quelques minutes pour convertir ce code en python...

[Invité]

salut,

oui c'est une idée, mais bon 162! ca fait quand même beaucoup...

[AJMont]

Ma solution actuelle faisait C(163,x) avec x variant 1 à 163 (stoppant lorsqu'il trouve la solution)...
donc en l’occurrence c'est mieux

[Invité]

une variante à l'algo proposé dans ton lien est la suivante:
(ca reste pas très malin non plus)

on considère ta matrice M comme une matrice d'adjacence.
Idem on considère les noeuds.

on considère la matrice A, dont les éléments sont de type Block
Block contient
- liste de chemins
un chemin étant un tableau de noeuds (tous différents)

Block définit pour
- l'addition:

Code :

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

  result = Block(b1.listeChemins.concat(b2)) // et on elimine deux chemins identiques

- la multiplication:

Code :

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

1
2
3
4
5
6
7
  result = Block([].concatIf(b1.listeChemin, b2.listeChemin, function(cheminb1, cheminb2){
    si aucun des noeuds de cheminb1 sont dans cheminb2
     si aucun des noeuds de cheminb2 sont dans cheminb1
       si pour tous les noeuds de cheminb1 il existe une liaison avec chacun des noeuds de cheminb2
         si idem de cheminb2 vers cheminb1
          return true
  })

- la nullité (ya un nom mais j'ai oublié xD)
qqsoit n, result = Block de taille n * Block de taille 0 donne un Block de taille 0 (on considère Block de taille 0 comme l'élément absorbant 0)

- la taille:

Code :

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

  taille dun des chemins de listeChemins

la taille d'un chemin étant le nombre de noeuds _distincts_ dans le chemin.

ainsi un block de taille k * un block de taille n va donner un block de taille k+n

L'idée est donc d'exponentiatier (...) la matrice du genre
T = A*A //A^2
T = T*T //A^4
T = T*T //A^8
T = T*T //A^16 etc
jusqu'à ce que T soit vide, puis après on trouve k, tq A^k non nulle et A^(k+1) nulle.
k définissant alors notre plus grand chemin tel que tous les noeuds sont en relation

l'idée sous jacente, c'est que dans un block, on considère que tous les noeuds d'un chemin sont en relation. donc on s'épargne ces tests.


evidemment, on explose avec le stockage des données, mais comme t'as l'air d'avoir des tera à disposition...