Résolution Polynomiale : le problème des 400 étudiants.
 

                                    À propos
             Cet ouvrage nécessite avoir lu le référenciel de SCI pour le comprendre.
 

Ce manuscrit résout le 3e problème de Smale (P=NP). Un logiciel accompagne ce tutoriel ( P_NP.gmk ). Cette open-source s'ouvre avec Game Maker 8.0 pro, et le «gml 8» est le langage utilisé.

​

                        Problème : Les 400 étudiants.
         Il y a 400 étudiants et 100 Places. Lorsqu'un étudiant prend une place, une ou plusieurs incompatibilités peuvent avoir lieu, empêchent d'autres étudiants d'avoir des places.

                             Question
        Est-ce possible de résoudre le problème de façon polynomiale, tout en ayant une solution vérifiée en temps réel ?

                    Réponse Théorique
   Oui, il est possible grâce à une formule de SCI (Suite de Chaîne Itérée).

   Voici un exemple avec 8 étudiants et 4 places :

           Tableau P1
                            | Étudiants
                                  1       2       3       4       5       6       7       8
       Étudiants  1 |    [3]      X        X      X
                         2 |     X      [3]               X                                  X
                         3 |                      [4]                       X       X
                         4 |     X                       [5]     X        X        
                         5 |                       X      X     [3]       X
                         6 |                                                 [4]     X
                         7 |                                                  X     [2]
                         8 |             X                X                                  [2]

Les X représentent les incompatibilités. Les nombres en diagonal à la position P1[i,i] représente le nombre total d'incompatibilité que possède un étudiant.
           Tableau R
                               | Incompatibilité
           Étudiant    1 |    2,3,4
                            2 |    1,4,8
                            3 |    1,5,6,7
                            4 |    1,2,5,6,8
                            5 |    3,4,6
                            6 |    3,4,5,7
                            7 |    3,6
                            8 |    2,4

Pour chaque incompatibilité d'un étudiant, il faut noter la valeur totale des incompatibilités.

           Tableau R L1
                               | Valeur du nombre total d'incompatibilité
           Étudiant    1 |    12
                            2 |    8
                            3 |    12
                            4 |    15

                            5 |    13
                            6 |    14
                            7 |    7
                            8 |    8

Ensuite, une formule doit être respectée. Pour l'étudiant « i », Si l'étudiant n'a pas été rejeté ou déjà placé, il faut calculer la somme d'incompatibilité au carré que possède l'étudiant « i », moins la somme des incompatibilités que possède chaque incompatibilité de l'étudiant i. Puis, choisir de placer l'étudiant ayant la valeur la plus basse et rejeter les autres étudiants.
 

Dans cet exemple, l'étudiant #1 est incompatible avec 2,3,4. Pour 3 incompatibilités de l'étudiant #1, ses incompatibilités comptent au total de 12. Le #2 arrive à un total de 8, le #3 à 12 et le #4 à un total de 15.

   L'étudiant #1 a une valeur de -3 (3² -12)
       Le #2 a une valeur de 1 (3² -8)
       Le #3 a une valeur de 4 (4² -12)
       Et le #4 a une valeur de 10 (5² -15)

L'étudiant #1 à la plus petite valeur, il est donc choisi et les 3 autres étudiants rejetés. Puis nous les retirons des calculs.

           Tableau R
                                | Incompatibilité
           Étudiant    1 |    2,3,4               [Choisi]
                             2 |    1,4,8               [Rejeté]
                             3 |    1,5,6,7            [Rejeté]
                             4 |    1,2,5,6,8         [Rejeté]
                             5 |    6
                             6 |    5,7
                             7 |    6
                             8 |    

           Tableau R L1
                               | Valeur du nombre total d'incompatibilité
           Étudiant   5 |    2
                            6 |    1
                            7 |    2
                            8 |    0

Poursuivons avec l'étudiant #5. Cet étudiant est incompatible avec l'étudiant #6. Nous répétons la même formule.

       L'étudiant #5 a une valeur de -1 (1²-2)
       L'étudiant #6 a une valeur de 3 (2²-1)

L'étudiant #5 est choisi, et le #6 Rejeté.

           Tableau R
                                | Incompatibilité
           Étudiant    1 |    2,3,4               [Choisi]
                             2 |    1,4,8               [Rejeté]
                             3 |    1,5,6,7            [Rejeté]
                             4 |    1,2,5,6,8         [Rejeté]
                             5 |    6                     [Choisi]
                             6 |    5,7                  [Rejeté]
                             7 |    
                             8 |    

           Tableau R L1
                                | Valeur du nombre total d'incompatibilité
           Étudiant    7 |    0
                             8 |    0

Pour terminer, comme l'étudiant #7 et #8 ont une valeur d'incompatibilité de 0, ils sont choisis tout les 2. Pour conclure l'exemple, nous avons 4 places de prises : #1, #5, #7, #8.
 

Cette méthode peut être appliquée mathématiquement. Voici comment exploiter informatiquement la résolution polynomiale.

                Réponse Mathématique
 

#SO()==        // Système d'Origine.
/*        1 : Identifier les sujets du problème :
           400 Étudiants    [P]
               l__ Des incompatibilités sont possibles entre les étudiants. [R]
                   l__ 100 Places disponibles pour les étudiants    [M]

       2 : Identifier Les Variables Primitives.
           Il y a 400 étudiants. Ces étudiants sont Parent des incompatibilités. C'est donc une Variable Primitive Simple qui représentera les étudiants «P1». Sa limitation étant la plus grande sera représenté par la variable de Limitation «L1».

           Il y a la possibilité d'une ou plusieurs incompatibilités entre les étudiants. L'existence des incompatibilités est dépendante des étudiants. C’est donc une variable de Résolution «R1».

           Il y a 100 Places. Pour la résolution de ce problème, il n'est pas nécessaire d'ajouter cette variable. Au lieu de noter tout dans cette variable, nous pourrions très bien par exemple déclarer dans la variable de résolution la valeur L1³ pour tous les étudiants choisis. Mais dans cet exemple nous allons classer les étudiants dans une Variable Primitive de Mémoire «M1».

       3 : Connaître les dimensions des variables :
           P1[n,n] :
               - possède une origine de limitation supérieur à 1.
               - possède une variable de résolution (les incompatibilités).
           R1[n,n] :
               - Son existence dépend toujours d'au moins une variable Pn.
           M1.n :
               - possède une origine de limitation supérieur à 1.
               
*/
   OL( 400 , 100 )        // Variable : L1, L2
   OM( 6 )                    // Variable : i, j, k, l, m et n

   OP( L102 ¦ L102 ¦ L201 ) ;    // Variable : P1[n,n] , R1[n,n] , M1[n]
   PN() ;

#PN()==            // Proposition : nous plaçons les valeurs sur le tableau P1.
   PR( L1 , i )
   {    PR( L1 , j )
       {    RA( i = j )
           {    P1[ i , j ] = L1
           } !
           {    RA( ( ir(1,5) ) = 1 )
               {    P1[ i , j ] = 1
               } !
               {    P1[ i , j ] = 0
           }
       }
   }
   PR( L2 , i )
   {    M1.i = 0
   }
   m = 1
   n = 1 ;
   SLP() ;
#SLP()==        // Suite Logique Parent : Nous plaçons les étudiants.
   PR( (L1-1) , i )    // Pour chaque étudiant :
   {    RA( R1[i,L1] < L1² )          // Si les incompatibilités ne sont pas calculés :
       {    m = i ;
           RA( P1[i,i] >= L1 )    // Si P1[i,i] n'est pas mesuré :
           {    SL.1( i ) ;                   // Mesure la valeur de l'étudiant.
           }         // Si l'étudiant « i » a au moins une incompatibilité :
           RA( P1[i,i] > 0 )    
           {        // Calcul les incompatibilités ; calcul la grille « R1 ».
               SL.2( i ) ;
           }
           AF() ;        // Place l'étudiant choisi.
       }    // Si toutes les places sont prises, ou s'il n'y a pas assez d'étudiant :
       RA( L2 < n | (L1-i) < (L2-n) )
       {    break ;
       }
   }
   RA( (L1-i) < (L2-n) )        // S'il manque des étudiants pour remplir les places :
   {    msg("Il n'y a pas de patern valide.")
       exit ;
   }
   RA( L2 < n )            // Si toutes les places sont prises :
   {    msg("Toutes les places ont un étudiant.")
       exit ;
   }
   RA( R1[L1,L1] = (L1² + 1) )    // Si le dernier étudiant n'a jamais été calculé :
   {    m = L1 ;                // Choisi le dernier étudiant.
       AF() ;                // Place le dernier étudiant.
       msg("Toute les places ont un étudiant.") ;
   } !                // Sinon, il manque un étudiant.
   {    msg("Il n'y a pas de patern valide.") ;
   }
#SL.1()==        // Suite Logique Enfant : Mesure la valeur de l'étudiant.
   P1[a1,a1] -= L1 ;             // Déclare que les incompatibilités de l'étudiant sont mesurées.
   PR( (L1-i) , l )        // Pour chaque étudiant au-dessus de « i » :
   {    RA( (i+l) != a1 )        // Excluant soi-même :
       {          // Si l'incompatibilité possible n'est pas déclaré comme étant mesurée :
           RA( P1[ (i+l),(i+l) ] >= L1 )
           {        // S'il y a une incompatibilité :
               RA( P1[ a1,(i+l) | P1[ (i+l),a1 ] = 1 )         
               {    // Ajoute +1 à la mesure des d'incompatibilité.
                   P1[a1,a1] ++
                   P1[ (i+l),(i+l) ] ++ ;
                         // Place l'incompatibilité dans la liste itéré R1[n,n]
                   R1[ a1,P1[a1,a1] ] = (i+l)
                   R1[ (i+l) , ( P1[ (i+l),(i+l) ] - L1 ) ] = a1 ;
               }
           }
       }
   }
#SL.2()==        // Suite Logique Enfant : Calcul les incompatibilités.
   R1[ i,L1 ] -= ( L1² + 1 ) ;        // Déclare que l'étudiant est en train d'être calculé.
   PR( P1[i,i] , j )            // Pour Chaque incompatibilité :
   {              // Si l'incompatibilité n'est pas déclaré comme étant calculé :
       RA( R1[ R1[i,j],L1 ] < L1² )
       {        // Si l'incompatibilité n'est pas déclaré comme étant mesuré :
           RA( P1[ R1[i,j] , R1[i,j] ] >= L1 )
           {    SL.1( R1[i,j] ) ;        // Mesure l'incompatibilité.
           }
       // Chaque étudiant ajoute la mesure de l'autre dans le résultat de la grille R1.
           R1[i,L1] += P1[ R1[i,j] , R1[i,j] ]
           R1[ R1[i,j],L1 ] += P1[i,i] ;
           SL.3( R1[i,j] ) ;    // Calcule les incompatibilités de l'incompatibilité.
       }
   }
   RF.1() ;        // «m» choisi l'étudiant le plus rentable.
#SL.3()==        // Suite Logique Enfant :  Calculer la valeur de l'étudiant incompatible.
   // Déclare le résultat de la grille « R1 » de l'incompatibilité comme étant calculé.
   R1[ a1,L1 ] += L1² ;
   PR( P1[a1,a1] , l )    // Pour chaque incompatibilité que la grille possède :
   {        // Si le résultat de la grille R1 de l'incompatibilité n'est pas calculé :
       RA( R1[ R1[a1,l],L1 ] < L1² )
       {        // Si la mesure de l'incompatibilité n'a pas été fait :
           RA( P1[ R1[a1,l] , R1[a1,l] ] >= L1 )
           {    SL.1( R1[a1,l] ) ;        // Mesure l'incompatibilité.
           }        // Les étudiants s'échangent leurs mesures.
           R1[a1,L1] += P1[ R1[a1,l] , R1[a1,l] ]
           R1[ R1[a1,l],L1 ] += P1[a1,a1] ;
       }
   }
#SL.4()==    // Suite Logique Enfant : Déclare comme étant calculé l'étudiant Arg1.
   PR( P1[a1,a1] , k )    // Pour chaque incompatibilité de l'étudiant :
   {    RA( R1[ R1[a1,k ],L1 ] < L1² )    // Excluent les incompatibilités déjà calculé :
       {        // Retire l'étudiant du calcule.
           RF.2(a1) ;
       }
   }
   R1[a1,L1] = L1² ;        // Déclare que l'étudiant est calculé.
#RF.1()==
   PR( P1[i,i] , j )        // Pour Chaque incompatibilité :
   {    RA( (P1[m,m]² - ( R1[m,L1]-L1² )) > (P1[ R1[i,j],R1[i,j] ]² - (R1[ R1[i,j],L1 ] - L1²)) )
       {    SL.4( m ) ;    // Déclare l'étudiant pré-choisi comme étant calculé.
           m = R1[i,j] ;    // Et choisi la nouvelle incompatibilité.
       } !        // Sinon :
       {    SL.4( R1[i,j] ) ;    // Déclare l'incompatibilité comme étant calculé.
       }
   }
#RF.2()==
       // Retire l'étudiant du calcule de la grille R1 de l'incompatibilité.
   R1[ R1[a1,k],L1 ] -= P1[a1,a1] ;
       // Pour chaque incompatibilité de l'incompatibilité :
   PR( P1[ R1[a1,k],R1[a1,k] ] , l )
   {        // Si l'une des incompatibilités est l'étudiant :
       RA( R1[ R1[a1,k],l ] = a1 )
       {        // Le dernier étudiant de la liste prend sa place.
           R1[ R1[a1,k],l ] = R1[ R1[a1,k] , P1[ R1[a1,k],R1[a1,k] ] ] ;
               // Et le dernier étudiant est retiré de la liste.
           P1[ R1[a1,k],R1[a1,k] ] --
           break ;
       }
   }
#AF()==        // Application Finale : Place les étudiants.
   M1.n = m ;        // L'étudiant choisi gagne la place n .
   SL.4(m)            // Déclare que l'étudiant est calculé.
   n ++ ;            // Sélectionne la prochaine place à remplir.

​

NOTE : L'exemple reproductible est fait avec Game Maker Pro 8.0 .