Sélectionner des colonnes et des lignes dans une (grosse) matrice de façon à maximiser la somme des cellules

Bonjour,

J'ai une matrice 134x190 remplie de nombre positifs avec une majorité de 0 (env 85%).
Je cherche à sélectionner 30 colonnes et 30 lignes de façon a ce que la somme des cellules de la "sous matrice" ainsi obtenue soit maximale.
D'après mes calculs ça fait 5,6x10^64 combinaisons possibles, donc impossible de faire un algo naif.

Je sèche sur l'algo à utiliser, je pense qu'il y a des algos qui répondent à ce problème mais je n'en trouve pas.


Je vous remercie d'avance si vous pouvez m'aider.

Bonjour.

Votre sous-matrice 30x30 est-elle constituée de valeurs contiguës dans la matrice initiale ?

En d'autres termes, est-elle un carré parfait inclus dans la matrice ?

Cdlt

Non, l'ordre des lignes/colonnes n'a aucune importance dans la matrice (sinon il n'y aurait "que" quelques dizaines de milliers de solutions possibles donc ça serait possible de toutes les tester).

Comme j'ai pas forcément besoin de la solution optimale j'ai fait un algo tout bête qui me donne une solution sub-optimale : dans une boucle je retire la ligne ou la colonne avec le plus petit score, et ce jusqu'à arriver au nombre de colones/lignes voulues.

Vu que les valeurs de ma matrice ne sont pas aléatoires mais que j'ai des colonnes/lignes avec des scores beaucoup plus élevés que d'autres, j’obtiens une matrice qui doit être très proche de la solution optimale (ce qui me conviens).

Si tu calcules ce que l'on appelle "integral image" ou dans ton cas "integral matrix", en deux passes de ta matrices tu devrais avoir ta réponse.

Je ne cherche pas un "rectangle" mais 30 lignes et 30 colonnes quelconques, pas forcément contiguës, donc l'image intégrale ne s'applique pas ici.

Ce n'est pas du traitement d'image même si je comprends qu'en lisant vite on puisse le croire. En fait ma matrice représente une série d'expériences réalisées avec 2 différentes modalités (une présentée en ligne dans la matrice, une en colonne), le nombre attribué à chaque cellule correspond au nombre d'observations. Et j'essaye de réduire le jeu de données de façon a avoir le moins de données manquantes.

La matrice intégrale est une représentation de ta matrice qui te permet de faire des calculs d'intégrales super rapidement par la suite.
Hors tu souhaites maximiser les valeurs dans une zone de 30x30.
Donc ça s'applique.

Citation:

---

Envoyé par ToTo13

Hors tu souhaites maximiser les valeurs dans une zone de 30x30.

---

Non, je veut pas maximiser les valeurs d'une zone 30x30 mais sélectionner 30 lignes et 30 colonnes qui ne sont pas forcément à la suite. Par exemple si je voulais une matrice 3x3 je pourrais très bien prendre les lignes 5, 28 et 56 et les colonnes 98, 107 et 2.

Ok.
Pour accélérer ta recherche, tu pourrais pré-calculer la somme de chaque ligne/colonne.
Puis tu tries les lignes et les colonnes.
Tu ne gardes que les plus grandes valeurs.

Sauf si tu ne t'intéresses qu'à la somme des intersections de tes lignes/colonnes.