Qu’est-ce qu’un problème combinatoire ?
Définition
Un problème combinatoire est un problème où l’on doit explorer ou compter toutes les combinaisons possibles d’un ensemble d’éléments pour trouver une solution optimale (ou toutes les solutions valides).
Autrement dit : on cherche une solution parmi énormément de possibilités, souvent en testant plein de configurations différentes.
Exemple classique : Le sac à dos
Tu as :
- Un sac peut contenir 10 kg
- 5 objets (A à E), chacun ayant un poids et une valeur
- Tu veux remplir ton sac pour maximiser la valeur totale, sans dépasser 10 kg
Tu dois donc essayer plein de combinaisons :
- A seulement ?
- A et C ?
- B et D ?
- A, B et E ?
- ... etc.
Il y a 2^n combinaisons possibles
- Si tu as 20 objets → plus d’un million de combinaisons à tester !
- Si tu en as 100 → plus de
10³⁰combinaisons
Autres exemples de problèmes combinatoires :
| Problème | Complexité naïve | Description |
|---|---|---|
| Voyageur de commerce | O(n!) | Trouver le plus court chemin pour visiter plusieurs villes — c'est une permutation (l'ordre compte : A→B→C ≠ A→C→B) |
| Sac à dos | O(2^n) | Choisir des objets à emporter — c'est une combinaison (on prend ou non chaque objet, l'ordre ne compte pas) |
| Coloration de graphe | O(k^n) | Colorier un graphe sans que deux voisins aient la même couleur |
| Sudoku | O(9^n) | Compléter la grille avec toutes les règles |
| Placement d'objets | O(n!) | Organiser un horaire, un plan de salle, etc. |
Pourquoi sont-ils durs ?
Parce qu’ils impliquent souvent :
- Un grand nombre de choix à considérer
- Pas de formule magique pour trouver la solution rapidement
- Une solution naïve prend souvent un temps exponentiel (
O(2^n)) ou factoriel (O(n!))O(2^n)→ problèmes de combinaison (on choisit ou non chaque élément, l'ordre n'a pas d'importance)O(n!)→ problèmes de permutation (l'ordre de visite ou d'arrangement compte)
En résumé
Un problème combinatoire est un problème où on doit combiner, arranger ou choisir des éléments pour trouver une solution.
Ces problèmes sont puissants, mais souvent très coûteux à résoudre dès qu’on augmente un peu la taille des données.