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 :

recherche de meilleure solution, nombre de combinaison gigantesque


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre émérite
    Profil pro
    Assistant recherche bioinformatique
    Inscrit en
    Novembre 2007
    Messages
    877
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations professionnelles :
    Activité : Assistant recherche bioinformatique

    Informations forums :
    Inscription : Novembre 2007
    Messages : 877
    Par défaut recherche de meilleure solution, nombre de combinaison gigantesque
    Bonjour,

    Je bosse dans la bioinformatique, et j'e bosse sur une puce a ADN.
    Le problème est le suivant :
    Je dois selectionner le plus petit nombre de sondes possibles qui fixeront toutes les sequences ADN (des cibles) en présence.

    Les données :
    Pour chaque sonde, j'ai le nombre de cibles qu'elle fixera.
    Je connais le nombre total de cible qui est 148.
    J'ai approximativement 800 000 sondes.

    Mon algo actuel :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Tant qu'on a pas recupéré les 148 cibles
        Parcourir la liste de sonde a la recherche de celle qui ajoute le plus de nouvelles cibles
        Ajouter cette sonde a la liste de sondes selectionnées
        Ajouter cette liste de cible a la liste de cible des sondes selectionnées
    fin tant que
    De cette sorte, je desends a 12 sondes.
    Tester toutes les combinaisons de 800 000 sondes est impossible !
    Mais j'ai bon espoir de trouver une piste d'algo heuristique ou stochastique qui me permettra d'augmenter ce score, grace a votre aide

    Merci,
    Z.

  2. #2
    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 : 46
    Localisation : Etats-Unis

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

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    pourquoi ne testes tu pas une recherche tabou. Ca convient parfaitement à tout ce qui est problème binaire.
    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.

  3. #3
    Membre émérite
    Profil pro
    Assistant recherche bioinformatique
    Inscrit en
    Novembre 2007
    Messages
    877
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations professionnelles :
    Activité : Assistant recherche bioinformatique

    Informations forums :
    Inscription : Novembre 2007
    Messages : 877
    Par défaut
    Merci de ta réponse.
    Je ne connais pas la recherche tabou, mais j'ai une piste pour commencer mes recherches !
    Z.

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    C'est un problème de "Partial Set Cover", comme dans les systèmes réducteurs ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    une idée serait de trier les sondes par nombre de cibles (qsort).


  6. #6
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2007
    Messages
    123
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2007
    Messages : 123
    Par défaut
    Dans ce cas, (presque académique, je t'envie), j'utiliserais une optimisation par Branch & Bound.

    En gros tu poses toutes les combinaisons possibles sous forme d'un arbre, et tu te rends compte que le nombre est gigantesque. Impossible de toutes les explorer ! C'est là que l'algo Branch & Bound intervient en supprimant en cours de route des pans entiers de ton arbre que l'on sait non intéressants sans l'explorer pour autant en entier.

    Alors dans ton cas, ton arbre aurait une profondeur variable (mais pas vraiment en fait en formalisant bien comme il faut), et tu chercherais en fait les branches les plus courtes, ce qui s'intègre parfaitement dans cet algorithme au prix d'une petite modif.

    N'hésite pas à me contacter pour plus de détails, j'adore ce type de problème.

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 25
    Par défaut Un idée
    Ton algo initial me semble bien adapté : pas excessivement long, ne parcours pas toutes les possibilités et aboutit à une solution qui devrait être en général assez bonne, même s'il n'aboutit pas obligatoirement à la meilleure solution.

    En revanche, la solution que tu trouves n'est peut-être pas minimale. C'est-à-dire, qu'il se peut que certaines sondes retenues ne servent finalement à rien. Dans la solution finale, il y a peut-être des sondes qui peuvent être supprimées, sans perdre aucune cible. Ca mériterait d'être vérifié pour éventuellement affiner le résultat et obtenir une solution minimale (à défaut d'être optimale).

    D'ailleurs, cela me me fait penser à un autre algo, qui est un peu l'inverse du tiens.

    Au départ, on considère que toutes les sondes sont sélectionnées, donc on a bien le maximum de cibles (toutes). Ensuite, on effectue une boucle qui retire une sonde qui n'enlève pas de cible et qui contient un nombre de cible minimal.

    En pseudo-code, ça donne ça :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Retenir à priori toutes les sondes (le maximum de cibles sont trouvées).
    Tant qu'on peut enlever une sonde sans perdre de cible
            Rechercher une sonde qui peut être supprimée et qui possède le plus petit nombre de cibles.
            Supprimer cette sonde.
    Fin tant que
    Comme ton algo initial, il n'y a aucune garantie d'aboutir à une solution optimale. Mais la solution trouvée devrait ne pas être trop mauvaise non plus, tout en étant différente de celle que tu trouves. D'autre part, la solution trouvée par mon algo serait "minimale" dans le sens ou il est impossible de supprimer une sonde sans perdre une cible.

    En fait, suivant la configuration de départ, un algo peut aboutir à un meilleur résultat que l'autre. De même, celui proposé par souviron34 est très bon aussi et abouti à une autre solution minimale (mais pas obligatoirement "optimale"), qui suivant la configuration de départ, peut être meilleure ou moins bonne que les notres.

    Je pense que tu dois pouvoir "mixer" ses approches de diverses manières.

    Tu peux par exemple partir d'une solution minimale (par exemple, celle rendue par mon algorithme ou bien rendue par ton algorithme après "affinage" ou bien rendue par l'algorithme de souviron34) et essayer de "dériver" une meilleure solution de la manière suivante :
    1- Ajouter quelques sondes (choisies au hasard ou bien en privilégiant celles qui ont beaucoup de cibles),
    2- Supprimer les sondes inutiles selon mon algorithme (celles qui contribuent le moins de cibles sont supprimées en premier).

    En partant d'une solution et en faisant plusieurs essais de "raffinage" selon cette méthode (en faisant varier les sondes ajoutées à l'étape 1), tu as des chances trouver une meilleure solution. Tu peux arrêter le raffinage lorsque tu n'arrives plus à améliorer malgré N essais ou en fonction d'une durée.

Discussions similaires

  1. La meilleure solution recherche full text ?
    Par oveka dans le forum Zend Framework
    Réponses: 3
    Dernier message: 15/08/2013, 15h39
  2. Réponses: 0
    Dernier message: 17/06/2010, 14h22
  3. Réponses: 26
    Dernier message: 08/11/2007, 20h19
  4. meilleur solution pour créer un document imprimable???
    Par martimacfly dans le forum XML/XSL et SOAP
    Réponses: 26
    Dernier message: 08/07/2004, 10h09

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