CHAPITRE 9 EXPLORATION DE GRAPHESbherer/Transparents_Ch09.pdfAnalyse d’Algorithmes 2001 Ch. 9 - EXPLORATION DE GRAPHES 3 EXEMPLE 1: JEU DE NIM Règles du jeu A) Au départ, le premier

Analyse d’Algorithmes 2001 Ch. 9 - EXPLORATION DE GRAPHES 1

CHAPITRE 9EXPLORATION DE GRAPHES

Les sections indiquées sont celles du nouveau livreLes numéros de pages de ces transparents sont indiqués à droite

1 . INTRODUCTION 2

Exemple des graphes de jeux 3

2. EXPLORATION D’ARBORESCENCES 7

3. FOUILLE EN PROFONDEUR:GRAPHES NON ORIENTÉS 8

3.1 Points d’articulation 1 0

4. FOUILLE EN PROFONDEUR:GRAPHES ORIENTÉS 14

4.1 Graphes sans circuit: tri topologique 1 6

4.2 Composantes fortement connexes 1 9

5. FOUILLE EN LARGEUR 22

6. ALGORITHMES À RETOUR ARRIÈRE 24

7. ALGORITHME DE “BRANCH AND BOUND” 31

2 Ch. 9 - EXPLORATION DE GRAPHES ©2001 R. Lelouche

1. INTRODUCTION

Position d’un problème en termes de graphes

• Plusieurs problèmes peuvent être posés en termes de graphes.• Les algorithmes présentés jusqu’à maintenant imposent implicitement un

ordre de visite du graphe.• Dans certaines applications, aucun ordre de visite n’est imposé.

Graphe ? Deux sens différents, techniques identiques

• 1º Structures de données concrètes implantées en machine.• 2º Abstraction de raisonnement, non manipulable dans son ensemble.• Opérations communes: marquer un sommet, trouver un sommet adjacent.• Les techniques de parcours présentées ici s’appliquent aux deux cas;

seules les implantations diffèrent.

Exemple 1Un vacancier arrive dans un pays étranger pour en visiter les principalesvilles. Une fois ces villes identifiées, tout en ayant en sa possession unecarte du système routier de ce pays, il veut donc :

«Décrire un algorithme permettant de visiter ces villes.»

Exemple 2Le tour du cavalier aux échecs (chemin hamiltonien).Noter que le graphe à considérer n’est pas “tout à fait” l’échiquier!

Exemple 3 (graphe abstrait)Succession des coups au jeu d’échecs(les sommets sont les positions globales, et les arcs les coups légaux).

But du chapitre

Suggérer des techniques d’exploration de graphes.Les analyser.


EXEMPLE 1: JEU DE NIM

Règles du jeu

A) Au départ, le premier joueur enlève autant d’allumettes qu’il le désire,mais il doit en enlever au moins une et en laisser au moins une (il y a doncau départ au moins 2 allumettes dans le jeu).

B) Par la suite, chaque joueur enlève au moins une allumette, et au plus ledouble du nombre d’allumettes enlevées lors du coup précédent.

C) Le joueur qui enlève la dernière allumette gagne la partie.

Considérons un graphe correspondant à ce jeu, où chaque nœud estreprésenté par un couple <i, j>, signifiant qu’il reste i allumettes dans le jeu etqu’il est permis d’en enlever un nombre quelconque entre 1 et j (j ≤ i). Uncoup légal est alors:

<i, j> → <i–k, min (2k, i–k)> k ∈ 1, 2, ..., jet la racine (position de départ) est <n, n–1> pour n allumettes au départ.

Algorithme pour déterminer si une position est gagnanteFONCTION GagnantRecursif (i, j) : booléen

i = Nb pièces total, j = Nb max pièces otables, 0 ≤ j ≤ iRetourne vrai ssi <i, j> est gagnantePOUR k ← 1 à j FAIRE k = Nb pièces otées

SI ¬ GagnantRecursif (i–k, min (2k, i–k)) ALORSla position <i–k, •> est perdanteRETOURNER vrai.

Assert: tous les successeurs de <i, j> sont gagnantsRETOURNER faux.FIN.

5,4

2,2

4,2

3,3

0,0 4,3

1,1 2,1

3,2position

gagnante

positionperdante

À partir d’une configuration gagnante, il suffit d’emprunter un arc gras pourgagner.


EXEMPLE 1: JEU DE NIM (suite)

L’algorithme précédent est inefficaceparce qu’il recalcule plusieurs fois les mêmes valeurs.

Levée de l’inefficacité: programmation dynamiqueDe manière ascendante, on remplit un tableau G[i, j] pour indiquer si laposition <i, j> est gagnante (G[i, j] = VRAI) ou non (G[i, j] = FAUX).PROCEDURE GagnantDynamique (n).

Pour tout 1 ≤ j ≤ i ≤ n, met G[i, j] à VRAI ssi la position <i, j> est gagnanteG[0,0] ← FAUX.POUR i ← 1 à n FAIRE i = Nb pièces au total

POUR j ← 1 à i FAIRE j = Nb pièces ôtablesk ← 1. k = Nb pièces ôtéesTANT QUE k < j ET G (i–k, min (2k, i–k)) FAIRE

k ← k + 1.G[i, j] ← NON G (i–k, min (2k, i–k)).FIN POUR.

FIN POUR.FIN GagnantDynamique.

Programmation dynamique inefficace!

Calcule des valeurs inutiles!

Par exemple, on sait que <15, 14> est gagnante dès que l’on sait que sonsuccesseur <13, 4> est une position perdante. Dès lors, on se moque desavoir si le successeur suivant <12, 6> est gagnant ou perdant...

Dans le calcul de G[15, 14], seuls 28 nœuds sont vraiment utiles, mais laprogrammation dynamique en calcule 121. Autres exemples dans le livre.

Levée de l’inefficacité: fonction à mémoire

Combiner les avantages des deux algorithmes: le récursif ne calcule que desvaleurs utiles; le dynamique ne calcule jamais deux fois la même chose!Donc: se rappeler quels nœuds ont déjà été calculés lors du calcul récursif enutilisant un tableau booléen global Connu [0 .. n; 0 .. n] (n borne supérieure dunombre d’alumettes utilisables) initialisé à FAUX (sauf Connu [0, 0] = VRAI).

L’algorithme récursif devient:FONCTION Gagnant (i, j) : booléen.

Retourne vrai ssi <i, j> est gagnante, pour tout 1 ≤ j ≤ i ≤ n

Pour les détails, voir livre p. 289


GÉNÉRALISATION AUX AUTRES GRAPHES DE JEU

Plusieurs jeux de stratégie peuvent se représenter sous forme de graphesorientés:- un nœud correspond à une configuration possible du jeu ;- un arc correspond à une transition légale entre 2 configurations.

Hypothèses communes

a) Le jeu se joue en alternance entre 2 joueurs.

b) Les 2 joueurs sont soumis aux mêmes règles (jeu symétrique).

c) Le hasard n’intervient pas (jeu déterministe).

d) Chaque partie dure un temps fini, et aucune configuration (nœud) nepossède un nombre infini de successeurs possibles.

e) Les configurations terminales sont les nœuds du graphe n’ayant pas desuccesseur.

Approche

Déterminer une stratégie gagnante en attribuant à chaque nœud uneétiquette choisie parmi gagnante, perdante, nulle, correspondant à lasituation d’un joueur placé devant cette configuration, et respectant les règlessuivantes:

- la valeur de l’étiquette (gagnante, perdante, ou nulle) d’une configurationterminale est immédiate (elle dépend du jeu spécifique);

- une configuration non terminale est “gagnante” si au moins un de sessuccesseurs est perdant;

- une configuration non terminale est “perdante” si tous ses successeurssont gagnants;

- dans tous les autres cas, une configuration non terminale est nulle (lessuccesseurs incluent au moins une position “nulle”).


EXEMPLE 2: LES ÉCHECS

• Chaque nœud du graphe représentant le jeu d’échecs désigne uneconfiguration:

• position des pièces,

• quels rois et tours ont bougé depuis le début de la partie,

• quel pion vient d’avancer de 2 pas,

• etc.

• Chaque nœud est étiqueté comme suit:

a) configuration gagnante pour les Blancs,

b) configuration gagnante pour les Noirs,

c) nulle.

UNE FOUILLE COMPLÈTE DU GRAPHEEST IMPENSABLE

Plusieurs heuristiques ont été proposées pour jouer un “bon” coup.

⇒ Intelligence artificielle


2. EXPLORATION D’ARBORESCENCES

Techniques d’exploration

• 3 techniques sont souvent utilisées pour visiter une arborescence binaire:

Visites à effectuer Techniques possibles

R: visiter la Racine en Pré-ordre: R , G, DG: visiter le sous-arbre de Gauche en Ordre: G, R, DD: visiter le sous-arbre de Droite en Post-ordre: G, D, R

(le préfixe indique où est visitée la racine par rapport à ses deux branches)

• On peut utiliser les mêmes techniques pour balayer de droite à gauche(exercice: chercher les liens entre les six techniques d’exploration).

Résultats d’analyse

• Le temps d’exploration d’une arborescence de n nœuds est dans Θ(n).

Démonstration: par récurrence sur n.

• Une implantation récursive exige un espace dans Ω(n).

Démonstration: problème 9.10.

• Il est possible de ramener cette exigence d’espace à Θ(1).

Démonstration: *problème 9.11.

Ces techniques d’exploration peuvent être généraliséesà des arborescences quelconques.


3. FOUILLE EN PROFONDEUR:GRAPHES NON ORIENTÉS

Il s’agit d’explorer (pour les traiter) tous les nœuds d’un graphe (pas un arbreen général). Cependant, la fouille s’effectue comme s’il s’agissait d’un arbre.

Un sommet est marqué pour indiquer s’il a déjà été visité.

Programme principalInitialisations

POUR chaque sommet v dans N FAIRE

Visité [v] ← fauxExploration et traitement

POUR chaque sommet v dans N FAIRE

SI NON Visité [v] ALORS FEP (v) Fouille en Profondeur et traitementFin.

PROCÉDURE FEP (v : sommet)Visité [v] ← VRAI

POUR chaque sommet w dans Adjacent [v] FAIRE

SI NON Visité [w] ALORS FEP (w).FIN FEP.

Analyse

Soient n le nombre de sommets et a le nombre d’arêtes de G=<N, A>

Appels de procédure: O(n)

Inspection des marques: O(a) si liste d'adjacenceouO(n) si matrice d'incidence


3. Fouille en profondeur (suite)

Exemple

7

98

1 2

4

3

5

6

2 composantes connexes

Ordre d’exploration: 1, 2, 4, 3, 6, 5 puis 7, 8, 9

Cet algorithme associe au graphe exploré une arborescence sous-tendanteà ce graphe (arbre recouvrant ce graphe).

12

4

36

5

7

89


3.1 Points d’articulation

Point d’articulation

Définition: Un sommet v d’un graphe connexe tel que le sous-grapheobtenu en supprimant v et toutes les arêtes incidentes à v n’est plus connexe.

Exemple: le sommet 1. (Est-ce le seul ?)

1

2 3

5 6

4

7 8

Graphe biconnexe ou inarticulé

Définition: Graphe connexe qui ne possède pas de point d’articulation.

Graphe bicohérent

Définition: Graphe connexe où chaque point d’articulation est relié par aumoins 2 arêtes à chacune des composantes du sous-graphe restant.

Le graphe précédent n’est pas bicohérent au sommet 1 : il faudrait unedeuxième arête du sommet 1 vers la composante (4, 7, 8).

Intérêt de ces notions et exemple

Un réseau d’ordinateurs bi-connexe peut continuer à fonctionner même si undes nœuds de calculs est en panne; s’il est bicohérent, tous les nœuds decalculs pourront communiquer entre eux même si une ligne fait défaut.


3.1 Recherche des points d’articulationLorsqu’on effectue une fouille en profondeur, le graphe ci-dessous contienttoutes les arêtes du graphe initial: les arcs gras forment un arbre recouvrant,tandis que les autres sont représentés en grisé.

De plus, ces derniers vont nécessairement d’un nœud à un de ses ancêtres.(Pourquoi ?)

3

6

5

8

3

4

5

8

22

1

1

2

2

46 6

77

6

6

Ordre de visite en pré-ordre(vecteur PréNum)

Vecteur PPH(PréNum du Plus Haut)

arcs de T

arêtes de A–T

11

18

4

3

2

1

7

6

5

Ordre de visite de T en post-ordre

À gauche de chaque nœud v et en gras est indiqué PréNum [ v], traduisantl’ordre de sa visite dans un exploration du graphe en pré-ordre.

À droite de chaque nœud est indiqué PPH [v] défini ainsi: soit w le nœud leplus haut dans T tel que on peut atteindre w à partir de v en descendantautant de lignes continues (arcs de T) qu’on veut et en remontant au plus uneligne grisée (arête de A–T). Alors :

PPH [v] = PréNum du Plus Haut nœud atteignable à partir de v = PréNum [w].

Ainsi: PPH [7] = PréNum [4] = 6, PPH [6] = PPH [5] = PréNum [2] = 2.


3.1 Recherche des points d’articulation (suite)

Étude de PPH

• Le plus haut nœud w atteignable de cette manière est nécessairement unancêtre de v. Le plus haut w est donc celui qui minimise PréNum.

• Soit un nœud v autre que la racine, et supposons que v n’a pas de fils.Alors ce n’est pas un point d’articulation de G (évident).

• Soit v un nœud autre que la racine, et soit x un fils de v.- Supposons que PPH [x] < PréNum [v]. Alors il existe une chaîne d’arêtes

qui lie x aux autres sommets du graphe, même si v est supprimé. (cas dunœud 3 de la figure). Donc, si cela est vrai pour tous les fils x de v, v n’estpas un point d’articulation.

- Si, pour au moins un fils x de v, PPH [x] ≥ PréNum [v], alors il n'existe pasde chaîne pour relier x au père de v (cas du nœud 4 de la figure). Donc vest un point d’articulation.

• Si v est la racine, c’est un point d’articulation si et seulement si v a au moins2 fils (dans ce cas la déconnexion de la racine sépare ses sous-arbres).

Algorithmea) Effectuer une fouille en profondeur dans G. Soient

• T l’arborescence engendrée par la fouille,• PréNum [v] ≡ le numéro attribué par la fouille au sommet v de G.

Cette numérotation désigne le pré-ordre comme ordre de visite de T

b) Parcourir l’arborescence T en post-ordre.Au moment de la visite de chaque nœud v,

calculer PPH [v] (le PréNum du Plus Haut) comme le minimum de:• PréNum [v],• PréNum [w] pour tout sommet w tel que ∃ v, w ∈ A–T,• PPH [x] pout tout sommet x qui est un fils de v (dans T).

c) Déterminer les points d’articulation de G comme suit:i) la racine de T est un point d’articulation de G

⇔ elle possède plus d’un fils.ii) un sommet v autre que la racine de T est un point d’articulation de G

⇔ v a un fils x tel que PPH [x] ≥ PréNum [v] .


3.1 Recherche des points d’articulation (fin)

Exemple de parcours avec un autre point de départ

12

2

6

5

4

7

8

3

4

5

6

7

8

1

1

1

6

6

6

31

1

11

2

3

4

5

6

7

8

Le sommet 3 ( racine) possède 1 seul fils⇒ 3 n'est pas un point d'articulation.

Le sommet 1 est un point d'articulation carPPH [4] ≥ PréNum [1].

Le sommet 4 est un point d'articulation carPPH [7] ≥ PréNum [4].


4. FOUILLE EN PROFONDEUR:GRAPHES ORIENTÉS

L’algorithme est identique; seule l’interprétation du terme “adjacent” estdifférente:

w est adjacent à v ⇔ l’arc (v, w) existe.

Exemple

1

4

765 8

32

Ordre de visite: 1, 2, 3, 4, 8, 7;

puis: 5, 6.

4

83

2

1

5

6

7

O(Max (a, n)).


Fouille en profondeur graphes orientés (suite)

Soit F l’ensemble des arcs de la forêt. Il existe 3 sortes d’arcs dans A–F:

4

83

2

1

5

6

7

(i) (3,1) et (7,4)un sommet vers l’un de ses ancêtres

(ii) (1,8)un sommet vers l’un de ses descendants

(iii) (5,2), (6,3)arcs appartenant à des arborescences différentes et ils sont orientés dela droite vers la gauche.

Remarque

Dans le cas d’un graphe non orienté, seul le type (i) (ou (ii)) existe.

Exercice (problème 6.4.2)

Prouvez que si (v, w) ∈ G–T et si (v, w) est de type (iii), alorsPréNum [v] > PréNum [w]

(les numéros PréNum étant affectés comme dans la section 3 par laconstruction de la fouille en profondeur)


4.1 Graphes sans circuit : tri topologique

Exemples de représentation de relationsà l’aide de graphes orientés sans circuit

A) une expression arithmétique

a (a / (a+b+c)) - (a / (a+b+c)) ((a+b+c) + d) (c / d)

–

* *

/ + /

+

a b c d

b) la relation «plus petit» définie sur les entiers

2

41

3


4.1 Tri topologique (suite)

Exemples de représentation de relationsà l’aide de graphes orientés sans circuit

c) Représentation des étapes d’un projet

- un sommet représente un état du projet,

- un arc correspond à l’activité permettant de passer d’un état à un autre.

A

se rendre à une brasserie

commander des bières

recevoirla commande

sortir son argent

boire les bièrespayer

les bières

donnerun pourboire

Sortir de la brasserietant bien que mal

B C

D

G EF

Problème 9.26

Soit F la forêt associée à une fouille en profondeursur un graphe orienté G = <N,A>.

G est sans circuit ⇔ A–F n’inclut aucun arc de type (i).


TRI TOPOLOGIQUE DES SOMMETSD’UN GRAPHE ORIENTÉ SANS CIRCUIT

Définition∀ (i, j) ∈ A, i précède j dans la liste.

Exemple (fig. 9.9)

C

EB

F

A D Gse lever

se réveillerchoisir cravate

se doucher

faire café boire café

s'habiller

prendre documents

sortir

Ordres possibles:A B C F E D GA F B C E D G

........

PROCÉDURE FEP (v : sommet)Marque [v] ← visitéPOUR chaque sommet w adjacent à v FAIRE

SI Marque [w] ≠ visité ALORS FEP (w)Écrire v.

Les sommets sont écrits dans un ordre topologique inverséExercice: prouvez-le! ou voyez le livre p. 301-302.

Ordre d’écriture pour le premier ordre indiquédans l’exemple précédent:G D E F C B A

Si les sommets sont examonés dans l’ordre alphabétique des nœuds(faites-le!), on obtient l’ordre d’écriture: G D C E B F A


4.2 Composantes fortement connexes(problème 9.29)

Définitions

• Un graphe orienté est fortement connexe⇔ ∀ u, v ∈ N, ∃ un chemin allant de u à v ET un chemin allant de v à u

• Si un graphe orienté n’est pas fortement connexe, il s’agit de déterminerchaque composante fortement connexe (de taille maximale) du grapheoriginal.

Exemple

A

C E

D

B

A

C E

D

B

2 COMPOSANTES FORTEMENT CONNEXES.


RECHERCHE DES COMPOSANTES FORTEMENT CONNEXESD’UN GRAPHE ORIENTÉ G (suite)

Remarque préliminaireDans les fouilles en profondeur que nous allons effectuer, la numérotationdes sommets est faite en post-ordre.

PROCÉDURE FEP (v : sommet)Marque [v] ← visitéPOUR chaque sommet w adjacent à v FAIRE

SI Marque [w] ≠ visité ALORS FEP (w)NumP ← NumP + 1PostNum [v] ← NumP.

NumP est une variable globale (Numérotation en Post-ordre) initialisée à 0

Algorithme

i) Effectuer une fouille en profondeur dans le graphe G à partir d’unsommet quelconque.

ii) Construire un graphe G’, à partir de G, en inversant simplementl’orientation des arcs.

iii) Effectuer une fouille en profondeur dans G’ en commençant toujours unefouille par le sommet w ayant la plus grande valeur de PostNum, enautant qu’il n’a pas été visité.

iv) Chaque arborescence dans la forêt résultante est une composantefortement connexe de G.

Analyse

i) ii) iii)O (Max (a, n)) + O (a) + O (Max (a, n)) ≡ O (Max (a, n))


RECHERCHE DES COMPOSANTES FORTEMENT CONNEXESD’UN GRAPHE ORIENTÉ G (suite)

Exemple (graphe de la page 19)

1er point de départ: le sommetpour lequel PostNum est maximum,

puis fouille en profondeur

2ième point de départ => 2me composante

Début de la fouille

valeurs du vecteur PostNum

=> 1 arborescence

Graphe G

A

C E

D

B

5

4

3 2

1

A

C E

D

B

5

4

3 2

1

A

C E

D

B

Graphe G’

=> 2 composantesfortement connexes

A

C E

D

B

5

4

3 2

1


5. FOUILLE EN LARGEUR

Fouille en profondeur: visite v, un voisin de v, un voisin de ce voisin, etc.Fouille en largeur: visite v, les voisins immédiats de v, les 2mes voisins de v,

etc. (n'est pas naturellement récursif).

Reformulation itérative de l’algorithme de fouille en profondeur

Un type Pile est défini, permettant 2 opérations, Empiler et Dépiler ;la fonction Haut désigne l’élément en haut de la pile

PROCÉDURE FEP’ (v : sommet).P ← Pile vide.Marque [v] ← visité.Empiler v sur P.TANT QUE P n’est pas vide FAIRE

TANT QUE il existe un sommet w adjacent à Haut (P)tel que Marque [w] ≠ visité FAIRE

Marque [w] ← visitéEmpiler w sur P w est maintenant Haut (P).

Dépiler Haut (P).

Algorithme itératif de fouille en largeur

Un type File est défini avec 2 opérations: Mettre en file et Sortir de la file ;la fonction Premier désigne le 1er élément de la file(le prochain à sortir)

PROCÉDURE FEL (v : sommet).Q ← File vide.Marque [v] ← visité.Mettre v dans Q.TANT QUE Q n’est pas vide FAIRE

u ← Premier (Q).Sortir u de la file Q.POUR chaque sommet w adjacent à u FAIRE

SI Marque [w] ≠ visité ALORSMarque [w] ← visité ; Mettre w dans Q.

Programme principal

∀ v ∈ N FAIRE Marque[v] ← non visité.∀ v ∈ N FAIRE

SI Marque [v] ≠ visité ALORS Fouille (v) FEP’ ou FEL selon le cas

Efficacité: O (Max (a, n))


Exemple de fouille en largeur

Celle-ci peut se faire: soit avec un graphe non orienté (voir livre),soit avec un graphe orienté (cas ici, pb 9.31)

1

4

765 8

32

1

4

765 8

32

États successifs de la file (les lire de gauche à droite et de bas en haut):

8 3 puis4 8 3 7 (parce qu’il reste des

1 2 4 8 3 7 sommets non visités) 5 6

Pb. 9.32: Sortes d’arcs pointillés (extérieurs à l'arbor. de fouille)Type i = un sommet vers l’un de ses ancêtres : (3, 1), (6, 5).Type iii =

- les sommets peuvent appartenir à des arborescences de fouilledifférentes : (5, 2), (6, 2), (6, 3),

- ou, sinon, ni l’une, ni l’autre des extrémités de l’arc n’est undescendant ou un ancêtre dans l’arborescence de fouille : (4,8), (7, 4).


6. ALGORITHMES À RETOUR ARRIÈRE

• Méthode de fouille systématique pour la recherche d’une solution (peutaller jusqu’à la fouille exhaustive).

• Technique d’exploration de graphe orienté.

Exemple 1

Retrouver son chemin dans un labyrinthe en évitant de tourner en rond.

Exemple 2

Placer 8 reines sur un échiquier de telle sorte qu’aucune d’entre elles ne soitprise par une autre.

Stratégie 1: Mettre les reines n'importe où.

(648 ) ≡ 4 426 165 368 cas à examiner

Stratégie 2: Éviter de mettre plus d’une reine sur une même ligne.

88 ≡ 16 777 216 cas à examiner

Nous représentons un échiquier par un vecteur de 8 entiers donnant laposition de chaque reine sur sa ligne.

POUR i1 ← 1 à 8 FAIREPOUR i2 ← 1 à 8 FAIRE

......

POUR i8 ← 1 à 8 FAIREEssai ← (i1, i2, ..., i8)SI Solution (Essai) ALORS

Ecrire Essai ; StopÉcrire “il n’y a pas de solution”.

Stratégie 3: Éviter en outre de mettre deux reines sur une même colonne.

⇒ l’échiquier est représenté par une permutation de (1, 2, ..., 8).

8! ≡ 40 320 cas possibles


6. Algorithmes à retour arrière (suite)

Forme de l’algorithme

Essai ← permutation initiale.TANT QUE non Solution (essai) ET essai ≠ permutation finale FAIRE

Essai ← permutation suivante.SI Solution (essai) ALORS Écrire essai.SINON Essai = permutation finale Écrire “pas de solution”.

Génération des n! permutations des n premiers entiers

Algorithme

PROCÉDURE Perm (i)SI i = n ALORS Traiter (T) T est une nouvelle permutationSINON i < n

POUR j ← i à n FAIREMettre T [j] en tête

Interchanger T[i] et T [j]Générer et traiter toutes les permutations correspondantes

Perm (i+1)Remettre T[j] à la place qu’il avait

Interchanger T[i] et T[j].FIN Perm.

où T[1..n] est initialisé à [1,2,...,n],l’appel initial est Perm (1).

Remarque

Traiter (T) peut désigner : «SI Solution (T) ALORS Stop».



Ex.: Trace de l’exécution pour n = 4 (pb. 9.45 anc. 6.6.3) *

j = 2 T = [2, 1, 3, 4]

j = 3 T = [3, 2, 1, 4]

j = 4 T = [4, 2, 3, 1]

Perm(1)

T = [1, 2, 3, 4]j = 1 T = [1, 2, 3, 4]

Perm(2)

j = 2 T = [1, 2, 3, 4] j = 3 T = [1, 2, 3, 4]

j = 4 T = [1, 2, 3, 4]

Perm(3)

Perm(4)

j = 4 T = [1, 2, 4, 3]

j = 4 T = [1, 2, 4, 3]

Perm(4)

j = 3 T = [1, 3, 2, 4] j = 3 T = [1, 3, 2, 4]

j = 4 T = [1, 3, 2, 4]

Perm(3)

Perm(4)

j = 4 T = [1, 3, 4, 2]

j = 4 T = [1, 3, 4, 2]

Perm(4)

j = 4 T = [1, 4, 3, 2] j = 3 T = [1, 4, 3, 2]

j = 4 T = [1, 4, 3, 2]

Perm(3)

Perm(4)

j = 4 T = [1, 4, 2, 3]

j = 4 T = [1, 4, 2, 3]

Perm(4)

Les flèches indiquentles valeurs du vecteur T

qui sont utilisées dans les appels de Perm

* Merci à Lydia Bell, étudiante à la session A-2000, qui nous a fourni cette représentation très claire.



Exercice

Pour montrer que Perm (1) génère toutes les permutations, montrons que:

Perm (i) génère toutes les permutations possibles des n–i+1dernierséléments (positions i, i+1, ..., n), en de la manière suivante:

• toutes les permutations commençant par l’un quelconque de ces élémentssont générées de manière consécutive,

• T est dans la configuration initiale à la fin de chacun de ces groupes.

Preuve

Procédons par induction sur i, en allant “à l’envers” de n à 1.

Base de l’induction: Perm (n). Trivial (T n’est pas modifié du tout).

Boucle d’induction: Perm (i) avec i < n.

Supposons que chaque appel à Perm (k), k = i+1, ..., n :• (H1) génère toutes les permutations des positions k, k+1, ..., n,• (H2) laisse T inchangé.Examinons alors le comportement de Perm (i).

Le corps de boucle de l’algorithme Perm se compose de trois instructions:I1 (échange initial T[i] ↔ T[j]), I2 (appel à Perm (i+1)), et I3 (échange final).

Chaque exécution de I2 génère toutes les permutations possibles deséléments en positions i+1, ..., n (d’après H1), donc toutes les permutationsdes positions i, i+1, ..., n commençant par une même valeur en position i.

D’après H2, chaque exécution de I2 laisse T inchangé. L’état de T après I2est donc le même que l’état de T après I1, donc le même que si I2 n’existaitpas. Ainsi, I3 a pour effet de remettre T dans l’état où il était avant exécutionde I1, c’est-à-dire dans l’état où il était au moment de l’entrée dans le corpsde boucle. Cet état est donc un invariant de cette boucle, ce qui montre que:

• l’élément en position i est successivement chacun des éléments del’ensemble T[i], T[i+1], ..., T[n]; donc toutes les permutations des positionsi, i+1, ..., n sont générées, ce qui prouve H1 pour i;

• l’état de T à la fin du dernier tour de boucle (j=n), donc à la sortie dePerm(i), est le même que l’état de T avant le premier tour de boucle (j=i),suite à l’entrée dans Perm(i), ce qui prouve H2 pour i.



Analyse de l’appel «Perm (1)» (problème 9.46)

Hypothèse: temps de Traiter (T) ∈ Θ (1)

Soit t(k) le temps pris pour un appel à Perm (n–k+1).

t (k) = a s i k = 1

∑j=n–k+1

n

[2b + t(k–1)] sinon ( b est le tempsde la permutation)

ou encore (en développant les t(k–1) puis en les éliminant):

t (k) = a s i k = 1

( k ! ) a + 2b ∑j=1

k–1

k!(k–j)! sinon

d'où (en majorant k!(k–j)! par k!):

t(n) ∈ O (a (n!) + 2b (n+1)!)

Hypothèse: temps de Traiter (T) ∈ Θ(n)

Le terme a (n!) devient a n (n!) ≅ a ((n+1)!), d’où:

t(n) ∈ O ((a+2b) (n+1)!)

Remarques pour le problème des 8 reines

a) La génération des permutations (stratégie 3) est plus difficile que celle descombinaisons avec répétition des entiers de 1 à 8 (stratégie 2)

mais

la vérification qu’un essai est une solution est plus facile dans le 1er cas.

b) Un défaut majeur de cette approche:

La vérification d’un essai (= une permutation) se fait seulement lorsqu’il estcomplètement constitué.


6. Algorithmes à retour arrière (suite)Stratégie 4 à retour arrière

Principe général

Utiliser l’idée d’une solution partielle prometteuse, c’est-à-dire satisfaisanttoutes les conditions imposées à la solution finale, sauf celle concernant lenombre de reines. On étendra donc une solution partielle prometteuse à uneautre ayant une reine de plus, si c’est possible.

Formalisation de cette approche

Soit V [1..k] un vecteur d’entiers entre 1 et 8.

V est k-prometteur (pour 0 ≤ k ≤ 8) ⇔ aucune des k reines placées enpositions (1, V [1]), (2, V [2]), ..., (k, V [k]) n’est en prise par une autre.

Soit G = <N, A> oùN est l’ensemble des vecteurs k-prometteurs (0 ≤ k ≤ 8),(U,V) ∈ A ⇔ • U est k-prometteur

• V est (k+1)-prometteur• U [i] = V [i] ∀ i = 1,2,...,k.

G est une arborescence; sa racine est le vecteur vide k = 0;ses feuilles sont soit des solutions (k=8), soit des culs-de-sac (k<8).Par conséquent, il s’agit d’explorer l’arborescence G en profondeur.

Notes.

a) #N = 2057 (tandis que 8! = 40320)

b) En associant à chaque nœud prometteur les ensembles de colonnes,de diagonales positives, et de diagonales négatives, contrôlées par lesreines en place, il est facile de décider si un vecteur est k-prometteur,sachant qu’il est une extension d’un vecteur (k-1)-prometteur.


6. Algorithmes à retour arrièreStratégie 4 pour le problème des huit reines (suite)

Algorithme

PROCÉDURE Test (k, col, diag45, diag135)SI k = 8 ALORS un vecteur 8-prometteur est solution

Écrire Essai; StopSINON explorons les extensions k-prometteuses à Essai

POUR j ← 1 à 8 FAIRE

SI j ∉ col ET j–k ∉ diag45 ET j+k ∉ diag135 ALORS

Essai [k+1] ← j Essai [1..k+1] est (k+1)-prometteurTest (k+1, col ∪ j, diag45 ∪ j–k, diag135 ∪ j+k).

FIN Test.

Appel initial: Test (0, Ø, Ø, Ø)

1 - k 2 - k 3 - k 8 - k

k ième ligne

k-1 ième ligne

Note: Dans certains cas, une fouille en largeur est préférable, soit parceque le graphe est infini, soit parce que l’application s’y prête mieux(par exemple s’il s’agit de minimiser le nombre de manipulations).


7. ALGORITHME DE “BRANCH AND BOUND ”

Il s’agit d’une technique d’exploration de graphe orienté implicite .

Stratégie

• effectuer une fouille en largeur ou en profondeur tout en calculant àchaque nœud visité une borne sur les valeurs des solutions éventuellessituées plus loin dans le graphe.

• si cette borne est telle qu’aucune solution éventuelle ne peut être meilleurequ’une solution déjà trouvée, on abandonne l’exploration de cette partiedu graphe.

• on peut aussi se servir de cette borne pour sélectionner le candidat ayantle plus de potentiel.


7. ALGORITHME DE “BRANCH AND BOUND”EXEMPLE: PROBLÈME DU COMMIS-VOYAGEUR

Chercher le plus court chemin du sommet 1 en passant par les autressommets une et une seule fois et en revenant à 1.

- Soit une arborescence implicite où les nœuds correspondent à deschemins partiellement spécifiés.

- Les successeurs d’un nœud correspondent aux chemins dont un élémentadditionnel est déterminé.

- À chaque nœud de l’arborescence implicite, on associe une borneinférieure sur la longueur des chemins complets correspondants.

- Si la borne est supérieure à la valeur d’une solution déjà trouvée, il estinutile de poursuivre l’exploration à partir de ce nœud.

Soit la matrice de distances D où D [i, j] est la distance entre les villes i et j.Il s’agit de calculer une borne inférieure sur la longueur des cheminscomplets dont le chemin partiel commun (“p” comme partiel) est:

i1 i2 i3 ... ip–1 ip avec i1 = 1

Borne = trajet partiel i1–i2–i3–...–ip–1–ip (connu)

+ départ de ip vers j, j ∉ i1, i2, ..., ip

+ ∑j∉ i1,i2,...,ip

un passage par j

ne provenant pas de i1, i2, ..., ip–1et n’aboutissant pas à i2, i3, ..., ip–1, ip

+ arrivée à 1 en provenance de j, j ∉ i1, i2, ..., ip

= trajet partiel i1–i2–i3–...–ip–1–ip

+ 12 Min j ∉ i1, i2, ..., ip D [ip, j]

+ 12 Min i ∉ i1, i2, ..., ip–1 D [i, j] + 12 Min k ∉ i2, i3, ..., ip–1, ip D [j, k]

+ 12 Min j ∉ i1, i2, i3, ..., ip D [j, 1]

Ainsi, quels que soient i et j à l’extérieur du chemin déjà connu i1, ..., ip :

coût de départ de i + coût d’arrivée à j

≡ 12 Min k ∉ i2, i3, ..., ip–1, ip D [i, k] + 12 Min k ∉ i1, i2, ..., ip–1 D [k, j]

≤ D [i,j]


7. ALGORITHME DE “BRANCH AND BOUND”PROBLÈME DU COMMIS-VOYAGEUR (suite)

Exemple

1 2

3

10

5

139

156

1Borne 22.5

Coût certain à 1: 0Départ de 1: 5Passage par 2: 5 + 2,5 = 7,5Passage par 3: 4,5 + 3 = 7,5Arrivée à 1: 2,5Total: 22,5

1,2Borne 25

Coût certain 1-2: 10Départ de 2: 4,5Passage par 3: 4,5 + 3 = 7,5Arrivée à 1: 3Total: 25

1,3Borne 33

Coût certain 1-3: 15Départ de 3: 6,5Passage par 2: 6,5 + 2,5 = 9,0Arrivée à 1: 2,5Total: 33

1,2,3Borne 25

Coût certain 1-2-3: 19Départ de 3: 3Arrivée à 1: 3Total: 25

inutilede poursuivre


7. ALGORITHME DE “BRANCH AND BOUND” RESOLUTION DE PROBLEMES

DE PROGRAMMATION EN NOMBRES ENTIERS

Soit à calculer

Min F(X) = ∑i=1

n

ai xi

sujet à Bx = c

où les ai sont des réels, B est une matrice de réels, c un vecteur de réels, et x le vecteur à calculer des booléens xi ∈ 0, 1 (i = 1, 2, ..., n).

NIL Bornes inf. & sup.

x1 = 0 x1 = 1

x– 1 Bornes inf. & sup.

x1 Bornes inf. & sup.

x2 = 0 x2 =

1

etc.

Calcul de la borne inférieure

Quel que soit xi non fixé: ai > 0 ⇒ xi est fixé à 0 ai = 0 ⇒ xi est fixé à 1

Documents

CHAPITRE 9 EXPLORATION DE GRAPHESbherer/Transparents_Ch09.pdfAnalyse d’Algorithmes 2001 Ch. 9 - EXPLORATION DE GRAPHES 3 EXEMPLE 1: JEU DE NIM Règles du jeu A) Au départ, le premier