Chapitre 5 :

Classes de complexité

Classe: M1SIAD
 Plan
1. Rappel sur la complexité
2. Classes de problèmes
3. Définition d'un problème d'optimisation
4. Classification de problèmes d’optimisation
5. Méthodes de résolution de problèmes d’optimisation
 1. Rappels sur la complexité algorithmique

- La complexité d'un algorithme est la quantité de ressources nécessaires pour

que cet algorithme accomplit sa tâche. Il existe deux types de complexité :
1) La complexité spatiale : concerne la taille de la mémoire nécessaire pour l'exécution
de l'algorithme.
2) La complexité temporelle : concerne le nombre d’instructions élémentaires qu'il doit exécuter.
- La complexité d’un algorithme est toujours mesurée en fonction de la taille des données en entrée
(n).
-Dans la littérature, lorsqu'on parle de la complexité d'un algorithme, il s’agit de la complexité
temporelle dans le pire des cas.
- Exemples : n7 + 2030 instructions, n + 3 instructions, etc... (n est la taille des données en entrée).

3
 1. Rappels sur la complexité algorithmique

Les classes classiques de complexité :

O : ordre de grandeur Type de complexité
O(1) Constante
O(log(n)) Logarithmique
O(n) Linéaire
O(nlog(n)) Quasi-linéaire
O(n2) Quadratique
O(n3) Cubique
O(cn) Exponentielle
O(n!) Factorielle 4
 2. Classes de problèmes

• Dans la vie, les entreprises sont confrontées à de nombreuses problématiques qui

deviennent de plus en plus complexes au fil du temps dans différents domaines
comme le transport, l'industrie, l'économie, l'énergie, la distribution des
marchandises, la production…etc.

• La recherche d’une solution optimale ou sous optimale dans un temps raisonnable

est devenue une priorité importante dans chaque entreprise.
 occupent en particulier une
place importante pour résoudre ces nombreux problèmes. Dans le processus de
décision nous devons répondre "oui "ou "non" pour savoir s'il existe une
solution à ce problème, par contre, l’optimisation combinatoire cherche à
optimiser la valeur d’une fonction.

• Généralement, Les problèmes d'optimisation combinatoire sont souvent faciles

à définir et difficiles à résoudre.
 2. Classes de problèmes

- Un problème de décision : est un problème (sous forme de question) qui a une

réponse par oui ou par non.
Exemple : Soient a et b deux entiers, existe-t-il un diviseur commun entre a et b ?
- La classe P (Polynomiale) : Un problème de décision A appartient à la classe P
s'il existe un algorithme en temps polynomial qui peut résoudre A (c'est à dire un
algorithme avec une complexité O(n k ) où k est indépendant de la taille des
données en entrée).
La classe P est la classe des problèmes "faciles".
Exemple : soit un graphe orienté G, et deux sommets s et t. Est-ce qu'il y a un
chemin reliant le sommet s au sommet t dans G ?
8
 2. Classes de problèmes

- La classe NP (Non-déterministe Polynomiale) : un problème de décision A est

dans la classe NP, s'il existe un algorithme polynomial qui peut vérifier la validité
d'une solution à ce problème (A).
Exemple : Soit un ensemble S de n entiers, existe-t-il un sous-ensemble S' dont
Σ S' = (Σ S)/2 ? => On peut vérifier une solution à ce problème avec un
algorithme en O(n).
- Remarque : il est claire que P ⊂ NP.
- La réduction de turing : On dit qu'un problème B se réduit à problème A si:
Il existe un solveur SL2 du problème B qui peut appeler le solveur SL1
du problème A et la complexité de SL2 sans compter la complexité de SL1 est
polynomiale. 9
 2. Classes de problèmes

A: E1 SL1 : solveur de A S1

B: E2 SL2 solveur de B S2

B se réduit à A si : SL2 utilise SL1 et

la complexité de SL2 sans compter la
complexité de SL1 est polynomiale.
10
 2. Classes de problèmes

- La classe NP-complète :
- Un problème de décision A est dans la classe NP-complète, si:
1) Le problème A appartient à la classe NP.
2) On peut réduire n'importe quel problème dans la classe NP à A.
Ou bien
1) Le problème A appartient à la classe NP.
2) Il existe un problème NP-complet B tel que B est réductible à A.

-Remarque: la complexité d'un problème qui appartient à la classe NP-

complète est au moins exponentielle. 12
 2. Classes de problèmes

- La classe NP-difficile :
- Un problème A appartient à la classe NP-difficile s'il existe un
problème NP-complet B tel que B est réductible à A.

- Remarque: La classe NP-difficile ne se limite pas aux seuls problèmes

de décision et elle contient aussi d'autres genres de problèmes.

13
 2. Classes de problèmes

- Les problèmes d'optimisation combinatoire sont des

problèmes NP-difficiles

14
 3. Définition d’un problème
d’optimisation combinatoire

Min (ou Max) f(s)

s∈ S

- S : un ensemble fini de solutions.

- La résolution d'un problème d'optimisation consiste à trouver la
meilleure solution réalisable sbest dans S (c'est-à-dire la solution qui
rend minimale (ou maximale) la fonction objectif f(s)).
- Une solution s ∈ S est réalisable, si elle respecte toutes les
contraintes du problème. 15
 3. Définition d’un problème
d’optimisation combinatoire

- Dans le domaine d'optimisation combinatoire, l'ensemble S est appelé

l'espace de recherche.

- En cherchant la solution optimale sbest ∈ S pour un problème

d’optimisation, la difficulté majeure est d'examiner toutes les solutions
dans S, quand S contient un nombre énorme de solutions.

16
 Exemple d’un problème
d’optimisation combinatoire

Le problème de voyageur de commerce

Le problème du voyageur de commerce (en anglais : Travelling Salesman

Problem, TSP) consiste à construire un tour ou un chemin pour un
voyageur en visitant un ensemble de villes et en retournant à la ville de
départ. Le voyageur doit visiter l’ensemble des villes en passant une et une
seule fois par chaque ville avec pour objectif de minimiser la distance du
chemin parcouru.
17
 Exemple d’un problème
d’optimisation combinatoire

Le problème de voyageur de commerce

- Le chemin :2-4-5-1-6-3-2 1
2
4 2
est une solution de TSP et 6 5
7
sa valeur = 19. 4 3 2
- Dans cet exemple, le nombre 2
6 3
de solutions possibles est: 6
((6-1)! / 2) = 60. 2 8 3
6
5 4
1

18
 Exemple d’un problème
d’optimisation combinatoire

Le problème de voyageur de commerce

- Pour un nombre de sommets (villes) égale à 100 nous avons 99!/2 de
solutions Possibles (10155).
- Même avec un ordinateur ultra puissant qui exécute 1018
instructions par seconde, nous avons besoin d'environ 10127 ans pour
parcourir toutes les solutions possibles afin de trouver la solution
optimale !!!

19
 4. Classification de problèmes
d’optimisation

- En général, les critères utilisés pour classifier les problèmes

d'optimisation sont :
1) Domaines des variables de décision : (Continu Vs. Discret ou combinatoire)
2) Le nombre de critères à optimiser : (Mono objectif Vs. Multi objectifs)
3) L'existence des variables aléatoires dans le problème : (Déterministe Vs.
Stochastique)
4) L'évolution des variables avec le temps : (Statique Vs. Dynamique)
Etc...

21
 4. Classification de problèmes
d’optimisation

1) Domaines des variables de décision : Continu Vs. Discret ou combinatoire

Un problème d'optimisation est :
1.1) Continu :
Si les solutions de problème appartiennent à un ensemble continu, par exemple si
la solution est un nombre réel entre deux limites.
1.2) Discret ou combinatoire :
Si les solutions de problème appartiennent à un ensemble discret et la solution est
une combinaison d'éléments de problème, par exemple une solution au TSP.

22
 4. Classification de problèmes
d’optimisation

2) Le nombre de critères à optimiser : Mono objectif Vs. Multi objectifs

Un problème d'optimisation est :
2.1) Mono objectif :
S'il y a un seul critère à optimiser dans la fonction objectif.
2.2) Multi objectifs :
S'il y a plusieurs critères à optimiser dans la fonction objectif.

23
 4. Classification de problèmes
d’optimisation

3) L'existence des variables aléatoires dans le problème : Déterministe Vs.

Stochastique
Un problème d'optimisation est :
3.1) Déterministe :
Si tous les toutes les variables du problème sont déterministes.
3.2) Stochastique:
S'il y a au moins une variable du problème définie sous forme d'une
variable aléatoire.
24
 4. Classification de problèmes
d’optimisation

2) L'évolution des variables avec le temps : Statique Vs. Dynamique

- Un problème d'optimisation est :
2.1) Statique :
Si les variables du problème ne changent pas avec le temps.
2.2) Dynamique :
Si les variables du problème changent avec le temps.

25
 Problèmes d’optimisation
dans différents domaines

-Logistique
1) Planification des tournées de distribution, de maintenance et de
collecte.
2) Le routage des taxis dans le domaine de transport à la demande.
3) La planification des tâches d'accostage et de désaccostage des navires
dans les ports.
- La santé & les hôpitaux
1) La planification des opérations dans les chambres en considérant
les contraintes de disponibilités.
26
 Problèmes d’optimisation
dans différents domaines

- Engineering
L'énergie renouvelable: détermination de paramètres pour les panneaux
solaires.
- Cloud computing
L'ordonnancement des taches dans un cloud.
- Réseaux
Le routage multicast avec qualité de service.
etc.….
27
 5. Méthodes de résolution de problèmes
d’optimisation

Méthodes d'optimisation

Méthodes approchées Méthodes exactes

Heuristiques Métaheuristiques Etc..

Métaheuristiques à base Métaheuristiques à base de

de solution unique population de solutions
28
 5. Méthodes de résolution de problèmes
d’optimisation

- Méthodes approchées
Des méthodes non-exhaustives qui cherchent à trouver une solution de
bonne qualité (pas nécessairement optimale) dans un temps de calcul
raisonnables.
- Méthodes exactes
Des méthodes exhaustives qui cherchent à examiner toutes les solutions,
dont le but est de trouver la solution optimale. L'inconvénient majeur de
ces méthodes est le temps de calculs surtout pour les moyennes et les
grandes instances.
29
Merci pour votre attention !