Précédent Remonter Suivant

Chapitre 9  Recherche exhaustive

Ce que l'ordinateur sait faire de mieux, c'est traiter très rapidement une quantité gigantesque de données. Cela dit, il y a des limites à tout, et le but de ce chapitre est d'expliquer sur quelques cas ce qu'il est raisonnable d'attendre comme temps de résolution d'un problème. Cela nous permettra d'insister sur le coût des algorithmes et sur la façon de les modéliser.

9.1  Rechercher dans du texte

Commençons par un problème pour lequel de bonnes solutions existent.

Rechercher une phrase dans un texte est une tâche que l'on demande à n'importe quel programme de traitement de texte, à un navigateur, un moteur de recherche, etc. C'est également une part importante du travail accompli régulièrement en bio-informatique.

Vues les quantités de données gigantesques que l'on doit parcourir, il est crucial de faire cela le plus rapidement possible. Le but de cette section est de présenter quelques algorithmes qui accomplissent ce travail.

Pour modéliser le problème, nous supposons que nous travaillons sur un texte T (un tableau de caractères char[], plutôt qu'un objet de type String pour alléger un peu les programmes) de longueur n dans lequel nous recherchons un motif M (un autre tableau de caractères) de longueur m que nous supposerons plus petit que n. Nous appelerons occurence en position i≥ 0 la propriété que T[i]=M[0], ..., T[i+m-1]=M[m-1].

Recherche naïve

C'est l'idée la plus naturelle: on essaie toutes les positions possibles du motif en dessous du texte. Comment tester qu'il existe une occurrence en position i ? Il suffit d'utiliser un indice j qui va servir à comparer M[j] à T[i+j] de proche en proche:
static boolean occurrence(char[] T, char[] M, int i){
    for(int j = 0; j < M.length; j++)
        if(T[i+j] != M[j]) return false;
    return true;
}

Nous utilisons cette primitive dans la fonction suivante, qui teste toutes les occurences possibles:
static void naif(char[] T, char[] M){
    System.out.print("Occurrences en position :");
    for(int i = 0; i < T.length-M.length; i++)
        if(occurrence(T, M, i))
            System.out.print(" "+i+",");
    System.out.println("");
}
Si T contient les caractères de la chaîne "il fait beau aujourd'hui" et M ceux de "au", le programme affichera
Occurrences en position: 10, 13,
Le nombre de comparaisons de caractères effectuées est au plus (n-m) m, puisque chacun des n-m tests en demande m. Si m est négligeable devant n, on obtient un nombre de l'ordre de n m. Le but de la section qui suit est de donner un algorithme faisant moins de comparaisons.

Algorithme linéaire de Karp-Rabin

Supposons que S soit une fonction (non nécessairement injective) qui donne une valeur numérique à une chaîne de caractères quelconque, que nous appelerons signature: nous en donnons deux exemples ci-dessous. Si deux chaînes de caractères C1 et C2 sont identiques, alors S(C1) = S(C2). Réciproquement, si S(C1) ≢ S(C2), alors C1 ne peut être égal à C2.

Le principe de l'algorithme de Karp-Rabin utilise cette idée de la façon suivante: on remplace le test d'occurrence T[i..i+m-1] = M[0..m-1] par S(T[i..i+m-1]) = S(M[0..m-1]). Le membre de droite de ce test est constant, on le précalcule donc et il ne reste plus qu'à effectuer n-m calculs de S et comparer la valeur S(T[i..i+m-1]) à cette constante. En cas d'égalité, on soupçonne une occurrence et on la vérifie à l'aide de la fonction occurrence présentée ci-dessus. Le nombre de calculs à effectuer est simplement 1+n-m évaluations de S.

Voici la fonction qui implante cette idée. Nous préciserons la fonction de signature S plus loin (codée ici sous la forme d'une fonction signature):
static void KR(char[] T, char[] M){
    int n, m;
    long hT, hM;

    n = T.length;
    m = M.length;
    System.out.print("Occurrences en position :");
    hM = signature(M, m, 0);
    for(int i = 0; i < n-m; i++){
        hT = signature(T, m, i);
        if(hT == hM){
            if(occurrence(T, M, i))
                System.out.print(" "+i+",");
            else
                System.out.print(" ["+i+"],");
        }
    }
    System.out.println("");
}

La fonction de signature est critique. Il est difficile de fabriquer une fonction qui soit à la fois injective et rapide à calculer. On se contente d'approximations. Soit X un texte de longueur m. En Java ou d'autres langages proches, il est généralement facile de convertir un caractère en nombre. Le codage unicode représente un caractère sur 16 bits et le passage du caractère c à l'entier est simplement (int)c. La première fonction à laquelle on peut penser est celle qui se contente de faire la somme des caractères représentés par des entiers:
    static long signature(char[] X, int m, int i){
        long s = 0;

        for(int j = i; j < i+m; j++)
            s += (long)X[j];
        return s;
    }

Avec cette fonction, le programme affichera:
Occurrences en position: 10, 13, [18],
où on a indiqué les fausses occurrences par des crochets. On verra plus loin comment diminuer ce nombre.

Pour accélérer le calcul de la signature, on remarque que l'on peut faire cela de manière incrémentale. Plus précisément:
S(X[1..m]) = S(X[0..m-1])-X[0]+X[m],
ce qui remplace m additions par 1 addition et 1 soustraction à chaque étape (on a confondu X[i] et sa valeur en tant que caractère).

Une fonction de signature qui présente moins de collisions s'obtient à partir de ce qu'on appelle une fonction de hachage, dont la théorie ne sera pas présentée ici. On prend p un nombre premier et B un entier. La signature est alors:
S(X[0..m-1]) = (X[0]Bm-1+⋯+X[m-1]B0) modp.
On montre que la probabilité de collisions est alors 1/p. Typiquement, B=216, p = 231-1 = 2147483647.

L'intérêt de cette fonction est qu'elle permet un calcul incrémental, puisque:
S(X[i+1..i+m]) = B S(X[i..i+m-1])-X[i] Bm + X[i+m],
qui s'évalue d'autant plus rapidement que l'on a précalculé Bmmodp.

Le nombre de calculs effectués est O(n+m), ce qui représente une amélioration notable par rapport à la recherche naïve.

Les fonctions correspondantes sont:
    static long B = ((long)1) << 16, p = 2147483647;

    // calcul de S(X[i..i+m-1])
    static long signature2(char[] X, int i, int m){
        long s = 0;

        for(int j = i; j < i+m; j++)
            s = (s * B + (int)X[j]) % p;
        return s;
    }

    // S(X[i+1..i+m]) = B S(X[i..i+m-1])-X[i] B^m + X[i+m]
    static long signatureIncr(char[] X, int m, int i,
                              long s, long Bm){
        long ss;

        ss = ((int)X[i+m]) - ((((int)X[i]) * Bm)) % p;
        if(ss < 0) ss += p;
        ss = (ss + B * s) % p;
        return ss;
    }

    static void KR2(char[] T, char[] M){
        int n, m;
        long Bm, hT, hM;

        n = T.length;
        m = M.length;
        System.out.print("Occurrences en position :");
        hM = signature2(M, 0, m);
        // calcul de Bm = B^m mod p
        Bm = B;
        for(int i = 2; i <= m; i++)
            Bm = (Bm * B) % p;
        hT = signature2(T, 0, m);
        for(int i = 0; i < n-m; i++){
            if(i > 0)
                hT = signatureIncr(T, m, i-1, hT, Bm);
            if(hT == hM){
                if(occurrence(T, M, i))
                    System.out.print(" "+i+",");
                else
                    System.out.print(" ["+i+"],");
            }
        }
        System.out.println("");
    }

Cette fois, le programme ne produit plus de collisions:
Occurrences en position : 10, 13,

Remarques complémentaires

Des algorithmes plus rapides existent, comme par exemple ceux de Knuth-Morris-Pratt ou Boyer-Moore. Il est possible également de chercher des chaînes proches du motif donné, par exemple en cherchant à minimiser le nombre de lettres différentes entre les deux chaînes.

La recherche de chaînes est tellement importante qu'Unix possède une commande grep qui permet de rechercher un motif dans un fichier. À titre d'exemple:
unix% grep int Essai.java
affiche les lignes du fichier Essai.java qui contiennent le motif int. Pour afficher les lignes ne contenant pas int, on utilise:
unix% grep -v int Essai.java
On peut faire des recherches plus compliquées, comme par exemple rechercher les lignes contenant un 0 ou un 1:
unix% grep [01] Essai.java
Le dernier exemple est:
unix% grep "int .*[0-9]" Essai.java
qui est un cas d'expression régulière. Elles peuvent être décrites en termes d'automates, qui sont étudiés en cours d'Informatique Fondamentale. Pour plus d'informations sur la commande grep, tapez man grep.

9.2  Le problème du sac-à-dos

Considérons le problème suivant, appelé problème du sac-à-dos: on cherche à remplir un sac-à-dos avec un certain nombre d'objets de façon à le remplir exactement. Comment fait-on ?

On peut modéliser ce problème de la façon suivante: on se donne n entiers strictement positifs ai et un entier S. Existe-t-il des nombres xi∈ {0, 1} tels que
S = x0 a0 + x1 a1 + ⋯ + xn-1 an-1?
Si xi vaut 1, c'est que l'on doit prendre l'objet ai, et on ne le prend pas si xi=0.

Un algorithme de recherche des solutions doit être capable d'énumérer rapidement tous les n uplets de valeurs des xi. Nous allons donner quelques algorithmes qui pourront être facilement modifiés pour chercher des solutions à d'autres problèmes numériques: équations du type f(x0, x1, …, xn-1) = 0 avec f quelconque, ou encore maxf(x0, x1, …, xn-1) sur un nombre fini de xi.

9.2.1  Premières solutions

Si n est petit et fixé, on peut s'en tirer en utilisant des boucles for imbriquées qui permettent d'énumérer les valeurs de x0, x1, x2. Voici ce qu'on peut écrire:

    // Solution brutale
    static void sacADos3(int[] a, int S){
        int N;

        for(int x0 = 0; x0 < 2; x0++)
            for(int x1 = 0; x1 < 2; x1++)
                for(int x2 = 0; x2 < 2; x2++){
                    N = x0 * a[0] + x1 * a[1] + x2 * a[2];
                    if(N == S)
                        System.out.println(""+x0+x1+x2);
                }
    }
Cette version est gourmande en calculs, puisque N est calculé dans la dernière boucle, alors que la quantité x0 a0 + x1 a1 ne dépend pas de x2. On écrit plutôt:
    static void sacADos3b(int[] a, int S){
        int N0, N1, N2;

        for(int x0 = 0; x0 < 2; x0++){
            N0 = x0 * a[0];
            for(int x1 = 0; x1 < 2; x1++){
                N1 = N0 + x1 * a[1];
                for(int x2 = 0; x2 < 2; x2++){
                    N2 = N1 + x2 * a[2];
                    if(N2 == S)
                        System.out.println(""+x0+x1+x2);
                }
            }
        }
    }
On peut encore aller plus loin, en ne faisant aucune multiplication, et remarquant que deux valeurs de Ni diffèrent de ai. Cela donne:
    static void sacADos3c(int[] a, int S){
        for(int x0 = 0, N0 = 0; x0 < 2; x0++, N0 += a[0])
            for(int x1 = 0, N1 = N0; x1 < 2; x1++, N1 += a[1])
                for(int x2=0, N2=N1; x2 < 2; x2++, N2+=a[2])
                    if(N2 == S)
                        System.out.println(""+x0+x1+x2);
    }
Arrivé ici, on ne peut guère faire mieux. Le problème majeur qui reste est que le programme n'est en aucun cas évolutif. Il ne traite que le cas de n=3. On peut bien sûr le modifier pour traiter des cas particuliers fixes, mais on doit connaître n à l'avance, au moment de la compilation du programme.

9.2.2  Deuxième approche

Les xi doivent prendre toutes les valeurs de l'ensemble {0, 1}, soit 2n. Toute solution peut s'écrire comme une suite de bits x0 x1xn-1 et donc s'interpréter comme un entier unique de l'intervalle In = [0, 2n[, à savoir
x0 20 + x1 21 + ⋯ xn-1 2n-1.
Parcourir l'ensemble des xi possibles ou bien cet intervalle est donc la même chose.

On connait un moyen simple de passer en revue tous les éléments de In, c'est l'addition. Il nous suffit ainsi de programmer l'addition binaire sur un entier représenté comme un tableau de bits pour faire l'énumération. On additionne 1 à un registre, en propageant à la main la retenue. Pour simplifier la lecture des fonctions qui suivent, on a introduit une fonction qui affiche les solutions:
    // affichage de i sous forme de sommes de bits
    static afficher(int i, int[] x){
        System.out.print("i="+i+"=");
        for(int j = 0; j < n; j++)
            System.out.print(""+x[j]);
        System.out.println("");
    }

    static void parcourta(int n){
        int retenue;
        int[] x = new int[n];

        for(int i = 0; i < (1 << n); i++){
            afficher(i, x);
            // simulation de l'addition
            retenue = 1;
            for(int j = 0; j < n; j++){
                x[j] += retenue;
                if(x[j] == 2){
                    x[j] = 0;
                    retenue = 1;
                }
                else break; // on a fini
            }
        }
    }
(L'instruction 1<<n calcule 2n.) On peut faire un tout petit peu plus concis en gérant virtuellement la retenue: si on doit ajouter 1 à xj=0, la nouvelle valeur de xj est 1, il n'y a pas de retenue à propager, on s'arrête et on sort de la boucle; si on doit ajouter 1 à xj=1, sa valeur doit passer à 0 et engendrer une nouvelle retenue de 1 qu'elle doit passer à sa voisine. On écrit ainsi:
    static void parcourtb(int n){
        int[] x = new int[n];

        for(int i = 0; i < (1 << n); i++){
            afficher(i, x);
            // simulation de l'addition
            for(int j = 0; j < n; j++){
                if(x[j] == 1)
                    x[j] = 0;
                else{
                    x[j] = 1;
                    break; // on a fini
                }
            }
        }
    }
La boucle centrale étant écrite, on peut revenir à notre problème initial, et au programme de la figure 9.1.

    // a[0..n[ : existe-t-il x[] tel que 
    // somme(a[i]*x[i], i=0..n-1) = S ?
    static void sacADosn(int[] a, int S){
        int n = a.length, N;
        int[] x = new int[n];

        for(int i = 0; i < (1 << n); i++){
            // reconstruction de N = somme x[i]*a[i]
            N = 0;
            for(int j = 0; j < n; j++)
                if(x[j] == 1)
                    N += a[j];
            if(N == S){
                System.out.print("S="+S+"=");
                for(int j = 0; j < n; j++)
                    if(x[j] == 1)
                        System.out.print("+"+a[j]);
                System.out.println("");
            }
            // simulation de l'addition
            for(int j = 0; j < n; j++){
                if(x[j] == 1)
                    x[j] = 0;
                else{
                    x[j] = 1;
                    break; // on a fini
                }
            }
        }
    }

Figure 9.1 : Version finale.


Combien d'additions fait-on dans cette fonction ? Pour chaque valeur de i, on fait au plus n additions d'entiers (en moyenne, on en fait d'ailleurs n/2). Le corps de la boucle est effectué 2n fois, le nombre d'additions est O(n 2n).

9.2.3  Code de Gray*

Théorie et implantations

Le code de Gray permet d'énumérer tous les entiers de In = [0, 2n-1] de telle sorte qu'on passe d'un entier à l'autre en changeant la valeur d'un seul bit. Si k est un entier de cet intervalle, on l'écrit k = k0 + k1 2 + ⋯ + kn-1 2n-1 et on le note [kn-1, kn-2, …, k0].

On va fabriquer une suite Gn = (gn, i)0≤ i<2n dont l'ensemble des valeurs est [0, 2n-1], mais dans un ordre tel qu'on passe de gn, i à gn, i+1 en changeant un seul chiffre de l'écriture de gn, i en base 2.

Commençons par rappeler les valeurs de la fonction ou exclusif (appelé XOR en anglais) et noté ⊕. La table de vérité de cette fonction logique est
  0 1
0 0 1
1 1 0
En Java, la fonction ⊕ s'obtient par ^ et opère sur des mots: si m est de type int, m représente un entier signé de 32 bits et m ^ n effectue l'opération sur tous les bits de m et n à la fois. Autrement dit, si les écritures de m et n en binaire sont:
m = m31 231 + ⋯ + m0 = [m31, m30, …, m0],
n = n31 231 + ⋯ + n0 = [n31, n30, …, n0]
avec mi, ni dans {0, 1}, on a
mn =
31
i=0
(mini) 2i.

On définit maintenant gn: [0, 2n-1] → [0, 2n-1] par gn(0) = 0 et si i > 0, gn(i) = gn(i-1) ⊕ 2b(i)b(i) est le plus grand entier j tel que 2ji. Cet entier existe et b(i) < n pour tout i < 2n. Donnons les valeurs des premières fonctions:
g1(0) = [0], g1(1) = [1],
g2(0) = [00], g2(1) = [01], g2(2)=g2([10])=g2(1)⊕ 21=[01] ⊕ [10] = [11],
g2(3) = g2([11]) = g2(2) ⊕ 20 = [11] ⊕ [01] = [10].
Écrivons les valeurs de g3 sous forme d'un tableau qui souligne la symétrie de celles-ci:
i g(i) i g(i)
0 000=0 7 100=4
1 001=1 6 101=5
2 011=3 5 111=7
3 010=2 4 110=6
Cela nous conduit naturellement à prouver que la fonction gn possède un comportement ``miroir'':
Proposition 6   Si 2n-1i < 2n, alors gn(i) = 2n-1 + gn(2n-1-i).

Démonstration: Notons que 2n-1-2n < 2n-1-i ≤ 2n-1-2n-1, soit 0 ≤ 2n-1-i ≤ 2n-1-1 < 2n-1.

On a
gn(2n-1) = gn(2n-1-1) ⊕ 2n-1 = 2n-1 + gn(2n-1-1) = 2n-1 + gn(2n-1-2n-1).
Supposons la propriété vraie pour i=2n-1+r > 2n-1. On écrit:
gn(i+1) = gn(i) ⊕ 2b(r+1)
  = (2n-1+gn(2n-1-i)) ⊕ 2b(r+1)
  = 2n-1 + (gn(2n-1-i) ⊕ 2b(r+1)).
On conclut en remarquant que:
gn(2n-1-i) = gn(2n-1-i-1) ⊕ 2b(2n-1-i)
et b(2n-i-1) = b(i+1) = b(r+1).

On en déduit par exemple que gn(2n-1) = 2n-1 + gn(0) = 2n-1.
Proposition 7   Si n≥ 1, la fonction gn définit une bijection de [0, 2n-1] dans lui-même.

Démonstration: nous allons raisonner par récurrence sur n. Nous venons de voir que g1 et g2 satisfont la propriété. Supposons-la donc vraie au rang n≥ 2 et regardons ce qu'il se passe au rang n+1. Commençons par remarquer que si i < 2n, gn+1 coïncide avec gn car b(i) < n.

Si i = 2n, on a gn+1(i) = gn(2n-1) ⊕ 2n, ce qui a pour effet de mettre un 1 en bit n+1. Si 2n < i < 2n+1, on a toujours b(i) < n et donc gn+1(i) conserve le n+1-ième bit à 1. En utilisant la propriété de miroir du lemme précédent, on voit que gn+1 est également une bijection de [2n, 2n+1-1] dans lui-même.



Quel est l'intérêt de la fonction gn pour notre problème ? Des propriétés précédentes, on déduit que gn permet de parcourir l'intervalle [0, 2n-1] en passant d'une valeur d'un entier à l'autre en changeant seulement un bit dans son écriture en base 2. On trouvera à la figure 9.2 une première fonction Java qui réalise le parcours.

  static void gray(int n){
    int gi = 0;

    affichergi(0, n);
    for(int i = 1; i < (1 << n); i++){
      // on écrit i = 2^j*k, 0 <= j < n, k impair
      int k = i, j;

      for(j = 0; j < n; j++){
        if((k % 2) == 1)
          // k est impair, on s'arrête
          break;
        k /= 2;
      }
      gi ^= (1 << j);
      affichergi(gi, n);
    }
  }

  static void afficherAux(int gi, int j, int n){
    if(j >= 0){
      afficherAux(gi >> 1, j-1, n);
      System.out.print((gi & 1));
    }
  }

  static void affichergi(int gi, int n){
    afficherAux(gi, n-1, n);
    System.out.println("="+gi);
  }

Figure 9.2 : Affichage du code de Gray.


On peut faire un peu mieux, en remplaçant les opérations de modulo par des opérations logiques, voir la figure 9.3.

  static void gray2(int n){
    int gi = 0;

    affichergi(0, n);
    for(int i = 1; i < (1 << n); i++){
      // on écrit i = 2^j*k, 0 <= j < n, k impair
      int k = i, j;

      for(j = 0; j < n; j++){
        if((k & 1) == 1)
          // k est impair, on s'arrête
          break;
        k >>= 1;
      }
      gi ^= (1 << j);
      affichergi(gi, n);
    }
  }

Figure 9.3 : Affichage du code de Gray (2è version).


Revenons au sac-à-dos. On commence par calculer la valeur de ∑ xi ai pour le n-uplet [0, 0, …, 0]. Puis on parcourt l'ensemble des xi à l'aide du code de Gray. Si à l'étape i, on a calculé
Ni = xn-1 an-1 + ⋯ + x0 a0,
avec g(i) = [xn-1, …, x0], on passe à l'étape i+1 en changeant un bit, mettons le j-ème, ce qui fait que:
Ni+1 = Ni + aj
si gi+1 = gi + 2j, et
Ni+1 = Ni - aj
si gi+1 = gi - 2j. On différencie les deux valeurs en testant la présence du j-ème bit après l'opération sur gi:

  static void sacADosGray(int[] a, int S){
    int n = a.length, gi = 0, N = 0, deuxj;

    if(N == S)
      afficherSolution(a, S, 0);
    for(int i = 1; i < (1 << n); i++){
      // on écrit i = 2^j*k, 0 <= j < n, k impair
      int k = i, j;

      for(j = 0; j < n; j++){
        if((k & 1) == 1)
          // k est impair, on s'arrête
          break;
        k >>= 1;
      }
      deuxj = 1 << j;
      gi ^= deuxj;
      if((gi & deuxj) != 0)
        N += a[j];
      else
        N -= a[j];
      if(N == S)
        afficherSolution(a, S, gi);
    }
  }

  static void afficherSolution(int[] a, int S, int gi){
    System.out.print("S="+S+"=");
    for(int i = 0; i < a.length; i++){
      if((gi & 1) == 1)
        System.out.print("+"+a[i]);
      gi >>= 1;
    }
    System.out.println();
  }

Figure 9.4 : Code de Gray pour le sac-à-dos.


Remarques

Le code de Gray permet de visiter chacun des sommets d'un hypercube. L'hypercube en dimension n est formé précisément des sommets (x0, x1, …, xn-1) parcourant tous les n-uplets d'éléments formés de {0, 1}. Le code de Gray permet de visiter tous les sommets du cube une fois et une seule, en commençant par le point (0, 0, …, 0), et en s'arrêtant juste au-dessus en (1, 0, …, 0).





9.2.4  Retour arrière (backtrack)

L'idée est de résoudre le problème de proche en proche. Supposons avoir déjà calculé Si = x0 a0 + x1 a1 + … + xi-1 ai-1. Si Si = S, on a trouvé une solution et on ne continue pas à rajouter des aj>0. Sinon, on essaie de rajouter xi = 0 et on teste au cran suivant, puis on essaie avec xi = 1. On fait ainsi des calculs et si cela échoue, on retourne en arrière pour tester une autre solution, d'où le nom backtrack .

L'implantation de cette idée est donnée ci-dessous:
    // on a déjà calculé Si = sum(a[j]*x[j], j=0..i-1)
    static void sacADosrec(int[] a, int S, int[] x,
                           int Si, int i){
        nbrec++;
        if(Si == S)
            afficherSolution(a, S, x, i);
        else if(i < a.length){
            x[i] = 0;
            sacADosrec(a, S, x, Si, i+1);
            x[i] = 1;
            sacADosrec(a, S, x, Si+a[i], i+1);
        }
    }
On appelle cette fonction avec:
    static void sacADos(int[] a, int S){
        int[] x = new int[a.length];

        nbrec = 0;
        sacADosrec(a, S, x, 0, 0);
        System.out.print("# appels=" + nbrec);
        System.out.println(" // " + (1 << (a.length + 1)));
    }
et le programme principal est:
    public static void main(String[] args){
        int[] a = {1, 4, 7, 12, 18, 20, 30};

        sacADos(a, 11);
        sacADos(a, 12);
        sacADos(a, 55);
        sacADos(a, 14);
    }



On a ajouté une variable nbrec qui mémorise le nombre d'appels effectués à la fonction sacADosrec et qu'on affiche en fin de calcul. L'exécution donne:
S=11=+4+7
# appels=225 // 256
S=12=+12
S=12=+1+4+7
# appels=211 // 256
S=55=+7+18+30
S=55=+1+4+20+30
S=55=+1+4+12+18+20
# appels=253 // 256
# appels=255 // 256
On voit que dans le cas le pire, on fait bien 2n+1 appels à la fonction (mais seulement 2n additions).

On remarque que si les aj sont tous strictement positifs, et si Si > S à l'étape i, alors il n'est pas nécessaire de poursuivre. En effet, on ne risque pas d'atteindre S en ajoutant encore des valeurs strictement positives. Il suffit donc de rajouter un test qui permet d'éliminer des appels récursifs inutiles:
    // on a déjà calculé Si = sum(a[j]*x[j], j=0..i-1)
    static void sacADosrec(int[] a, int S, int[] x,
                           int Si, int i){
        nbrec++;
        if(Si == S)
            afficherSolution(a, S, x, i);
        else if((i < a.length) && (Si < S)){
            x[i] = 0;
            sacADosrec(a, S, x, Si, i+1);
            x[i] = 1;
            sacADosrec(a, S, x, Si+a[i], i+1);
        }
    }



On constate bien sur les exemples une diminution notable des appels, dans les cas où S est petit par rapport à ∑i ai:
S=11=+4+7
# appels=63 // 256
S=12=+12
S=12=+1+4+7
# appels=71 // 256
S=55=+7+18+30
S=55=+1+4+20+30
S=55=+1+4+12+18+20
# appels=245 // 256
# appels=91 // 256
Terminons cette section en remarquant que le problème du sac-à-dos est le prototype des problèmes difficiles au sens de la théorie de la complexité, et que c'est là l'un des sujets traités en Majeure 2 d'informatique.

9.3  Permutations

Une permutation des n éléments 1, 2, …, n est un n-uplet (a1, a2, …, an) tel que l'ensemble des valeurs des ai soit exactement {1, 2, …, n}. Par exemple, (1, 3, 2) est une permutation sur 3 éléments, mais pas (2, 2, 3). Il y a n! = n× (n-1)× 2× 1 permutations de n éléments.

9.3.1  Fabrication des permutations

Nous allons fabriquer toutes les permutations sur n éléments et les stocker dans un tableau. On procède récursivement, en fabriquant les permutations d'ordre n-1 et en rajoutant n à toutes les positions possibles:
    static int[][] permutations(int n){
        if(n == 1){
            int[][] t = {{0, 1}};

            return t;
        }
        else{
            // tnm1 va contenir les (n-1)! 
            // permutations à n-1 éléments
            int[][] tnm1 = permutations(n-1);
            int factnm1 = tnm1.length;
            int factn = factnm1 * n; // vaut n!
            int[][] t = new int[factn][n+1];

            // recopie de tnm1 dans t
            for(int i = 0; i < factnm1; i++)
                for(int j = 1; j <= n; j++){
                    // on recopie tnm1[][1..j[
                    for(int k = 1; k < j; k++)
                        t[n*i+(j-1)][k] = tnm1[i][k];
                    // on place n à la position j
                    t[n*i+(j-1)][j] = n;
                    // on recopie tnm1[][j..n-1]
                    for(int k = j; k <= n-1; k++)
                        t[n*i+(j-1)][k+1] = tnm1[i][k];
                }
            return t;
        }

9.3.2  Énumération des permutations

Le problème de l'approche précédente est que l'on doit stocker les n! permutations, ce qui peut finir par être un peu gros en mémoire. Dans certains cas, on peut vouloir se contenter d'énumérer sans stocker.

On va là aussi procéder par récurrence: on suppose avoir construit une permutation t[1..i0-1] et on va mettre dans t[i0] les n-i0+1 valeurs non utilisées auparavant, à tour de rôle. Pour ce faire, on va gérer un tableau auxiliaire de booléens utilise, tel que utilise[j] est vrai si le nombre j n'a pas déjà été choisi. Le programme est alors:
    // approche en O(n!)
    static void permrec2(int[] t, int n,
                         boolean[] utilise, int i0){
        if(i0 > n)
            afficher(t, n);
        else{
            for(int v = 1; v <= n; v++){
                if(! utilise[v]){
                    utilise[v] = true;
                    t[i0] = v;
                    permrec2(t, n, utilise, i0+1);
                    utilise[v] = false;
                }
            }
        }
    }

    static void permrec2(int n){
        int[] t = new int[n+1];
        boolean[] utilise = new boolean[n+1];

        permrec2(t, n, utilise, 1);
    }

Pour n=3, on fabrique les permutations dans l'ordre:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

9.4  Les n reines

Nous allons encore voir un algorithme de backtrack pour résoudre un problème combinatoire. Dans la suite, nous supposons que nous utilisons un échiquier n× n.

9.4.1  Prélude: les n tours

Rappelons quelques notions du jeu d'échecs. Une tour menace toute pièce adverse se trouvant dans la même ligne ou dans la même colonne.

On voit facilement qu'on peut mettre n tours sur l'échiquier sans que les tours ne s'attaquent. En fait, une solution correspond à une permutation de 1..n, et on sait déjà faire. Le nombre de façons de placer n tours non attaquantes est donc T(n) = n!.

9.4.2  Des reines sur un échiquier

La reine se déplace dans toutes les directions et attaque toutes les pièces (adverses) se trouvant sur les même ligne ou colonne ou diagonales qu'elle.



Une reine étant une tour avec un peu plus de pouvoir, il est clair que le nombre maximal de reines pouvant être sur l'échiquier sans s'attaquer est au plus n. On peut montrer que ce nombre est n pour n=1 ou n ≥ 41. Reste à calculer le nombre de solutions possibles, et c'est une tâche difficile, et non résolue.

Donnons les solutions pour n=4:



Expliquons comment résoudre le problème de façon algorithmique. On commence par chercher un codage d'une configuration. Une configuration admissible sera codée par la suite des positions d'une reine dans chaque colonne. On oriente l'échiquier comme suit:





Avec ces notations, on démontre:
Proposition 8   La reine en position (i1, j1) attaque la reine en position (i2, j2) si et seulement si i1 = i2 ou j1 = j2 ou i1-j1 = i2 - j2 ou i1 + j1 = i2 + j2.

Démonstration: si elle sont sur la même diagonale nord-ouest/sud-est, i1-j1 = i2 - j2; ou encore sur la même diagonale sud-ouest/nord-est, i1+j1 = i2+j2.

On va procéder comme pour les permutations: on suppose avoir construit une solution approchée dans t[1..i0[ et on cherche à placer une reine dans la colonne i0. Il faut s'assurer que la nouvelle reine n'attaque personne sur sa ligne (c'est le rôle du tableau utilise comme pour les permutations), et personne dans aucune de ses diagonales (fonction pasDeConflit). Le code est le suivant:



    // t[1..i0[ est déjà rempli
    static void reinesAux(int[] t, int n,
                          boolean[] utilise, int i0){
        if(i0 > n)
            afficher(t);
        else{
            for(int v = 1; v <= n; v++)
                if(! utilise[v] && pasDeConflit(t, i0, v)){
                    utilise[v] = true;
                    t[i0] = v;
                    reinesAux(t, n, utilise, i0+1);
                    utilise[v] = false;
                }
        }
    }
La programmation de la fonction pasDeConflit découle de la proposition 8:
    // t[1..i0[ est déjà rempli
    static boolean pasDeConflit(int[] t, int i0, int j){
        int x1, y1, x2 = i0, y2 = j;

        for(int i = 1; i < i0; i++){
            // on récupère les positions
            x1 = i;
            y1 = t[i];
            if((x1 == x2) // même colonne
               || (y1 == y2) // même ligne
               || ((x1-y1) == (x2-y2))
               || ((x1+y1) == (x2+y2)))
                return false;
        }
        return true;
    }

Notons qu'il est facile de modifier le code pour qu'il calcule le nombre de solutions.

Terminons par un tableau des valeurs connues de R(n):
n R(n) n R(n) n R(n) n R(n)
4 2 9 352 14 365596 19 4968057848
5 10 10 724 15 2279184 20 39029188884
6 4 11 2680 16 14772512 21 314666222712
7 40 12 14200 17 95815104 22 2691008701644
8 92 13 73712 18 666090624 23 24233937684440

Vardi a conjecturé que logR(n)/(nlogn) → α > 0 et peut-être que α=1. Rivin & Zabih ont d'ailleurs mis au point un algorithme de meilleur complexité pour résoudre le problème, avec un temps de calcul de O(n2 8n).

9.5  Les ordinateurs jouent aux échecs

Nous ne saurions terminer un chapitre sur la recherche exhaustive sans évoquer un cas très médiatique, celui des ordinateurs jouant aux échecs.

9.5.1  Principes des programmes de jeu

Deux approches ont été tentées pour battre les grands maîtres. La première, dans la lignée de Botvinik, cherche à programmer l'ordinateur pour lui faire utiliser la démarche humaine. La seconde, et la plus fructueuse, c'est utiliser l'ordinateur dans ce qu'il sait faire le mieux, c'est-à-dire examiner de nombreuses données en un temps court.

Comment fonctionne un programme de jeu ? En règle général, à partir d'une position donnée, on énumère les coups valides et on crée la liste des nouvelles positions. On tente alors de déterminer quelle est la meilleure nouvelle position possible. On fait cela sur plusieurs tours, en parcourant un arbre de possibilités, et on cherche à garder le meilleur chemin obtenu.

Dans le meilleur des cas, l'ordinateur peut examiner tous les coups et il gagne à coup sûr. Dans le cas des échecs, le nombre de possibilités en début et milieu de partie est beaucoup trop grand. Aussi essaie-t-on de programmer la recherche la plus profonde possible.

9.5.2  Retour aux échecs

Codage d'une position

La première idée qui vient à l'esprit est d'utiliser une matrice 8× 8 pour représenter un échiquier. On l'implante généralement sous la forme d'un entier de type long qui a 64 bits, un bit par case. On gère alors un ensemble de tels entiers, un par type de pièce par exemple.

On trouve dans la thèse de J. C. Weill un codage astucieux: On stocke la position dans le vecteur de bits
(c1, c2, …, c768)
tel que c64i+j+1=1 ssi la pièce i est sur la case j.

Les positions sont stockées dans une table de hachage la plus grande possible qui permet de reconnaître une position déjà vue.

Fonction d'évaluation

C'est un des secrets de tout bon programme d'échecs. L'idée de base est d'évaluer la force d'une position par une combinaison linéaire mettant en oeuvre le poids d'une pièce (reine =900, tour=500, etc.). On complique alors généralement la fonction en fonction de stratégies (position forte du roi, etc.).

Bibliothèques de début et fin

Une façon d'accélérer la recherche est d'utiliser des bibliothèque d'ouvertures pour les débuts de partie, ainsi que des bibliothèques de fins de partie.

Dans ce dernier cas, on peut tenter, quand il ne reste que peu de pièces d'énumérer toutes les positions et de classifier les perdantes, les gagnantes et les nulles. L'algorithme est appelé analyse rétrograde et a été décrite par Ken Thompson (l'un des créateurs d'Unix).

À titre d'exemple, la figure ci-dessous décrit une position à partir de laquelle il faut 243 coups (contre la meilleure défense) à Blanc (qui joue) pour capturer une pièce sans danger, avant de gagner (Stiller, 1998).

Deep blue contre Kasparov (1997)

Le projet a démarré en 1989 par une équipe de chercheurs et techniciens: C. J. Tan, Murray Campbell (fonction d'évaluation), Feng-hsiung Hsu, A. Joseph Hoane, Jr., Jerry Brody, Joel Benjamin. Une machine spéciale a été fabriquée: elle contenait 32 noeuds avec des RS/6000 SP (chip P2SC); chaque noeud contenait 8 processeurs spécialisés pour les échecs, avec un système AIX. Le programme était écrit en C pour le IBM SP Parallel System (MPI). La machine était capable d'engendrer 200,000,000 positions par seconde (ou 60× 109 en 3 minutes, le temps alloué). Deep blue a gagné 2 parties à 1 contre Kasparov2.

Deep Fritz contre Kramnik (2002)

C'est cette fois un ordinateur plus raisonnable qui affronte un humain: 8 processeurs à 2.4 GHz et 256 Mo, qui peuvent calculer 3 millions de coups à la seconde. Le programmeur F. Morsch a soigné la partie algorithmique. Kramnik ne fait que match nul (deux victoires chacun, quatre nulles), sans doute épuisé par la tension du match.

Conclusion

Peut-on déduire de ce qui précède que les ordinateurs sont plus intelligents que les humains ? Certes non, ils calculent plus rapidement sur certaines données, c'est tout. Pour la petite histoire, les joueurs d'échec peuvent s'adapter à l'ordinateur qui joue face à lui et trouver des positions qui le mettent en difficulté. Une manière de faire est de jouer systématiquement de façon à maintenir un grand nombre de possibilités à chaque étape.
1
Les petits cas peuvent se faire à la main, une preuve générale est plus délicate et elle est due à Ahrens, en 1921.
2
www.research.ibm.com/deepblue

Précédent Remonter Suivant