Université d’Alger 1 Benyoucef Benkhedda
Département de Mathématiques et Informatique
Optimisation Combinatoire:
Méthodes par séparation et
évaluation
Le niveau: Année universitaire:
1ère année master ASD 2021/2022
Introduction
Méthode naïve Méthode par séparation et
évaluation
Consiste à énumérer toutes les Permets d’éviter les solutions dont on
solutions possibles pour calculer le cout sait qu’elles sont mauvaises
Inefficace pour les problèmes NP- très utilisée afin de
complets. résoudre des problèmes NP-complets
02/06/2022 2
Introduction
Etat du problème
Lors du processus de résolution, le problème transite
d’un état vers un autre.
On distingue:
- L’état initial
- Un ou plusieurs états finaux
02/06/2022 3
Introduction
Opérateurs
Un opérateur transforme un état en un autre état.
- L’application des opérateurs sur les états en
démarrant de l’état initial conduit à la construction
d’une arborescence
02/06/2022 4
Introduction
La racine correspond à la configuration initiale
Un nœud représente une configuration quelconque
Un arc correspond à l’application d’un opérateur
02/06/2022 5
Les stratégies de développement
Stratégies
Profondeur Largeur Coût
d’abord d’abord uniforme
02/06/2022 6
Profondeur d’abord
pour chaque nœud, on prend le
premier fils jusqu'à ce qu’un
nœud n'ait plus de fils actif,
auquel cas on remonte alors au
nœud père et on emprunte une
autre direction (s’il en reste)
02/06/2022 7
Algorithme de recherche en profondeur
1. Insérer le nœud initial s dans la liste OPEN
2. Si OPEN est vide alors échec sinon continuer
3. Retirer le premier nœud de OPEN et l’insérer dans
une liste appelée CLOSED. Soit n ce nœud.
4. Si la profondeur de l’arbre est égale au seuil de
profondeur aller à 2 sinon continuer
5. Engendrer les successeurs de n et les empiler dans
OPEN. Créer un chaînage de ces nœuds vers n
6. Si parmi les successeurs, il existe un état final
alors succès: la solution est obtenue en suivant le
chaînage arrière de ce nœud vers la racine, sinon aller à
2
02/06/2022 8
Largeur d’abord
à partir d'un nœud
source, on liste d'abord
tous ses fils pour ensuite
les explorer un par un.
02/06/2022 9
Un algorithme de recherche en
largeur d’abord
1) Insérer le nœud initial s dans une liste appelée
OPEN
2) Si OPEN est vide alors échec sinon continuer
3) Retirer le premier nœud de OPEN et l’insérer dans
une liste appelée CLOSED. Soit n ce nœud.
4) S’il n’existe pas de successeur alors aller à 2.
Engendrer les successeurs de n et les insérer à la queue
de OPEN. Créer un chaînage de ces nœuds vers n
5) Si parmi les successeurs, il existe un état final
alors succès: la solution est obtenue en suivant le
chaînage arrière de ce nœud vers la racine, sinon aller à
2
02/06/2022 10
Coût uniforme
à chaque étape on explore
le nœud qui minimise la
fonction de coût, i.e. celui
qui détient le plus petit
coût
02/06/2022 11
Méthode de coût uniforme
une version plus générale de la recherche en largeur
d’abord
Soient:
◦ c(ni,nj) le coût de l’arc reliant ni à son successeur
nj
◦ g(n) le coût minimal de la chaîne allant de s à n
◦ La méthode garantit le calcul de la chaîne de coût
minimal
02/06/2022 12
Algorithme du coût uniforme
1. Insérer s dans une liste appelée OPEN. Soit g(s)=0
2. Si OPEN est vide alors échec sinon continuer
3. Retirer de OPEN, le nœud qui a la plus petite
valeur g et l’insérer dans CLOSED. Soit n ce
nœud. En cas de conflit, choisir arbitrairement n.
4. Si n est un état final alors succès sinon continuer
5. Engendrer les successeurs de n. S’il n’existe pas
de successeur aller à 2 sinon calculer et insérer
dans OPEN pour chaque successeur ni,
g(ni)=g(n)+c(n,ni). Etablir le chaînage arrière.
6. Aller à 2
02/06/2022 13
Exemple : Le problème des N reines
Le problème des N reines consiste à placer N reines
sur un chéquier de taille N * N, de telle sorte qu’aucune
ne soit en prise. Il ne faut donc pas plus d’une reine par
ligne, par colonne et par diagonale.
02/06/2022 14
Une solution au problème pour N=
6:
R1
R2
R3
R4
R5
R6
02/06/2022 15
Le problème des N reines
Le problème des N reines consiste à placer des reines
de telle sorte qu’aucune ne soit menacée.
Puisque chaque ligne doit contenir une seule reine,
pour faciliter l’accès aux informations sur les reines, la
reine numéro i est insérée à la ligne numéro i.
Donc, il reste à sauvegarder l’information sur la
colonne de la reine.
02/06/2022 16
Largeur d’abord
R1=1 R1=2 R1=3
R1=4 R1=5 R1=6
02/06/2022 17
Largeur d’abord
R1=1 R1=2 R1=3
R1=4 R1=5 R1=6
R2=3 R2=4 R2=5 R2=6
02/06/2022 18
Profondeur d’abord
R1=2
02/06/2022 19
Profondeur d’abord
R1=1
R2=3
02/06/2022 20
Profondeur d’abord
R1=1
R2=3
R3=5
02/06/2022 21
