Partage
  • Partager sur Facebook
  • Partager sur Twitter

Résoudre un système d'(in+)équation "binaire"

Sujet résolu
    15 juin 2019 à 22:19:25

    Bonjour,

    J'aimerais savoir comment trouver les solutions du système, ou tout du moins savoir s'il y en a au moins une.

    Le système suivant n'est qu'un exemple, mais j'aimerais pouvoir appliquer la méthode de résolution à un algorithme et résoudre des systèmes plus grands.

    Le système:

    a+f    +d        =  2
        f+c+d+e    >=2
               d+e+b=  2
    a    +c   +e    =  2
    a+f       +e+b>=2
        f+c       +b=   2

    Avec les inconnues a,b,c,d,e,f égalent à 0 ou 1.

    Je suppose qu'on peut appliquer le pivot de Gauss pour les égalités ?

    a+f           +d=  2
        f+c       +b=  2
          2c-d+e-b=   2
              d+e+b=   2

    a+f        +e+b>=2
        f+c+d+e    >=2

    Et après, on fait comment ? (le fait que ce soit un mélange d'équation/d'inéquation avec des variables binaire me perturbe un peu...^^')

    -
    Edité par MrSiuol 15 juin 2019 à 22:19:57

    • Partager sur Facebook
    • Partager sur Twitter
      15 juin 2019 à 22:46:27

      L'information ESSENTIELLE, c'est celle que tu donnes en dernier : a,b,c,d,e,f prennent leurs valeurs dans {0,1}

      Du coup, le pivot de Gauss, il ne sert à rien. Le pivot de Gauss, il va nous emmener vers des solutions réelles quelconques.

      Y a-t-il au moins une solution.  On va être bourrin, on a 2^6=64 combinaisons à regarder, ça va aller vite.

      Si a =0, ça donne quoi ? La 1ère équation donne d=f=1 ; la 4ème équation donne c=e=1, la dernière équation donne b=0. Et on voit que ce sextuplet (0,0,1,1,1,1) est solution.

      Y-a-t-il d'autres soutions ? Si a=1, alors la 1ère équation nous dit :  (f=1,d=0) ou bien (f=0,d=1)

      La 4ème équation nous dit (c=1,e=0) ou bien (c=0, e=1)

      Si b=0, on n'aura pas de solution, mais si b=1, alors on trouve vite 2 nouvelles solutions (1,1,1,1,0,0) et (1,1,0,0,1,1).

      Et ce sont bien évidemment les 3 seules solutions, puisqu'on a exploré COMPLETEMENT les cas a=0 et a=1

      • Partager sur Facebook
      • Partager sur Twitter
        15 juin 2019 à 23:23:26

        Merci beaucoup tbc92😊,

        Mais il y avait aussi une information importante en 2e: Je ne cherchais pas spécifiquement la solution de ce système, mais j'aurais aimé savoir s'il y avait un moyen de le résoudre sans passer par la case "bourrin" ^^

        Comme je l'ai écrit, ce n'est qu'un exemple et j'utiliserai normalement beaucoup plus de variables, et pour peu que je passe à 100 variables, 2^100  je n'y arriverais jamais en recherche exhaustive....

        Est-ce qu'il n'existe pas un moyen élégant, à l'image du pivot de Gauss pour savoir s'il y a une solution ? (ou encore mieux: les trouver )

        J'aimerais avoir un algo qui résoud ça en temps polynomiale...

        • Partager sur Facebook
        • Partager sur Twitter
          16 juin 2019 à 0:51:07

          Avec 100 variables, en théorie, tu as 2^100 cas à explorer. Mais dans la pratique, tu en as beaucoup moins. Il y a plein de branches qu'on peut couper très vite.  Dans l'exemple précédent, si on se limite aux variables (a,c,e), on a en théorie 8 combinaisons, et avec l'équation a+c+e=2, on tombe à 3 combinaisons. Chaque équation est l'équation d'un 'hyperplan',elle réduit énormément la taille de l'arbre.

          Si par exemple j'ai 100 variables , si j'ai une équation qui me dit que la somme des 50 premières variables donne 25, alors, on avait 2^50 combinaisons possibles pour ces 50 variables, et on tombe à 50!/25!25!. On a divisé par 10 le nombre de combinaisons, avec une seule équation.

          C'est un cas peu favorable. Si on a une équation qui dit que la somme de 50 variables donne 10, avec cette seule équation, on divise la taille de l'arbre par 100000.

          Je ne suis pas du tout un spécialiste des théories, mais ici, si tu dois rechercher dans les outils 'modernes', je chercherais du côté 'Parcours d'arbre binaire'.

          • Partager sur Facebook
          • Partager sur Twitter
            16 juin 2019 à 16:35:47

            Hello,
            les techniques arborescentes de recherche de solutions sont regroupées sous le nom Programmation par contraintes.
            • Partager sur Facebook
            • Partager sur Twitter
              18 juin 2019 à 20:29:42

              Merci à vous tbc92 et cvanare 😊

              • Partager sur Facebook
              • Partager sur Twitter

              Résoudre un système d'(in+)équation "binaire"

              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
              • Editeur
              • Markdown