Fanny Pascual
Vous êtes en vacances dans une métropole, et vous vous trouvez devant un plan de métro. Votre problème est le suivant : quel est l'itinéraire le plus court pour aller de la station de métro où vous vous trouvez, à celle où vous souhaitez aller ? Sans le savoir, vous vous trouvez face à un problème qui peut être facilement résolu par un algorithme : étant donné un plan de métro et deux stations A et B, trouver le chemin le plus court (en nombre de stations) qui va de A vers B.
Supposons que l'on charge un ordinateur de résoudre ce problème. Supposons également que nous ayons accès à l'ordinateur de notre choix. Tant qu'à faire, choisissons TaihuLight, l'ordinateur le plus puissant au monde (ce supercalculateur chinois peut faire 94 000 000 000 000 000 opérations par seconde !). Étant donné la puissance de la machine, un premier réflexe serait de faire au plus simple : on demande à l'ordinateur de tester toutes les combinaisons possibles des stations (toutes les permutations). L'ordinateur connaît le plan de métro : étant donné une permutation, il regarde si elle correspond à une liste de stations voisines. Si c'est le cas, alors c'est que la liste des stations est un chemin possible. L'ordinateur calcule la longueur de ce chemin (le nombre de stations qu'il parcourt), et garde en mémoire le chemin le plus court trouvé.
Plan du métropolitain de Paris de 1973. Roger W/Flickr, CC BY-SA
En utilisant cet algorithme, si le réseau de métro contient 19 stations (ce qui, on en convient, est bien peu), le supercalculateur trouvera le chemin le plus court en moins d'une seconde. En effet, pour combiner 19 stations (ou plutôt 18, puisque la première est A), il y a 18×17×16×... ×2×1 = 6 402 373 705 728 000 choix possibles.
On divise ce nombre de permutations à examiner par le nombre d'opérations par seconde de notre ordinateur, et on trouve que l'ordinateur met moins d'une seconde à trouver le chemin le plus court (et même si l'ordinateur fait plusieurs opérations et non une seule pour vérifier qu'une permutation est un chemin, cela ne change pas l'ordre de grandeur du temps mis).
L’actualité qui compte pour vous, chaque jour dans votre boîte mail.
Si le réseau contient 21 stations, l'ordinateur mettra 25 secondes à trouver le chemin le plus court. Avec 23 stations, il lui faudra un peu plus de 3 heures, tandis qu'avec 25 stations il lui faudra 76 jours. Avec 30 stations il lui faudra plus de 2 982 siècles ! C'est ce que l'on appelle l'explosion combinatoire : ici, si l'on ajoute une station à un plan de n stations, le temps d'exécution de l'algorithme devra être multiplié par n.
Ce résultat est décourageant, mais en fait notre ordinateur pourrait faire bien mieux : pour trouver le chemin le plus court dans un plan de métro, il existe un algorithme bien plus efficace.
On demande maintenant à l'ordinateur de sélectionner toutes les stations voisines de votre station de départ, A. Ces stations sont donc à distance 1 de A. S'il a trouvé une station X, il mémorise le chemin A-X.
Puis, il explore les stations voisines de ces stations à distance 1 (stations à distance 2 de A donc). Il continue ainsi de suite, jusqu'à tomber sur la station de destination, B. En utilisant cet algorithme, notre supercalculateur mettrait moins d'une milliseconde à trouver le plus court chemin entre deux stations dans un plan contenant un million de stations !
Vous êtes soulagés, et vous vous dites que finalement vous aimeriez visiter plusieurs lieux se trouvant à différentes stations de métro de cette ville. Votre but est donc maintenant de trouver un itinéraire comprenant tous ces lieux. Vous ne souhaitez pas vous éterniser dans le métro, et votre problème est le suivant : quel est le chemin le plus court qui permet d'aller à toutes les stations que vous avez sélectionnées ?
Plan du métro de Tokyo. Oran Viriyincy/Flickr, CC BY
Là, malheureusement, la solution est moins simple. Personne ne connaît d'algorithme efficace trouvant à coup sûr la meilleure solution ! C'est le fameux problème du voyageur de commerce.
Et non seulement personne ne connaît un tel algorithme, mais si quelqu'un en trouvait un alors cet algorithme permettrait de résoudre des centaines de problèmes très étudiés par les chercheurs, ayant énormément d'applications dans l'industrie - mais des problèmes pour lesquels personne n'a encore trouvé d'algorithme efficace (c'est-à-dire rapide).
On dit que ce problème est difficile, alors que celui consistant à trouver un plus court chemin est considéré comme facile.
Les problèmes difficiles sont rencontrés très couramment : trouver des tournée de véhiculeslivrant des clients et minimisant la distance parcourue ; planifier des emplois du temps étant donné une liste de contraintes ; affecter des tâches à des machines qui les exécutent de manière à ce que les tâches soient terminées le plus tôt possible ; sont par exemple des problèmes difficiles.
Revenons à nos deux problèmes de recherche de plus court chemin entre deux stations, et de recherche d'itinéraire comprenant plusieurs points d'intérêt. Pour ces deux problèmes, vérifier qu'une solution est réalisable est facile (vous et moi pouvons aisément vérifier qu'un chemin entre A et B est bien un chemin, ou qu'un chemin passe bien par toutes les stations qu'on lui a demandé).
Ces problèmes, facilement vérifiables, forment la classe NP. Les problèmes faciles à résoudre, comme celui consistant à trouver un plus court chemin, forment, à l'intérieur de la classe NP, la classe P. Une des principales questions en informatique (et en mathématiques) est la suivante : est-ce que P est différent de NP ? Autrement dit, pour les problèmes difficiles de NP (comme notre problème d'itinéraire comprenant plusieurs points d'intérêt), la question est : est-ce qu'il existe un algorithme efficace (mais que l'on n'a pas encore trouvé), ou bien est-ce qu'il n'en existe pas ?
Les chercheurs sont persuadés que P est différent de NP. Mais en attendant de trouver la réponse à cette question, les chercheurs et ingénieurs s'emploient à trouver pour les problèmes difficiles des algorithmes efficaces qui retournent de bonnes solutions, à défaut d'être toujours les meilleures.
Mais avoir des problèmes difficiles peut aussi être un atout : si l'on arrivait à résoudre efficacement des problèmes difficiles (si P=NP), alors les implications seraient très importantes. Par exemple, tout un pan de la cryptographie s'effondrerait (les systèmes de cryptographie à clé publique, par exemple le chiffrement RSA, très utilisé dans le commerce électronique, seraient en effet cassés !).
_____
Par Fanny Pascual, Enseignante-chercheuse en informatique , Université Pierre et Marie Curie (UPMC) - Sorbonne Universités
La version originale de cet article a été publiée sur The Conversation
Fanny Pascual
