4. 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 :
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 = (d1, d2, ..., dm ; M) où di, M ∈ N, à déterminer s'il existe des si ∈ {0 ; 1} tels que :
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σ(
… pour nos abonnés, l'article se prolonge sur 10 pages…
