IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éclairé
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Janvier 2012
    Messages
    325
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : Janvier 2012
    Messages : 325
    Points : 888
    Points
    888
    Par défaut 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.

  2. #2
    Inactif  
    Homme Profil pro
    Inscrit en
    Janvier 2014
    Messages
    374
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations forums :
    Inscription : Janvier 2014
    Messages : 374
    Points : 479
    Points
    479
    Par défaut
    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

  3. #3
    Membre éclairé
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Janvier 2012
    Messages
    325
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : Janvier 2012
    Messages : 325
    Points : 888
    Points
    888
    Par défaut
    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).

  4. #4
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #5
    Membre éclairé
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Janvier 2012
    Messages
    325
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : Janvier 2012
    Messages : 325
    Points : 888
    Points
    888
    Par défaut
    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.

  6. #6
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  7. #7
    Membre éclairé
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Janvier 2012
    Messages
    325
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : Janvier 2012
    Messages : 325
    Points : 888
    Points
    888
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    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.

  8. #8
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

Discussions similaires

  1. total colonne et total ligne dans une requete croisée
    Par maamer dans le forum Requêtes et SQL.
    Réponses: 6
    Dernier message: 11/06/2018, 13h37
  2. Insérer des données sur plusieurs lignes dans une seule en SQL
    Par nathantahiti dans le forum Développement
    Réponses: 1
    Dernier message: 03/08/2011, 11h47
  3. [AC-2007] En-tête de colonne sur plusieurs lignes dans une list box
    Par Rémi GAUDINAT dans le forum IHM
    Réponses: 2
    Dernier message: 25/10/2010, 12h52
  4. Réponses: 8
    Dernier message: 22/03/2010, 11h32
  5. Réunir des colonnes de tables différentes dans une requête
    Par GCAccess dans le forum Modélisation
    Réponses: 3
    Dernier message: 14/03/2009, 00h59

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo