Question de méthode

Gilles Dowek a été l'un des lauréats du prix d'Alembert, un prix créé par la Société Mathématique de France, et décerné par un jury de lycéens le 28 mai 2000 à la Cité des Sciences et de l'Industrie. Voici une partie de son exposé.

Gilles Dowek : Un ami m'a demandé de lui ramener 12 kilos de sucre en poudre de voyage. J'ai trouvé ce paquet de 7 kilos, celui-ci de 6 kilos, celui-ci de 4 et ces deux paquets de 3 kilos. Est-il possible avec ces paquets de remplir un sac qui fasse exactement 12 kilos ? Si je prends uniquement ce paquet, 7 kilos, ce n'est pas assez, si je prends ces deux-là, treize kilos, c'est trop. Si je prends ces deux-là, 11 kilos, ce n'est pas assez. Mais il y a une solution qui consiste à prendre ce paquet de 6 kilos et ces deux paquets de 3 kilos.
Dans une situation comme celle-ci où il est facile de tester si une solution potentielle est une solution ou non, puisqu'il suffit d'ajouter le poids des paquets et de vérifier si on obtient 12 kilos ou pas, mais où il est plus difficile de trouver une solution quand on a juste les paquets d'un côté et le poids du sac de l'autre on dispose d'une méthode générale qui s'appelle la méthode de recherche exhaustive. Cette méthode consiste à énumérer tous les sacs qu'on peut faire avec ces objets, depuis le sac vide qui ne contient aucun paquet jusqu'au sac qui les contient tous les cinq. Pour chacun de ces trente deux sacs, on peut calculer le poids obtenu et tester si on obtient un sac de 12 kilos ou non. Après avoir énuméré les trente deux solutions potentielles ou bien on en aura trouvé une comme celle-ci, ou bien, et ça serait le cas si on cherchait à faire un sac de 8 kilos, on s' apercevrait qu'aucune ne convient et on constaterait l'absence de solution.

Cette méthode de recherche exhaustive dont on vient de voir qu'elle permet de remplir des sacs peut s'appliquer à des problèmes très divers et c'est en fait une des méthodes de base de l'informatique. Elle peut par exemple permettre de résoudre le jeu du solitaire. Alors ce jeu, je pense que tout le monde le connaît, il se joue sur un plateau qui contient 33 cases qui forment une croix, et disposées sur ces 33 cases, 32 billes, en laissant vide la case du milieu. On peut déplacer une bille vers une case libre en sautant par-dessus une autre bille qui est retirée du jeu. Le but du jeu, c'est d'arriver à ne laisser qu'une seule bille sur le plateau. Ici, j'ai commencé une partie, je peux continuer comme ça, puis comme ça, puis comme ça, un cinquième, un sixième et là j'arrive à une situation bloquée. Il n'y a plus de moyen de déplacer une bille. Donc je suis parti dans une mauvaise direction et il faut que j'essaie autre chose.
Bon, de cette manière, je vais pouvoir tâtonner et trouver peut-être une solution si j'ai un petit peu de chance ou si je suis suffisamment patient. Il y a une autre méthode pour résoudre le jeu du solitaire est d'essayer systématiquement toutes les solutions. Donc pour ça il faut un tout petit peu mathématiser le problème. Tout à l'heure j'ai dit je prends cette bille et je la déplace ici. Il faut que j'ai une manière de nommer les cases qui se trouvent sur le plateau. Et pour ça je vais juste utiliser la méthode des joueurs d'échec qui consiste à repérer une case par son abscisse et son ordonnée, c'est-à-dire le numéro de sa colonne et le numéro de sa ligne. Le coup qui consiste à déplacer ce pion vers cette case, on l'appelle (4,2) (4,4).
Nommer les cases va me permettre de nommer les coups puisque un coup se décrit en donnant la case de départ et la case d'arrivée puis de nommer les solutions potentielles. Une solution potentielle, c'est juste une suite de coups. Donc de cette manière je vais pouvoir énumérer toutes les solutions potentielles et les tester l'une après l'autre. C'est très facile de tester si une suite de coups qu'on décrit avec des nombres est une solution ou pas. Par exemple si je dis : je vais commencer par déplacer cette bille ici, on voit bien que ça ne marche pas puisque cette case n'est pas libre donc on peut éliminer cette solution potentielle. Maintenant il faut comprendre si on est dans un cadre où le nombre de situations à explorer est fini ou infini : si on a un nombre fini on sait qu'on peut les tester toutes, si y en a une qui est une solution on la trouvera, on aura gagné, si y en a pas on va toutes les tester et on va savoir, on va se rendre compte qu'il n'y a pas de solution. Alors ici, a priori on a l'impression qu'on se trouve dans un cadre infini; pourquoi? Certes il n'y a que 7 lignes et 7 colonnes mais comme on vient de dire qu'une partie se repère par une suite de nombres, à priori, les suites de nombres sont elles-mêmes en nombre infini; il peut y avoir des suites de longueur arbitraire et donc il y a une infinité de suites de nombres. Pourtant il y a une propriété particulière de ce jeu, du jeu du solitaire, qui fait que on peut se ramener à un cas fini : en effet, à chaque coup on va retirer une bille, on a dit qu'il y avait au départ 32 billes, on veut qu'il en reste une seule à la fin donc on sait que, une partie gagnante, une partie qui résout le problème fera nécessairement 31 coups, donc on sait limiter la longueur des suites qu'il est nécessaire d'explorer et donc on sait qu'elles sont en nombre fini, qu'on peut toutes les énumérer et les tester l'une après l'autre.
Donc ça c'est une solution un petit peu théorique, pourquoi ? Parce que on peut faire un petit calcul du nombre de suites à calculer, du nombre de suites à explorer et on s'aperçoit que même si on en teste un milliard par seconde ce qui est bien au-delà de ce qu'on peut faire à la main, et également bien au-delà de ce que peuvent faire les ordinateurs, il faudrait 10 puissance 88 années pour toutes les tester. 10 puissance 88 années c'est 10 millions de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards d'années donc ça fait beaucoup. C'est trop long pour résoudre un problème comme celui-ci. Alors, il faut trouver une autre idée. En général, les solutions exhaustives toutes seules ne marchent pas. Il faut mélanger une solution brutale, une solution exhaustive, avec un petit peu d'intelligence pour restreindre l'espace de recherche. Ici il est facile de voir qu'au premier coup il y a que 4 boules qu'on peut bouger donc il est inutile d'explorer toutes les situations qui commencent par exemple par déplacer cette bille ou celle-ci. Ensuite, il y a que trois possibilités pour le deuxième coup qui consiste à déplacer vers cette case cette bille, celle-ci ou celle-là. En début de partie, il y a très peu de possibilités parce qu'il y a très peu de places libres pour déplacer une bille. En fin de partie, il va aussi y avoir très peu de possibilités parce qu'il va y avoir très peu de billes qu'on peut déplacer. En milieu de partie on va avoir davantage de possibilités donc le nombre de solutions à explorer commence petit puis croît au cours de la partie, puis décroît à nouveau pour finir.

Avec cette idée, on peut énumérer les suites de cette manière mieux organisée, de cette manière plus intelligente pour chercher s'il y a une solution ou pas et donc voilà ce que ça donne : je lance un programme qui recherche une solution et on voit que il prend un petit peu de temps à calculer. Il va trouver une solution, que voilà...
Bien sûr, le solitaire ce n'est qu'un jeu qui permet d'illustrer cette notion de recherche exhaustive, c'est pas un problème mathématique très intéressant, mais cette idée de recherche exhaustive est utilisée pour résoudre d'autres problèmes, certains problèmes mathématiques mais aussi beaucoup de problèmes de la vie quotidienne, par exemple pour résoudre ce qu'on appelle le problème du voyageur de commerce les compagnies aériennes par exemple qui cherchent à envoyer leurs avions dans différentes villes en déplaçant tous leurs passagers et en économisant au maximum le kérosène utilisent des méthodes qui sont fondées sur la recherche exhaustive. Pour ce problème du voyageur de commerce comme pour le problème du solitaire, la recherche exhaustive toute seule ne suffit pas et il faut organiser la recherche d'une manière intelligente si on veut trouver une manière de déplacer les avions qui soit à la fois efficace et économique.