ALGORITHMIQUE

Algorithmes combinatoires

Entrent dans la catégorie des problèmes combinatoires, en informatique, les problèmes qui consistent à déterminer, pour une donnée d, si est satisfaite une condition :

où : (a) S(d) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de d ; (b) Q est une condition facilement vérifiable algorithmiquement (c'est-à-dire en un temps polynomial en la taille de ses arguments).

L'exemple le plus simple est le problème du sac à dos. Sous sa forme la plus élémentaire, il consiste, pour une donnée d = (d₁, d₂, ..., d_m ; M) où d_i, M ∈ N, à déterminer s'il existe des s_i∈ {0 ; 1} tels que :

En termes concrets : Peut-on remplir exactement un sac de capacité M avec un sous-ensemble d'objets de taille d₁, d₂, ..., d_n ? L'analogie avec (1) est immédiate : S(d) est l'ensemble {0, 1}ⁿ (de taille 2ⁿ) et la condition Q(d, s) est la condition (2) trivialement vérifiable par addition lorsque d et s sont connus.

On reconnaîtra de même comme appartenant à cette catégorie les problèmes suivants :

– Le problème du voyageur de commerce. La donnée est constituée d'un ensemble V de villes, pour chaque paire v, v′ ∈ V d'une distance d(v, v′) ∈ N, et d'une borne B ∈ N. Le problème consiste à déterminer s'il existe une « tournée » de V de longueur bornée par B : soit m la cardinalité de V ; il s'agit de déterminer s'il existe une permutation v_σ(1), v_σ(2), ..., v_σ(m) de V telle que :

– Le problème du coloriage de graphes. Étant donné un graphe G et un entier m, déterminer si G est m-coloriable, c'est-à-dire s'il existe une fonction f de l'ensemble des sommets de G dans {1, 2, ..., m} telle que, pour toute arête {s, s′} du graphe :– La programmation en nombres entiers. La donnée est un ensemble de formes linéaires M, L₁, L₂... de Z^m dans Z (à coefficients entiers) et un ensemble d'entiers B, b₁, b₂... Il s'agit de déterminer si le système d'inégalités :possède une solution entière ȳ ∈ Z^m.

Convenablement formalisée par référence à un modèle de calcul (par exemple le modèle de la machine de Turing), et à un codage standard des données, la relation (1) définit la notion de problème NP – c'est-à-dire résoluble en temps polynomial par une machine non déterministe. Les problèmes NP sont résolubles algorithmiquement en un temps 2^p(n) pour un certain polynôme p : il suffit pour cela d'organiser une recherche exhaustive sur l'espace de recherche S(d).

Il a été montré, à la suite de travaux de Cook et Karp vers 1970, que plusieurs centaines de problèmes de la classe NP, d'origine très variée en théorie des graphes, ordonnancement, théorie des jeux, optimisation combinatoire..., sont algorithmiquement équivalents : on entend par là qu'ils sont inter-réductibles au moyen de réductions algorithmiquement « efficaces », c'est-à-dire calculables en temps polynomial. Malgré l'ampleur des recherches algorithmiques, aucun algorithme n'a été trouvé qui permette de résoudre l'un quelconque de ces problèmes en un temps polynomial en la taille des données d'entrées. Ce fait donne lieu à la célèbre conjecture :

dans laquelle P désigne la classe des problèmes résolubles en temps polynomial.

Étant donné le caractère hautement plausible de cette conjecture, la recherche concernant les problèmes combinatoires s'oriente soit vers la découverte de sous-problèmes algorithmiquement résolubles rapidement (par un algorithme dans P), soit vers la découverte d'heuristiques permettant de trouver des solutions approchées rapidement.

Dans le cas des quatre problèmes précédemment cités, on a en particulier obtenu les résultats suivants :

– Problème du sac[...]