ProgDynamique

8/3/2019 ProgDynamique

1/168

Algorithmique, graphes etprogrammation dynamique

Notes de Cours

Rapport de Travaux Pratiques

Laurent Canet

Le 2 juillet 2003


2/168

Table des matieres

I IN202 - Algorithmique 6

1 Systeme formel de preuve de programme de OHare 81.1 Regles et axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 Construction de programmes sur invariant . . . . . . . . . . . . . 9

2 Problemes de recherches 112.1 Remarques sur levaluation de complexite dun programme . . . . 112.2 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . 112.3 Recherche sequentielle . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Recherche arriere . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Problemes de tris 163.1 Slowsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.3 Complexite minimum dun algorithme de tri . . . . . . . . . . . . 21

4 Approche diviser pour regner 234.1 Diviser pour regner . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Limites de lapproche diviser pour regner . . . . . . . . . . . . . . 24

5 Complexite des algorithmes 255.1 Expression du temps de calcul . . . . . . . . . . . . . . . . . . . . 255.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.3 Calculs courants dans le calcul des complexites . . . . . . . . . . . 275.4 Un peu de theorie de la complexite . . . . . . . . . . . . . . . . . 27

6 Programmation Dynamique 296.1 Cas concret : fibonnaci . . . . . . . . . . . . . . . . . . . . . . . . 296.2 Exemple : Multiplication de matrices . . . . . . . . . . . . . . . . 306.3 Exemple : Recherche du plus long sous-mot commun a 2 chaines . 33

1


3/168

II IN311 - Programmation dynamique 36

7 Applications de la programmation dynamique 387.1 Un probleme dassortiment . . . . . . . . . . . . . . . . . . . . . . 387.2 Compression dimage . . . . . . . . . . . . . . . . . . . . . . . . . 407.3 Justification de Parapgraphes . . . . . . . . . . . . . . . . . . . . 43

III IN302 - Graphes et algorithmes 45

8 Notions de base 468.1 Premiere definition . . . . . . . . . . . . . . . . . . . . . . . . . . 468.2 Representation en memoire . . . . . . . . . . . . . . . . . . . . . . 478.3 Definitions complementaires . . . . . . . . . . . . . . . . . . . . . 508.4 Chemins, connexite . . . . . . . . . . . . . . . . . . . . . . . . . . 538.5 Representation matricielle . . . . . . . . . . . . . . . . . . . . . . 598.6 Graphe biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

9 Arbre et arborescences 629.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629.2 Exemples et applications . . . . . . . . . . . . . . . . . . . . . . . 649.3 Arbre de poids minimum . . . . . . . . . . . . . . . . . . . . . . . 679.4 Algorithmes de Kruskal . . . . . . . . . . . . . . . . . . . . . . 69

10 Plus courts chemins 7110.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7110.2 Problematique du plus court chemin . . . . . . . . . . . . . . . . 7210.3 Algorithme de Floyd . . . . . . . . . . . . . . . . . . . . . . . . 7410.4 Algorithme de Bellman . . . . . . . . . . . . . . . . . . . . . . . 7510.5 Algorithme de Dikstra . . . . . . . . . . . . . . . . . . . . . . . 7810.6 Plus courts chemins (Exploration largeur) . . . . . . . . . . . . . 8010.7 Graphes sans circuits : GSC . . . . . . . . . . . . . . . . . . . . . 81

11 Cycles euleriens et hamiltoniens 8611.1 Cycle eulerien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

11.2 Cycle hamiltonien . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

12 Flots et reseaux de transport 8812.1 Modelisation dun reseau de transport . . . . . . . . . . . . . . . 8812.2 Proprietes dun reseau de transport . . . . . . . . . . . . . . . . . 8912.3 Algorithme de Ford et Fulkerson . . . . . . . . . . . . . . . . 90

2


4/168

13 Resolutions de problemes en Intelligence artificielle et optimisa-tion 9413.1 Exemple : le probleme des 8 dames . . . . . . . . . . . . . . . . . 9413.2 Strategies de recherche . . . . . . . . . . . . . . . . . . . . . . . . 9513.3 Algorithme A et A . . . . . . . . . . . . . . . . . . . . . . . . . . 97

IV Annexes 99

A TP1 - Tri par tas 100A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100A.2 Equations Booleennes . . . . . . . . . . . . . . . . . . . . . . . . . 100A.3 Tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

A.4 Comparaison avec dautres algorithmes de tri . . . . . . . . . . . 106B TP2 - Arbres de recherche optimaux 110

B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110B.2 Preliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111B.3 Recherche dans un arbre . . . . . . . . . . . . . . . . . . . . . . . 112B.4 Arbre binaire de recherche optimal . . . . . . . . . . . . . . . . . 114B.5 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

C TP3 - Sommes de sous-ensembles 130C.1 Premier algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 130

C.2 Deuxieme algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 131C.3 Optimisation & parallelisation . . . . . . . . . . . . . . . . . . . . 135C.4 Code source commente . . . . . . . . . . . . . . . . . . . . . . . . 137

D TP IN311 : le sac a ados 141D.1 Position du probleme . . . . . . . . . . . . . . . . . . . . . . . . . 141D.2 Equation du recurrence . . . . . . . . . . . . . . . . . . . . . . . . 141D.3 Complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142D.4 Reconstruction de la solution . . . . . . . . . . . . . . . . . . . . 142D.5 Exemples dexecution . . . . . . . . . . . . . . . . . . . . . . . . . 142D.6 Programme complet et commente . . . . . . . . . . . . . . . . . . 144

E Corrections de TD IN302 147E.1 TD 1 : Recherche de circuits . . . . . . . . . . . . . . . . . . . . . 147E.2 Le probleme de laffectation . . . . . . . . . . . . . . . . . . . . . 149E.3 Le probleme de la carte routiere . . . . . . . . . . . . . . . . . . . 150E.4 Le probleme du voyageur de commerce . . . . . . . . . . . . . . . 150

F Graphes TP 2 - Analyse de trajectoires dans une chambre abulle 151

3


5/168

G Graphes TP 3 - Ballades dans le metro 158

4


6/168

Introduction

Ce texte na aucune valeur officielle de support pour les cours concernes. Ilcontient vraisemblablement beaucoup derreurs et dinexactitudes, le lecteur sereportera a un ouvrage de reference pour les verifications.

Le rapport de TP de programmation dynamique a ete co-ecrit avec monbinome Thibaut Varene. Les sujets et les rapports de travaux pratiques degraphes ont ete ecrit par Gilles Bertrand et Michel Couprie.

5


7/168

Premiere partie

IN202 - Algorithmique

6


8/168

Introduction au coursdalgorithmique

Ce document fut a lorigine mes notes du cours dIN202 de lESIEE Paris.Cette unite a pour but dinitier les eleves ingenieurs a lalgorithmique grace a des

exemples detaillees. Le cours etait divise en 2 grandes parties, dabord un apercude lalgorithmique ainsi que de la notion de complexite en sappuyant sur desexemples tels que le quicksort, puis une description de lapproche dite de pro-grammation dynamique. Des notions de programmation en C ainsi des connais-sances basiques en analyses sont requises pour comprendre ce cours. Dautresunites du tronc commun ou de la majeure informatique de lESIEE Paris elar-gissent et approfondissent le sujet.

Mes notes de cours datent de mi-2002. Durant lete de cette annee jai enrichile cours notament de la notion de classe de probleme ainsi que des demonstra-

tions, notament la complexite minimale dun algorithme de tri ; finalement jaidecide de les publier sur ma page web.

Ces notes de cours ne constituent en rien un support officiel, il faut impe-rativement se referer a un ou des ouvrages specialises qui seront cites dans unebibliographie (qui na pas encore ete faite).

Je nai en aucun cas la pretention de faire un document interessant, exactou precis. Neanmoins Si vous estimez que je racontre vraiment nimporte quoi,signalez le moi sur mon email : [email protected].

7


9/168

Chapitre 1

Systeme formel de preuve deprogramme de OHare

On peut formaliser un programme en une forme logique dite de bote noire :

ELogique du 1er ordre

PProgramme

SLogique du 1er ordre

De la, plusieurs regles agissent sur ces enonces :

1.1 Regles et axiomes

Regle de la post-condition :

EP S ; S S EP S

Regle de la pre-condition :

EP S ; E E EP S

Regle du ou :

EP S ; EP S (E E)P S

Regle du et :EP S ; EP S EP(S S)

8


10/168

Regle du si-sinon :

(E B)P S ; (E B)QS E {Si B alors P sinon Q} S

Remarque : Levaluation de B ne doit pas modifier E.

Regle du tant-que :

(E B)P E ; E{tant que B faire P}(E B)

Axiomes daffectation :

EP A ; AQS E{P; Q}S

Exemple : Demontrer :

EP S ; EP S (E E)P(S S)

1. EP S

2. EP S

3. E E E

4. (E E)P S (Precondition sur 1 et 3)

5. (E E)P S (Precondition sur 2 et 3)

6. (E E)P(S S) (Regle du ET sur 4 et 5)

7. (S S) (S S)

8. (E E)P(S S) (Postcondition sur 7 et 8)

1.2 Construction de programmes sur invariant

Construire un programme decrit par linvariant, cest utiliser une propositionbooleenne I(x1, x2, , xn), fonction de plusieurs variables xi, qui decrit le pro-bleme a un instant donne. Lorsque lon veut faire un algorithme qui resoud EP Sbase sur un invariant, on doit donner plusieurs propositions :

Invariant : Decrit la position du probleme en fonction de variables xi.

Initialisation : Ce sont des conditions sur les variables xi, tels que la propositionE soit verifie et I(xi) le soit egalement.

9


11/168

Condition darret : Ce sont des conditions sur les variables xi, tels que la pro-position S soit verifiee. Lorsque la condition darret est verifiee, le pro-gramme doit avoir fini son traitement, et S est verifiee.

Implications : Elles sont de la forme I(x1, x2, , xn)

i(Pi vraies) I(x1, x

2, , x

3).

Ou Pi representent des propositions

On en deduit lexpression :

I(xi) TANTQUE(Condition darret)FAIRE Pi I(xi) (Condition darret)

1.2.1 Exemple : somme des elements dun tableau

Soit un programme realisant la somme de tous les elements de 0 a n 1 dun

tableau T. On veut un programme P verifiant lenonce suivant :

(n > 0) P

S =

n1i=0

T[i]

On se propose de decrire ce programme par linvariant :

Invariant : I(s, k) s =k1

i=0 T[i] . s est la somme des k premiers elements deT.

Initialisation : s = 0 et k = 0. En effet la somme des 0 premiers elements fait

0. Donc I(0, 0) est verifie.Condition darret : k = n. On sarrete lorsque lon a realisee la somme des n

premiers elements, comme demande.

Implication : I(s, k) (s = s + T[k]) I(s, k + 1).

En sortie du programme, on aura I(s, k) (k = n). La translation de cet algo-rithme en pseudo langage est tres simple :

s < - 0

k < - 0

// Ici on a I(0,0)

tant que (k != n) faire :s


12/168

Chapitre 2

Problemes de recherches

Le probleme que nous nous posons est de rechercher un element (nombre,caractere ou autre) dans un tableau homogene delements. La particularite de cetableau est quil est deja trie dans lordre croissant (ce qui impose davoir unerelation dordre entre les elements).

2.1 Remarques sur levaluation de complexitedun programme

Dans ce paragraphe et ceux qui suivront, nous allons evaluer le temps dexe-cution des programmes en fonction de la taille n du probleme. Comparer 2 pro-

grammes, cest comparer les temps dexecution dans les pires des cas respectifs.Les constantes dependent de la machine qui executera lalgorithme.

Definition : Le programme P est de complexite O(f(n)) sil existe et n0tels que :

n n0 Tp(n) f(n)

Ou Tp(n) represente le temps dexecution du programme P dans le pire des cas.Remarque : Si le programme P est en O(n), alors il est aussi en O(2n), O( n2 ) ouO(n2).

2.2 Recherche dichotomique

Supposons que lon cherche un element note e dans un tableau T. Le pro-gramme de recherche dichotomique que nous allons mettre au point repond alenonce suivant :

(T[0] e T[n 1]) RD (T[k] e T[k + 1])

11


13/168

Invariant : I(i, j) T[i] e T[j 1]

Condition darret : j = i + 2

Initialisation : (i = 0) (j = n)Implications : I(i, j) ((j i) > 2)

e < T[ i+j2 ]

I(i, i+j2 )

I(i, j) ((j i) > 2) (e T[ i+j2 ]) I(i+j

2 , i)

Ce programme se base sur le fait que le tableau est deja trie. On comparelelement a rechercher avec lelement du milieu du tableau. Si lelement que lonrecherche est inferieur, alors il se trouve dans le sous-tableau de gauche, sinondans celui de droite.On continue a appliquer le meme raisonnement de maniere iterative jusqua ceque lon a pu assez encadrer lelement.

2.2.1 Code Source

1

2 i=0;

3 j=n;

4

5 while( j-i > 2)

6 {

7 if (e < T[(i+j)/2]) // I(i,(i+j)/2)

8 j = (j+i)/2; // I(i,j)

9 else // I((i+j)/2,j)10 i = (j+i)/2; // I(i,j)

11 }

12 // Ici on a I(i,j)&&(j-i = 2)

On peut eventuellement faire une verification prealable sur les donnees (pourvoir si e T[0 n 1])

2.2.2 Complexite

On rappelle linvariant :

I(i, j) T[i] e T[j 1]

Precondition : T[0] e T[n 1]Postcondition : T[i] e T[i + 1]

Linitialisation se fait en temps constant (on suppose a). Levaluation de lacondition de la boucle est elle aussi en temps constant, note b. Le corps de laboucle est egalement en temps constant c.

12


14/168

A chaque execution du corps de boucle, la taille du probleme restant a traiter estdivisee par 2. On a la suite valeurs n, n

2, n

4,..., 1.

Hypothese : La taille du probleme n est supposee etre un multiple de 2.n = 2p. Avec n = 2p le corps de boucle est execute p fois.

Trd = a + (p + 1)b + pc

Trd = (a + b) + p(b + c)

Trd = log2(n) +

Pour un probleme de taille n = 2p, la complexite de la recherche dichotomiqueest de forme logarithmique, mais supposons que la taille du probleme ne soit pasun multiple de 2.Pour 2p n 2p+1

log2(n) + Trd a + b(p + 2) + (p + 1)c

log2(n) + Trd log2(n) +

On peut en deduire que le facteur dominant du temps de calcul est en log2(n), larecherche dichotomique est (log2(n))Remarque : Le logarithme base 2 et le logarithme neperien (base e) ne differentque dune constante, par consequent la recherche dichotomique est O(log(n)).

2.3 Recherche sequentielle

La recherche sequentielle est une methode plus traditionnelle : on regardetous les elements du tableau sequentiellement jusqua ce que lon tombe sur e,lelement que lon cherchait.Lavantage de la recherche sequentielle est quelle est possible sur des tableauxnon-tries.

Invariant : I(k) e / T[0...k 1]

Initialisation : k = 0

Condition darret : T[k] = e

Implications : I(k) (T[k] = e) I(k + 1)

2.3.1 Code

1 k = 0 ;

2

3 while( T[k] != e)

13


15/168


16/168

Initialisation : (p = 0) (q = n 1) (x = 0)

Condition darret : (p = m) (q = 1)

Implications :I(x,p,q) (p = m) (q = 1) (T[p][q] = e) I(x + 1, p + 1, q 1)I(x,p,q) (p = m) (q = 1) (T[p][q] < e) I(x, p + 1, q)I(x,p,q) (p = m) (q = 1) (T[p][q] > e) I(x,p,q 1)

2.4.1 Code

1 int p = 0;

2 int x = 0;

3 int q = n-1;

4

5 while( (p != n) && (q != -1) )

6 {

7 if (T[p][q] == e) // I(x+1,p+1,q-1)

8 { x++; p++; q--; } // I(x,p,q)

9 else if (T[p][q] < e) // I(x,p+1,q)

10 { p++; } // I(x,p,q)

11 else // I(x,p,q-1)

12 { q--; } // I(x,p,q)

13 }

2.4.2 Complexite

Le corps de boucle est en temps constants (structure if, incrementations). Lacondition du while est elle aussi en O(1), le corps de boucle est evalue au plusm + n fois, donc la complexite de la recherche arriere est en (m + n)

15


17/168

Chapitre 3

Problemes de tris

On veut trier un tableau T[0...n 1] = [t0...tn1] delements par ordre crois-sant. Pour cela, on etudiera plusieurs algorithmes : le slowsort, puis le quick-sort.

3.1 Slowsort

Invariant : I(k) T[0...k 1] trie T[0...k 1] T[k...n 1]

Condition darret : k = n

Initialisation : (k = 0) (I(0) est vrai)

Implications :I(k)(k = n)(t

m= min(T[k...n1]))(T[k] = t

m)(T[m] =

tk) I(k + 1)

3.1.1 Code

1 k=0; // I(0)

2 while(k != n)

3 {

4 m = min(T,k,n);

5 permuter(T[k], T[m]); // I(k+1)

6 k++; // I(k)

7 } // I(k) & (k=n)

3.1.2 Complexite

On suppose que les operations des lignes 1,5,6 sont en temps constants. Lacomparaison de la ligne 2 est aussi supposee en temps constant.Il reste a evaluer le temps dexecution de la ligne 4. On peut supposer que larecherche du minimum est en temps lineaire. Le temps de calcul du recherche du

16


18/168

min sur un tableau T[k...n 1] secrit :

a(n k) + b Tmin(n k) a(n k) + b

Le corps de la boucle while est executee n fois pour k = 0, 1, 2,...,n 1.

an1i=0

i + nb + nc Twhile a

n1i=0

i + nb + nc

an(n 1)

2+ n(b + c) Twhile a

n(n 1)

2+ n(b + c)

n2 + n Twhile n2 + n

En resumant les constantes dinitialisation par , on peut evaluer la complexitedu slowsort par :

n2 + n + Tss(n) n2 + n +

Pour des grandes valeurs ainsi Tss(n) = O(n2).

3.2 Quicksort

Lalgorithme de tri rapide, ou quicksort a ete mis au point par OHare dansles annees 50. Il repose sur une approche dite diviser pour regner.

Cette approche consiste a separer de facon optimale le probleme en 2 (ou plus)problemes de taille inferieure.Le quicksort fonctionne ainsi :

1 procedure QS(Tableau T, entier i, entier j)

2 entier k

3 si (j-i > 1)

4 segmenter(T, i, j, k)

5 QS(T,i,k)

6 QS(T,k+1,j)

7 finsi

On remarque que lessentiel du travail est effectue a la ligne 4 par la proceduresegmenter. Cest cette procedure que nous nous attacherons a decrire. La fonctionsegmenter va choisir un element T[k] du tableau, appele le pivot et reorganiser letableau tel que :

T[i...k 1] T[k] T[k + 1...j]

17


19/168

3.2.1 Segmenter

Cette procedure segmenter est batie sur linvariant suivant :

Invariant : I(k, k) T[i..k 1] < T[k] < T[k...k 1]

Initialisation : (k = i) (k = k + 1)

Condition darret : k = j

Implications :I(k, k) (T[k] > T[k]) I(k, k + 1)I(k, k) (T[k] < T[k]) (T[k] = tk) (T[k + 1] = tk) (T[k] = tk+1) I(k + 1, k + 1)

3.2.2 Code Source

1 void segmenter(T,i,j,k)

2 {

3 int k;

4 k = i ;

5 k= k+1;

6

7 while(k != j)

8 if (T[k] < T[k])

9 else {

10 permuter(T[k],T[k+1]);

11 permuter(T[k+1],T[k]);12 k++;

13 } k++;

14 }

3.2.3 Complexite du Quicksort

On remarque aisement que la complexite du corps de quicksort depend de lacomplexite de segmenter.

Complexite de segmenter

segmenter(T,i,j,k) est fonction lineaire de j i : (j i).

(j i) + Tseg (j i) +

18


20/168

Complexite de quicksort

Il y a 2 cas de figures :

j i > 1 :

TQS(i, j) A1 + A2 + Tseg(j i) + TQS(i, k) + TQS(k + 1, j)

TQS(i, j) A1 + A2 + (j i) + + TQS(i, k) + TQS(k + 1, j)

j i 1 :TQS(i, j) = A1 + A2

On a une equation de recurrence dun majorant du temps de calcul de QS(T ,i ,j) : j i 1 TQS(j i) = B0 j i > 1 TQS(j i) TQS(k i) + TQS(j k) + A(j i) + B

Nous sommes en presence de 2 cas limites :

Hypothese 1 : A chaque segmentation T[i...j] est separe en 2 tableaux detaille identiques : T[i...k 1] et T[k...j 1] tels que k i = j k. Dans ce cas,puisque les 2 tableaux sont de taille identique, on peut affirmer que la taille duprobleme est n = 2p

Hypothese 2 : A chaque segmentation T[i...j] est separe en 2 tableaux detaille quelconque :

Traitons chacune des hypotheses :

Hypothese numero 1 :

j i = 1 = 20 TQS(20) = B0

j i > 2p>0 TQS(2p) TQS(2

p1) + TQS(2p1) + (A 2p + B)

Essayons pour n = 20, 21, 22, 23... :

n = 20 T(1) = B0

n = 21 T(21) T(20) + T(20) + (A 21 + B)

T(21) = 2T(20) + (A21 + B) = 2B0 + 2A + B

n = 22 T(22) 2T(21) + (A 22 + B)

T(22) = 22B0 + 22B + 23A

19


21/168

Dune maniere generale, la complexite du quicksort pour un probleme de taillen = 2p est :

T(2p) = p 2p + 2p + T(n = 2p) = log2(n) n + 2

p +

(3.1)

Donc, sous lhypothese dun tableau separe en 2 parties egales la complexitedu quicksort est : TQS(n = 2

p) = O(n log2(n)).

Considerons le cas ou le tableau est deja trie par ordre croissant :

TQS(1) = A(constante)

TQS(n > 1) = B + Tseg(n) + TQS(1) + TQS(n 1)

TQS(n > 1) = B + (n + ) + A + TQS(n 1)

TQS(n > 1) = n + C+ TQS(n 1)

Si on devellope :

TQS(n) = n

i=2

i + (n 1)C+ A

TQS(n) = n(n + 1)

2

+ (n 1)C+ (A )

TQS(n) = n2

2

n + 2(n 1)

2+ (A C)

La complexite dun quicksort pour un tableau deja trie est donc en O(n2), cequi est beaucoup moins bon que la complexite originale en O(n log(n)) pour untableau quelconque.

3.2.4 Amelioration du quicksort

Nous avons vu que la complexite du quicksort dans le cas general est enO(n log(n)), tandis que celle dun tableau deja trie est en O(n2). La raison de

cette complexite en O(n2) (identique a un slowsort pour le meme tableau) estque la fonction segmenter coupe le tableau initial de taille n en 2 tableaux, lunde taille 1, lautre de taille n 1.Il faut donc ameliorer le quicksort pour effectuer une coupe plus egale. En effet,si le tableau initiale est coupe en 2 tableaux de taille n

2la complexite du quicksort

baisse a O(n log(n)).

Voici une amelioration possible, qui consiste a echanger le pivot (T[i]) par unautre element du tableau, tire au hasard.

20


22/168

1 procedure QS(Tableau T, entier i, entier j)

2 entier k

3 si (j-i > 1)

4 segmenter(T, i, j, k)

5 a = tirage_aleatoire(T,i,j)

6 permuter(T[i], T[a])

7 QS(T,i,k)

8 QS(T,k+1,j)

9 finsi

On peut aussi remplacer le tirage aleatoire par un tirage plus recherche, enprenant par exemple, la valeur mediane. Dans tous les cas, ce tirage doit etre en(n log(n)) pour conserver la complexite du quicksort.

3.3 Complexite minimum dun algorithme detri

Nous avons vu que des algorithmes intuitifs (donc nafs), tels le slowsortou le bubble sort avaient des complexites de lordre de n2. Des algorithmesameliores, comme le quicksort ou le heapsort ont des complexites inferieures,en n log(n).On est en droit de se demander si ces algorithmes sont les plusoptimaux, cest a dire sil existe un algorithme de tri en O(f(n)) avec f(n) 1) = (n) + 2TF(n

2)

Le tri fusion est donc bien en (n log(n)). Le probleme est que ce tri vacouter tres cher en memoire.

23


25/168

4.2 Limites de lapproche diviser pour regner

Lapproche diviser pour regner a ses limites : cest le recouvrement de sousproblemes.Si lon prend T(n) le temps de calcul du probleme de taille n, on a :

T(n) = T(f(n)) +

i

T(ni)

Si

i ni n lalgorithme est efficace, sinon le temps de calcul devient exponen-tielle ((2n)). Il faudra alors utiliser la programmation dynamique

24


26/168

Chapitre 5

Complexite des algorithmes

Dans cette section, nous nous attacherons a evaluer la complexite des algo-rithmes.Evaluer la complexite dun algorithme consiste a determiner la forme du tempsde calcul asymptotique. En dautres termes il sagit de determiner quelle sera,dans lexpression du temps de calcul dun algorithme, le terme Ai = f(n) telsque tous les autres termes Aj=i soit negligeable devant Ai pour n = +.Cette recherche de la complexite dun algorithme se fait dans le pire des cas,cest a dire que larrangement des donnees du probleme, bien qualeatoire, pousselalgorithme dans ses limites.

5.1 Expression du temps de calculChercher lexpression du temps de calcul dun algorithme consiste a evaluer

une fonction f(n) donnant le temps de calcul dun algorithme en fonction de lataille n du probleme et de constantes Ci.La taille du probleme, note n, peut tres bien le cardinal de lensemble a trier pourun algorithme de tri. Il peut aussi sagir dun couple, ou dune liste de variables,par exemple lors des problemes traitant de graphes, on exprime f en fonction de(V, E), ou V et E sont le nombre de vertices (arcs) et E le nombre de places dansce graphe.

Pour determiner cette expression, on travaille habituellement sur le codesource du programme, ou sur une version en pseudo-langage detaillee. On prendssoin de ne pas prendre en compte les fonctions dentree/sorties (en C : printfet scanf).On prends chaque ligne de ce programme et on lui affecte une constante de coutci. Ce cout represente le temps dexecution de linstruction a la ligne i, et dependdes caracteristiques de lordinateur qui execute lalgorithme. On essaye devaluer

25


27/168

egalement pour chaque ligne, le nombre de fois que cette ligne va etre executee,en fonction de n, et que lon va noter gi(n).Ainsi on obtient lexpression du temps de calcul en realisant la somme suivante :

f(n) =

pi=1

ci gi(n)

Letape suivante consiste a developper les fonctions gi(n) (lorsque celles-ci peuventetre developpes algebriquement, ou sommees lorsquelles sont sous la forme deserie numeriques), puis a ordonner selon les puissances de n decroissantes :

f(n) = C0 nk + C1 n

k1 + + Ck1 n + Ck

Lorsque le developpement presente des termes qui ne sont pas sous la formenk, on essaye de les encadrer, ou des les approximer, en tenant compte que lontravaille sur des valeurs de n assez grandes. Par exemple n2 > n log(n) > n, oun! > nk k.

Ce que lon appelle complexite de lalgorithme, se note sous la forme (F(n)).Avec F(n) tel que, (n > N f ix ), ( R) t.q. F(n) > f(n).Concretement, il sagit du premier terme du developpement de f(n) debarasse desa constante.

Exemples f(n) = A.n2 + B.n + C.n, alors lalgorithme est en (n2) donc egalement

en (5n2). f(n) = 50.n5 + n!, alors (n!).

En conclusion on peut dire que le temps de calcul dun programme ne dependpas uniquement de la complexite de lalgorithme sur lequel il se base. Dautresfacteurs interviennent, notamment les constantes que lon neglige, et les carac-teristiques de lordinateur. Neanmoins la complexite permet de se faire une ideede levolution du temps de calcul, independament de lordinateur utilise, lorsque

lon multiplie la taille du probleme, par 10 par exemple.Ainsi la complexite, permet en quelque sorte de juger de la performance desalgorithmes lorsque lon sattaque a des problemes de grande taille.

5.2 Notations

En plus de la notation (f(n)), on utilise egalement deux autres notations :la notation O (grand o), et la notation .

26


28/168

La notation O(F(n)) designe un majorant du temps de calcul.De meme, la notation (F(n)) designe un minorant du temps de calcul.

En appellant Fi(n) lensemble des fonctions tels que lalgorithme soit en O(fi Fi) et Gi(n) la famille de fonction tels que lalgorithme soit en (gi Gi), onalors Fi Gi = i avec i la famille de fonctions de n tels que la complexite dela lalgorithme soit en (i i).

Exemple : On peut deduire dun algorithme qui est en O(3n2), O(0.5n3),(10n2) et (n), quil sera en (n2).

5.3 Calculs courants dans le calcul des complexi-tes

Certains calculs courants peuvent apparatre lors de levaluation du temps decalcul dun programme. Je nai pas la pretention de donner toutes les astucespermettant de donner la complexite dun programme tres facilement, car cela sefait au feeling avec lhabitude.Neanmoins, cerains resultats importants meritent detre retenus :

ni=1

i =n(n + 1)

2 = (n2)

x < 1+k=0

xk =1

1 x

n

i=11/i = ln(n) + O(1) = (ln(n))

5.4 Un peu de theorie de la complexite

Nota Bene : Partie non traitee en cours

Au dela des algorithmes, que lon peut classer par complexite, il y a les pro-blemes, auxquels les algorithmes repondent. Il existent plusieurs classes de pro-bleme.

27


29/168

5.4.1 Solution ou pas

Il faut dabord differencier la solution dun probleme des solutions dun pro-

bleme. En effet, pour un probleme P auquel il y a une ou plusieurs solutions S.Chercher S est different de verifier si parmi toutes les propositions logiques s,s S.Prenons par exemple le cas de la factorisation dun entier N. Determiner len-semble des diviseurs premiers de N est different de verifier si une suite fini denombres premiers correspond bien a la factorisation de N.

5.4.2 Classes de problemes

La classe P : Cest la classe des problemes pour lesquels il existent une solutionque lon peut determiner integralement en temps polynomial, cest a direquil existe un algorithme pour ce probleme dont la complexite est en (nk).

La classe E : Cest la classe des problemes intrinsequement exponentiel, cest adire que tout algorithme sera de la forme (kn) avec k une constante.

La classe NP : (Abbreviation de Non-Deterministe Polynomiaux Cest la classedes problemes dont on peut verifier les solutions en temps polynomial, maisdont on ne connait pas forcement dalgorithme permettant de trouver lessolutions. Typiquement ce sont des problemes plus difficiles que ceux de P.

5.4.3 NP-CompletOn dit quun probleme est NP-Complet quand tous les problemes appartenant

a NP lui sont reductibles. Cest a dire si lon trouve une solution polynomial a unprobleme NP-Complet, alors tous les problemes NP-Complet peuvent etre resolusen temps polynomial aussi. Cest pourquoi les problemes dit NP-Complet sontgeneralement ceux qui sont les plus durs.Lorsque lon a affaire a un probleme NP-Complet, on essaye generalement dedevelopper un algorithme qui sapproche de la solution.

28


30/168


31/168

Un tel programme a une complexite exponentielle en O(2n). En pratique, lestemps de calcul depasse la seconde pour calculs dordre n > 40. Ceci est due ala relaive lourdeur de la recursivite : lordinateur va passer beaucoup de tempsa empiler et depiler les arguments de la fonction. La programmation dynamiquepropose un algorithme modifie :

T := Tableau dentier T[0...n]

T[0]


32/168

Le cout total de cette methode est T = pqr + prs = pr(q + s).

Deuxieme methode (T = A (B C)) :

Ap,q (Bq,r Cr,s) qrs

pqs

Le cout total de cette methode est T = qrs + pqs = qs(p + r).

On a un cout total pour ces 2 methodes different. Prenons un exemple :

p = 10 ; q = 104 ; r = 1 ; s = 104

Premiere methode : T = 10(104 + 104) = 2 104

Deuxieme methode : T = 108(10 + 1) = 11 108

Le rapport est donc de 5, 5 103, ce qui est tres significatif, dou limportance duparenthesage.

6.2.2 Algorithme de calcul.

Cet algorithme va proceder en 2 temps :1 - Determiner le cout minimum du produit < A0 . . . An1 >.2 - Calculer < A0 . . . An1 > selon le parenthesage optimal.

6.2.3 Cout minimum

Notation : Soit mij le nombre minimum de multiplications scalaires pour mul-tipliers les matrices Ai . . . Aj1.

mi i+1 = 0 i.

On note m(k)ij le cout du produit parenthese (Ai . . . Ak1)(Ak . . . Aj1). On a

m(k)ij = mik + mkj + PiPkPj.

Pour tout i, j tels que j > i + 1, on note mij le cout optimal pour lamultiplication des matrices Ai Aj1. Ce cout est le plus petit mkij.

mij =min

i < k < j (mik + mkj + PiPkPj)

On peut en deduire le code source de cette fonction aisement :

31


33/168

1 int m(int i, int j, tabDimMat P)

2 {

3 if (j == i+1) return 0;

4 else return min(m(i,k,P)+m(k,j,P)+P[i]*P[j]*P[k]);

5 }

Cette methode de calcul des couts minimum a un enorme probleme : il y a unrecouvrement des sous problemes : certains couts seront calcules plusieurs foisPour contrer cela, nous allons stocker dans un tableau les mij dans une matrice :

Mm0 Mm1 Mmn...

... Mii Mii+1...

. . . Mii Mii+1 Mii+1

... . . .

M00 M0n

Les elements Mii de la diagonale representent les couts des produits mii = 0. Ladiagonale est donc nulle De meme, la diagonale inferieure (Mi i+1) est nulle. Onutilise lalgorithme suivant pour remplir la partie inferieure du tableau :

// Calcul des problemes de taille 1

pour i allant de 0 a n-1

M[i][i+1] = 0

// Calcul par taille t croissantpour t allant de 2 a n

// calcul pour chaque taille t de tous les problemes de taille t

pour i allant de 0 a (n-t)

j = i+t

M[i][i+t] = min( M[i][k] + M[k][i+t] +P[i]*P[i+t]*P[k] )

Chaque diagonale t (elements du tableau m[i][i + t]) represente le cout dunprobleme de taille t.On peut maintenant etablir linvariant de lalgorithme de remplissage de la ma-trice des couts :

Invariant : I(,n,k) (m = min(M[i][n] + M[n][] + P[I] P[n] P[]) (k = argM[i][j])

Initialisation : ( = i + 2) (x = i + 1) (k = i + 1)

Arret : = j

Implications : I(,m,k) (m = M[i][] + M[][j] + P[i]P[]P[j]) (m m) I( + 1, m , k)I(,m,k) (m = M[i][] + M[][j] + P[i]P[]P[j]) (m < m) I( +1, m, k)

32


34/168

6.2.4 Calcul optimal du produit

Nous venons de calculer les couts optimaux pour le produits de matrices. Ces

couts sont stockes dans la partie inferieure dune matrice MNous allons faire en sorte que la partie superieure de la matrice M contient lesvaleurs kij tels que lont ait le cout minimum mij . M[i][j] = mij ; M[j][i] = kij .Le cout m0n de la multiplication des n 1 matrices se trouve donc en M[0][n].Il nous reste donc maintenant a calculer effectivement le produits de ces n 1matrices en utilisant les informations sur le parenthesage optimal contenu dansM.

Calcul du produit Ai Aj

1 void multopt(matrice resultat, matrice_couts M, matrice *A, int i, int j)

2 {3 matrice P1, P2;

4

5 if (j=i+1) resultat= A[i];

6 else {

7 multopt(P1,M,A,M[j][i],j);

8 multopt(P2,M,A,i,M[j][i]);

9 mult_matrice(resultat,P1,P2);

10 }

11 }

Lappel initial a cette fonction est multopt(resultat, A, M, 0, n).

6.3 Exemple : Recherche du plus long sous-motcommun a 2 chaines

Soit 2 mots A et B. Ces mots sont composes de caracteres ai et bj .A a0a1a2 am1B b0b1b2 bm1

Le probleme que nous nous posons ici est de calculer le plus long sous mot Mcommun a 2 mots A et B.Soit L(x, y) la longueur du plus long sous-mot commun a A(x) et B(y) Ainsipour tout i, j on a les propositions suivantes :

i > 0 et j > 0 : ai1 = bj1 L(i, j) = max(L(i 1, j), L(i, j 1))

i > 0 et j > 0 : i > ai1 = bj1 L(i, j) = 1 + L(i 1, j 1))

i = 0 : L(0, j) = 0

j = 0 : L(i, 0) = 0

33


35/168

6.3.1 Taille du probleme

Le but est de calculer L(m, n) longueur du probleme (A(m), B(n)). i, j,

L(i, j) sera calcule, par taille de probleme croissant.Il faut que chaque valeur L(i, j) ne soit calcule quune seule fois. Cest pourquoinous stockerons ces valeurs dans une matrice M[0 m][0 n].

6.3.2 Reconstruction de la solution

// Calcul des pbs de taille 0

pour i allant de 0 a m L[i][0] = 0

pour j allant de 0 a n L[0][j] = 0

// Calcul de tous les probl\emes par taille croissant

pour t allant de 1 a mpour i allant de t a m

si A[i-1]=B[t-1], alors L[i][t] = L[i-1][t-1] + 1

sinon L[i][t] = max( L[i-1][t], L[i][t-1] )

pour j allant de t a n

si A[t-1]=B[j-1], alors L[t][j] = L[t-1][j-1] + 1

sinon L[t][j] = max( L[t][j-1], L[t-1][j] )

La complexite de cet algorithme est (m n).

6.3.3 Exemple

Voici la matrice generee pour les deux chanes :

A = bca B = cabd

L =

3 0 1 2 2 22 0 1 1 1 11 0 0 0 1 10 0 0 0 0 0L 0 1 2 3 4

6.3.4 Affichage du plus long sous mot

Appelons M(p) le plus long sous-mot commun a A(m) et B(n). La longueurde de M(p) a deja ete calculee et se trouve a lemplacement (m, n) de la matriceL dont la construction vient detre detaillee.

M(p) = m0m1 mp1

34


36/168

. En appelant M(k) le k-prefixe, et M(k) le k-suffixe : M(k) = m0m1 mk1M(k) = mpmp1 mpk

M(p) = M(k).M(k)

Nous allons construire le programme de reconstruction de la plus longue souschane commune, base sur linvariant suivant :

Invariant : I(k,i,j) (M(k) affiche)(M(k) = PLSM(A(i), B(j))reste a afficher)(M(k).M(k) = M(p))

Init : (k = L[m][n]) (i = m) (j = n)

Arret : k = 0

Implications : I(k,i,j) (k = 0) (L(i, j) = 1 + L(i 1, j 1)) (A[i

1]affiche) I(k 1, i 1, j 1)I(k,i,j) (k = 0) (L(i 1, j) > L(i, j 1)) I(k, i 1, j)I(k,i,j) (k = 0) (L(i 1, j) L(i, j 1)) I(k,i,j 1)

Le code source de ce programme secrit tout simplement grace a cet invariant :

1 int k = L[m][n];

2 int i = m;

3 int j = n;

4

5 while (k != 0)

6 {

7 if ( L[i][j] == L[i-1][j-1] )

8 {

9 printf("%c ", A[i-1]);

10 i--; j--; k--;

11 } else if (L[i-1][j] > L[i][j-1]) i--;

12 else j--;

13 }

On peut remarquer que ce programme affiche la plus longe sous-chane communedans lordre inverse. Toutefois, ce nest pas si grave car on sait inverser des chainesen temps lineaire.

35


37/168

Deuxieme partie

IN311 - Programmationdynamique

36


38/168

Introduction au cours deprogrammation dynamique

Extrait de la brochure Programme des enseignements de 3o Annee :

La programmation dynamique est une methode doptimisation operant parphases (ou sequences) dont lefficacite repose sur le principe doptimalite de Bell-man : toute politique optimale est composee de sous-politiques optimalesCette unite met laccent sur la diversite des domaines et des problemes dappa-rence tres eloignes qui lorsquils sont correctement modelises relevent de la memetechnique. Elle permet de mettre en pratique sur des problemes de traitement dusignal, de controle et dinformatique les concepts abordes dans les cours dinfor-matique logicielle et materielle des deux premieres annees du tronc commun.Resoudre un probleme doptimalite par la programmation dynamique est, dans

ce contexte precis, une mise en oeuvre significative de la diversite des compe-tences attendues dun ingenieur : modelisation du probleme, proposition duneequation de recurrence, proposition dun algorithme efficace de resolution du pro-bleme (modelisation informatique des donnees, evaluation de complexite) ; etudedes differentes optimisations possibles de lalgorithme ; programmation effective ;possibilites dimplantation sur architectures specifiques deduites de lalgorithmeet des contraintes de programmation.

37


39/168

Chapitre 7

Applications de laprogrammation dynamique

7.1 Un probleme dassortiment

7.1.1 Sujet

On considere m objets, de format 1, 2, , m (tous les objets sont de formatsdifferents). Ces objets doivent etre empaquetes avec du papier demballage.Le papier demballage est disponible sous forme de feuilles chez le fabricant, etdans tous les formats convenables. Pour des raisons de cout de fabrication, la com-mande des m feuilles doit etre faite parmi n formats seulement. Le cout dune

feuille crot avec le format. Un format permet demballer tout objet de formatinferieur ou egal.Le probleme pose est celui du choix des n formats permettant dempaqueter lesm objets a moindre cout. Les donnees du probleme sont le nombre dobjets m,le nombre de formats n et, pour tout format f, 1 f n, son cout c(f).

On demande un algorithme calculant en temps polynomial le cout minimumde la commande et un assortiment de formats qui permette dobtenir ce coutminimum.

7.1.2 Resolution

On part du principe doptimalite de Bellman : Une solution optimale estcomposee de sous-solutions elles-memes optimales. On va raisonner ainsi par taillede problemes croissants.La taille du probleme est ici m, le nombre de formats a choisir.On note M(m, n) le cout minimum pour emballer les objets de taille 1...n avec mformats. Ce cout implique que les formats de feuilles demballage sont reparties

38


40/168

au mieux pour emballer les objets les objets des n premieres tailles.

On note x(t) | t [1, n], le nombre dobjets pour une taille t.Si lon ne dispose quune seule feuille de taille n pour emballer tous les objets, ilest evident que celle-ci doit etre de la taille du plus grand objet a emballer. Dunemaniere generale, la plus petite taille permettant demballer le plus grand objetdoit etre choisie. Quelque soit lassortiment de feuilles choisies optimalement,celui-ci comporte la feuille de taille n.

7.1.3 Cas general

Nous savons deja place le dernier emballage, de taille n. Il nous reste donca placer m 1 emballages optimalement. Pour cela on place un emballage enposition k, ainsi on en revient a un probleme de taille m1, sur k tailles dobjets.

k n0

M(m-1,k)

Tailles d'emballges

En notant Ct le cout pour emballer les n emballages :

Ct = M(m 1, k) +n

t=k+1

(c(n) x(t))

De la, on tire lequation de recurrence :

1 < m n M(m, n) =m1kn1

min

M(m 1, k) +

nt=k+1

c(n) x(t)

La borne inferieure du minimum vient du fait quil ne faut pas quil y ait plusde formats que de tailles. Si k < m 1, le probleme ne serait pas optimal.

39


41/168

On doit donc calculer M pour les problemes de taille 1 :

M(1, p) =

pt=1

c(p) x(t) p [1, n]

7.2 Compression dimage

7.2.1 Sujet

On considere une image en m niveaux de gris. Chaque pixel de limage a unniveau de gris compris entre 0 et m 1. On veut comprimer cette image enrestreignant a n le nombre de niveaux de gris de limage. Ces n niveaux sont achoisir parmi les m valeurs de limage dorigine.

Dans cette compression, le niveau de gris de chaque pixel est remplace par leniveau de gris le plus proche au sein des n niveaux choisis. La question posee estle choix de n niveaux de gris qui permettront cette compression avec le minimumderreur.Lerreur est ainsi definie :

pour chaque pixel lerreur est la distance entre sa valeur de niveau de griset le niveau de gris le plus proche parmi les n niveaux choisis.

lerreur de compression est la somme des erreurs des pixels de limage.Propose un algorithme calculant en temps polynomial lerreur de compression

minimum et un choix de n niveaux de gris permettant datteindre cette erreurminimum.

7.2.2 Histogramme

On dispose de lhistogramme de limage. Cette histogramme represente lafonction discrete t [0, m 1] f(t), ou f(t) represente le nombre de pixelsde couleur t.

7.2.3 Resolution du probleme

Le probleme est de choisir au mieux les n niveaux de gris pour representerlimage par les m niveaux deja present dans limage. Pour cela il faut minimiserlerreur.

40


42/168

0 m

f(t)

niveaux de gris

nombrede

pixel

On peut representer la compression par une application entre les niveaux degris de limage originale et les niveaux de gris de limage compressee.

imageoriginale

m niveaux

imagecompressee

n niveaux

Compression

C

En notant cette application C(t)) t [0, m 1], on peut exprimer lerreurep commise pour chaque pixel p dont le niveau de gris est gp :

ep = |gp C(gp)|

Ainsi la qualite de la compression sexprime grace a lerreur totale E :

E =

pimage

ep =

pimage

|gp C(gp)|

Pour ameliorer la qualite il faut minimiser lerreur totale E.

41


43/168

7.2.4 Equation de recurrence

On note lerreur X(N, M) lerreur commise en representant au mieux une

compression de M niveaux de gris sur N. Ainsi X(n, m) = Eminimal.

Calculons E(0, ), cest le cas ou lon nutilise aucun niveau de gris pourrepresenter les premier niveaux de gris de limage. Ainsi pour les niveaux degris 0 1 de limage, il y a une erreur de commise. En admettant quils soienttous representes par le niveau :

E(0, ) =

1g=0

f(g) |g |

On se place dans le cas ou lon a deja optimise le choix des niveaux de grispour minimiser la compression des m P derniers niveaux de gris de limage.Nous allons calculer X(t, P), lerreur commise en compressant P niveaux de grisen t.On admet que le niveau de gris k est choisi pour etre un representant. Les niveauxde gris entre k et P vont donc etre represente soit par k, soit par P, selon leurposition.

0 m

f(t)

niveaux de gris

nombrede

pixel

g

Pk

42


44/168

Lerreur X(t, P) sera egale a lerreur commise pour la representation des pixelsdont le niveau se situe entre k et P plus lerreur X(t 1, k) commise pour repre-senter les k premiers niveaux de gris.

X(t, P) = e(k, P) + X(t 1, k)

Avec e(k, P) lerreur commise en representant les pixels dont la couleur est dansla partie inferieur de lintervalle [k, P] par k et les pixels dont la couleur se trouvedans la partie superieure par P.

e(k, P) =

k+P

2g=k

(f(g) |g k|) +P

g=k+P2

(f(g) |g k|)

De la, on peut tirer lequation de reccurence :

X(n, ) =k[n1,1]

min [e(k, ) + X(n 1, k)]

Lintervalle [n 1, 1] sexplique par le fait que la compression est une appli-cation : on ne peut pas compresser un pixel en lui donnant 2 representant, il faurdonc k n.

7.2.5 Cas particulier

Lequation de reccurence ne permet pas explicitement de placer le dernierrepresentant, a partir duquel seffectue tout lalgorithme. Ce niveau se calculeainsi :

E = X(n, m) =k[n1,m1]

min

X(n 1, k) +

m1g=k

f(g) |g k|

7.2.6 Programmation

Lequation de recurrence correspond au calcul dune erreur minimale. Pourchaque calcul de minima, on definit largument du min. comme etant la valeurde parametre permettant dobtenir ce cout minimum.Ici le parametre du minimum est k, chaque valeur de k que lon obtiendra cor-respondra a un niveau de gris compresse

7.3 Justification de Parapgraphes

7.3.1 Sujet

On considere n mots de longueurs l0, . . . ln1, que lon souhaire imprimer enune suite de lignes ayant chacune C caracteres, sauf la derniere qui peut en

43


45/168

compter moins (le texte que vous lisez actuellement est un exemple du resultatescompte).Le nombre c de caracteres dune ligne est la somme des longueurs des mots qui lacomposent, plus les blancs qui separent les mots (un blanc entre tout couple demots). Pour une telle ligne, il faut ajouter C c blancs supplementaires entre lesmots pour quelle ait exactement C caracteres. Le cout de cet ajout est (C c)3.Le cout de la justification du paragraphe est la somme de ces couts sur toutes leslignes, sauf la derniere.Proposer un algorithme calculant cette justification de paragraphes en un tempspolynomial.

7.3.2 Algorithme

On a N mots de longueurs respectives l0, l1, , ln1.On se place dans le cas dune ligne (sauf la derniere, qui est un cas particulier).Cette ligne composee des mots mimi+1 mj , a pour longueur L :

L =

jk=i

(lk + (j i 1))

Cette ligne amene un cout supplementaire (C L)3. On va chercher a minimiserle cout total de formattage du document, cest a dire minimiser (C L)3 pourchacune des lignes.

On note e(k) le cout minimum de formattage des k premiers mots. Sur cesk premiers mots, on sautorise a mettre au plus k 1 retours chariots, soit klignes. Pour la derniere ligne, on va chercher a minimiser le cout :

e(N) = min(e(k))

Pour tout k tel que la longueur des mots k N soit inferieur a C (longueurmaximale dune ligne), soit

Ni=k

(li + (N k 1)) C

Pour la premiere ligne, le cout e(1) est :e(1) = (C li)

3

dune maniere generale, on a :

e(m) =k

min

e(k 1) +

C

mi=k

li + (m k 1)

3Avec k tel que

(li + (m k 1)) C

44


46/168

Troisieme partie

IN302 - Graphes et algorithmes

45


47/168

Chapitre 8

Notions de base

8.1 Premiere definitionSoit E un ensemble fini. On appelle graphe sur E un couple G = (E, ) ou

est une application de E P(E).

Exemple i:

Soit un graphe G tel que E = {1, 2, 3, 4}. est definie par : (1) = 1, 2, 4 (2) = 3, 1 (3) = 4

(4) =

Cette definition de est plutot difficile a imaginer. La representation sous formesdarcs fleches de la figure 8.1 est plus pratique.

2

1

4

3

Fig. 8.1 Graphe de lexemple 1

46


48/168

Tout element de E est appele sommet. Tout couple ordonne (x, y) E E tel que y (x) est appele arc du graphe. Si (x, y) est un arc, on dit que y est un successeur de x. Si (x, y) est un arc, on dit que x est un predecesseur de y.

Le graphe G de lexemple i comporte 4 sommets et 6 arcs.

On designe par lensemble des arcs. Lensemble des arcs est une partie duproduit cartesien E E : = P(E E). On peut definir formellement par :

= {(x, y) E E / y (x)}

Remarque: On peut representer G par (E, ) ou par (E, ). On appellera egale-

ment graphe le couple (E, ).

8.2 Representation en memoire

Le probleme qui se pose est celui de la representation dun graphe dans unememoire informatique.

8.2.1 Representation des ensembles finis

On peut voir que lensemble des arcs peut etre represente par lensemble des

sucesseurs de chacun des sommets du graphe. Representer un graphe revient donca representer un ensemble fini. Soit E = 1, , n et tel que |E| = n. Commentrepresenter un sous-ensemble X de E?

Liste-tableau

Cette methode de representation dun sous-ensemble consiste a aligner leselements du sous ensemble a representer dans un tableau. Ce tableau a une taillefixe egale au cardinal de E (cardinal de la plus grande partie de E). Pour savoircombien delements comporte le sous-ensemble, on utilisera un caractere specialque lon definira comme etant la fin de la liste. On pourra egalement indiquer lenombre delements du sous ensemble en debut de liste.

Liste chanee

On utilise une liste chanee contenant les elements du sous-ensemble X.

47


49/168

Tableau de booleens

On utilise un tableau de taille n (cardinal de E) et tel que la case i du tableau

vaut vrai (1) si lelement i appartient au sous ensemble X. Si lelement i de Enappartient pas a X, alors la cause vaut faux (0).

Exemple i:

Prenons n = 9 et X = {1, 2, 4}. Liste-tableau :

1 2 3 4 5 n

21 4 X ........

Liste chanee :

2 41

Tableau de booleens :

1 2 3 4 7 8 9

0 0 0 0 0 0

6

111

5

8.2.2 Operations sur un ensemble

Selon la representation memoire que lon prend, les complexite des operationselementaires sur lensemble vont etre changee. Le tableau suivant presente lesdifferentes operations elementaires sur un ensemble ainsi que leur complexite selonle type de representation memoire choisie.

Operation Liste chanee Tableau de booleensInitialisation X = O(1) O(n)Test dappartenance x X? O(n) O(1)Test non-vide ?x X O(1) O(n) 1

Ajout dun element X = X {x} O(n)/O(1) 2 O(1)

48


50/168

Le choix dune representation memoire adaptee est un facteur a prendre encompte lors de la conception dalgorithmes.

8.2.3 Representation dun graphe

La representation liee a (E, ) est celle liee a lintegralite du graphe. Plusieursrepresentations sont possibles.

Deux tableaux

Cette representation consiste a choisir deux tableaux I et T de taille ||, telsque I(j) est le sommet initial de larc numero j et T(j) est le sommet terminalde larc numero j.

Tableaux de listes de chanees

Cela consiste a prendre un tableau M contenant n = |E| listes chanees et telque M(i) est la liste chanee des arcs partant du sommet numero i.

Matrice booleenne

Cest le type de donnees forme a partir des tableaux de booleens (8.2.1). Lamatrice M est telle que Mij = 1 arc entre i et j.

8.2.4 ComplexiteNous allons voir avec un exemple concret dalgorithme que le choix de la re-

presentation peut influer sur la complexite des programmes et donc leur efficacite.

Algorithme de recherche des successeurs dune partie

Lalgorithme suivant a pour but de rechercher les successeurs dune partie X dunensemble E.Donnees : G = (E, ), X E.Resultat : Y = ensemble des sommets de G qui sont successeurs des sommetsde X. On notera Y = (X).

Y =

y E , x X , (x, y)

1: Y

2: for all (x, y) do

3: if x X then

49


51/168

4: Y = Y {y}

5: end if

6: end for

Selon le choix du type de donnes pour X et Y, la complexite de lalgorithmeprecedent peut varier. Prenons par exemple Y sous forme dun tableau de boo-leens et X sous forme de liste chanee.On note n = |E| et m = ||.

Linstruction dinitialisation de Y a la ligne 1 est en O(n). La boucle de la ligne2 a 6 est executee m fois et son evaluation est en temps constant O(1). Le testdappartenance ligne 3 est en O(n) car X est sous forme dune liste chanee, de

plus il est executee m fois. Lajout dun element a un tableau de booleens, ligne4, est en temps constant. on peut conclure que la forme de la complexite de cetalgorithme est en O(mn).Choisissons maintenant X sous forme dun tableau de booleens. Linstruction dela ligne 3 devient en temps constant O(1) ; le corps de boucle de la ligne 2-6 esten temps constant et est execute m fois. Lalgorithme est alors O(m + n) ce quiest bien meilleur que la complexite precedente qui est quadratique pour m n.

8.3 Definitions complementaires

8.3.1 SymetriqueSoit G = (E, ). On appelle symetrique de G le graphe G1 = (E, 1)

defini par :x E , 1 = {y , x (y)}

Exemple i:

A

B

C

graphe G

A

B

C

symtrique de G

Graphe et son symetrique

50


52/168

Remarque: y 1(x) x (x)

Definition : Un graphe (E, ) est un graphe symetrique si 1 = .

Exemple ii:

G symetrique

A

B

C

Exemple iii:

G non symetrique

A

B

C

Fermeture symetrique

Soit G = (E, ). On appelle fermeture symetrique de G le graphe Gs =(E, s) defini par :

s(x) = (x) 1(x) x E

La fermeture symetrique forme un graphe non-oriente.

Une arete est un ensemble {x, y} (x E, y E) tel que (x, y) ou (y, x) .

Algorithme de calcul du symetrique

Donnees : (E, ),Resultat : 1.

51


53/168


54/168

8.3.3 Graphe complet

Un graphe G = (E, ) est dit complet si (x, y) E E , x = y (x, y) .

Exemple v:

G complet

A B

C

Les graphes complets a n sommets sont notes Kn.

8.4 Chemins, connexite

8.4.1 Chemins et chanes

Soit G = (E, ) et xi une famille de points de E. Un chemin de x0 a xk estdefini par (x0, x1, x2, , xk1, xk) telle que i [1, k], xi (xi1). (Chaquepoint xi du chemin est un sucesseur du point xi1 ).On definit k comme etant la longueur du chemin : cest le nombre darcs du che-min. Un chemin C est un circuit si x0 = xk.

Exemple i:

53


55/168

12

3

4

(1, 2, 1) nest pas un chemin. (1, 2, 3) est un chemin. (1, 2, 3, 1, 2, 4) est un chemin.

Chemin elementaire

Un chemin C est dit elementaire si les sommets xi sont tous distincts (saufeventuellement x0 et xk ).

Proposition : Tout chemin C de x a y dans G contient (au sens suite extraite)

un chemin elementaire de x a y dans G.Proposition : Soit G = (E, ), avec |E| = n. La longueur dun chemin elemen-taire non-circuit dans G est inferieure a n 1. De meme la longueur dun circuitelementaire est inferieure a n.

Chanes et cycles

Definition : Soit G = (E, ), et s la fermeture symetrique de . On appellechane tout chemin dans (E, s).On appelle cycle tout circuit dans (E, s) ne passant pas 2 fois par la memearete.

Exemple ii:

54


56/168

12

3

4

(4, 2, 1) nest pas un chemin. (4, 2, 1) est une chane.

Le tableau suivant resume les differentes definitions selon la nature du graphe :

Graphe oriente Graphe non-orientearc arete

chemin chanecircuit cycle

8.4.2 Composante connexe et fortement connexeComposante connexe

Definition : Soit G = (E, ) et x E. On definit Cx, la composanteconnexe de G contenant x par :

Cx = {y E , chane entre x et y} {x}

Exemple iii:

55


57/168

12

3

46

7

8

5

C1 = {1, 2, 3, 4} = C2 = C3 = C4 C5 = {5} C6 = C7 = C8

La composante connexe contenant le sommet x est lensemble des points quilest possible dattendre par une chane a partir de x.

Composante fortement connexe

Definition : Soit G = (E, ) et x E. On definit Cx, la composantefortement connexe de G contenant x par :

Cx = {y E , chemin entre x et y} {x}

Exemple iv:

Dans le graphe de lexemple precedent : C1 = {1, 2, 3, 4} = C

2 = C

3

C4 = {4} C5 = {5}

8.4.3 Calcul des composantes fortement connexes et descomposantes connexes

Definitions preliminaires

Soit un graphe G = (E, ), on definit plusieurs familles de graphes sur E :

56


58/168

0(x) = {x} 1(x) = (x)

2(x) = (

1)

p(x) = (p1)

(En utilisant la notation (X) cest a dire lensemble des sucesseurs de la partieX).De meme, on peut definir les predecesseurs 1p =

1(1p1).

Proposition : p = {y E , un chemin de x a ydans G de longueurp}Proposition : 1p = {y E , un chemin de y a x dans G de longueur p}Definition :

p =

pi=0

i

1p =

pi=0

1i

Proposition : p = {y E , un chemin de x a y dans G de longueur p}

{x}. La meme proposition sapplique aussi pour 1p . On definit aussi (x) parlensemble des y E tels quil existe un chemin de x a y dans G.La composante fortement connexe Cx de G contenant x se calcule par la formule :

Cx = 1

La composante connexe de G contenant x secrit :

Cx = s = s1

Remarque: En general s = = s1

.

Algorithme du calcul de la composante fortement connexe

Donnees : (E, , 1); a EResultat : Ca

1: (a) ; T {a};

2: while x T do

3: T T\{x}

57


59/168

4: for all y (x) tel que y / (a) do

5: (a) (a) {y}

6: T T {y}

7: end for

8: end while

9: (a) , T {a};

10: while x T do

11: T T {x}

12: for all y 1(x) tel que y / (a) do

13: (a) (a) {y}

14: T T {y}

15: end for

16: end while

17: Ca

(a) (a)

{a}

Algorithme du calcul de la composante connexe

Donnees : (E, , 1); a E Resultat : Ca

1: Ca {a} ; T {a}

2: while x T do

3: T T\{x}

4: for all y (x) tel que y / Ca do

5: Ca Ca {y}

6: T T {y}

7: end for

8: for all y 1(x) tel que y / Ca do

9: Ca Ca {y}

10: T T {y}

11: end for

12: end while

58


60/168

8.4.4 Degres

Soit un graphe G = (E, ) et un sommet x E. On definit le degre exterieur

de x, note d+(x) par :d+(x) = |(x)|

Le degre exterieur est le nombre de successeurs de x.On definit le degre interieur de G, note d(x) par :

d(x) = |1(x)|

Le degre interieur est le nombre de predecesseurs de x.

Le degre du sommet x est defini par d(x) = d+(x) + d(x). La somme des

degres de tous les sommets dun graphe G est paire.Proposition : Dans tout graphe, le nombre de sommets de degre impair est pair.

kregularite

Soit k un nombre entier positif, on dit que G est kregulier si le degre dechacun de ses sommets est egal a k.

8.5 Representation matricielle

Soit G = (E, ). G peut se representer par la matrice booleenne M = mijtelle que :

mij = 1 si j (i)mij = 0 sinon

Exemple i:

Soit le graphe G = (E, ) suivant :

2

1

4

3

59


61/168

La matrice dadjacence M associee a G est la suivante :

1 2 3 4

1 1 1 0 12 1 0 1 03 0 0 0 14 0 0 0 0

Considerons le produit booleen de matrices et les operateurs (ou binaire)et (et binaire).Soit A = aij et B = bij deux matrices booleennes, alors C = A B = [cij ] est

defini par :

cij =n

k=1

(aik bkj )

Soit Mp = M M M, p fois la matrice booleenne associee au graphe G,Mpij = 1 un chemin de longueur p dans G de i a j.

Remarque: Pour tout graphe G, il nexiste pas de nombre k N tel que Mk =

Mk+1. (Par exemple, prendre 2 points A et B et 2 arcs AB et BA.

Soit Mp = M M2 Mp ; Mpij = 1 un chemin de longueur p dansG de i a j.

Remarque: Si |E| = n alors p n 1, Mp = Mn1 = M.

8.6 Graphe biparti

On dit quun graphe G = (E, ) est biparti si lensemble E des sommets peutetre partitionne (ou colorie) en deux sous-ensembles distincts E1 et E2 de tellesorte que :

u = (x, y) ,

x E1 y E2x E2 y E1

Exemple i:

60


62/168

G1 = G2 =

1 2

3 4

5

1 2

3 4

5

On voit G1 est biparti avec E1 = {1, 4, 5} et E2 = {2, 3}. G2 nest pas biparti.

On peut montrer quun graphe est biparti si et seulement si il ne contient pascycle impair.Preuve : Soit un cycle C = x0, x1, xk avec x0 = xk puisque C est un cycle.

Dapres la definition dun graphe biparti, si x0 E1, alors x1 E2. Ainsi parreccurence, si on a xk E1, alors xk+1 E2.On peut poser que xk Ek(2)+1 cest a dire que xk appartient a lensemble Eiavec i egal a k modulo 2 (plus 1 car on a pose que x0 E1). On a alors :

xk

E1 si k pairE2 si k impair

Puisque C est un cycle, x0 = xk et donc si k impair on a xk = x0 E2 ce qui esten contradiction avec lhypothese de depart x0 E1. On ne peut donc avoir decycle de longueurs impaires dans un graphe biparti.

8.6.1 Algorithme

61


63/168

Chapitre 9

Arbre et arborescences

9.1 Definitions

9.1.1 Isthme

Soit G = (E, ), u . On dit que u est un isthme si sa suppression de augmente le nombre de composantes connexes de G.Exemple i:

AB

C

D

E

F

G

Larc u = (A, B) est un isthme.

Si u est un isthme, u nappartient a aucun cycle de G.

Proposition : Soit G = (E, ), tel que |E| = n et || = m. Si G est connexe,m n 1. Si G est sans cycle, m n 1.

9.1.2 Arbre

Un arbre est un graphe connexe et sans cycle. Une foret est un graphe sanscycle.

Remarque: Un arbre ne comporte pas de boucles. Dans un arbre, chaque arc estun isthme.

62


64/168

Proposition : Soit G = (E, ), tel que |E| = n 2 et || = m. Les proprietessuivantes sont equivalentes :

1. G est connexe et sans cycles,2. G est connexe et m = n 1,

3. G est sans cycles et m = n 1,

4. G est sans boucles et a E, b E, une chane elementaire uniqueentre a et b.

9.1.3 Racine

Soit G = (E, ), x E. x est une racine de G (resp. antiracine) si y E{x}, un chemin de x a y. (resp. y a x)

Exemple ii:

C

D

B

E

A

Ce graphe na pas de racine, et a pour antiracine B.

C

D

B

E

A

Ce graphe a pour racine D et na pas dantiracine.

9.1.4 Arborescences

G est une arborescence (resp. anti-arborescence) de racine r E si :

1. G est un arbre

2. r est une racine (resp. anti-racine) de G

63


65/168

9.1.5 Decoupage en niveau

Une arborescence peut etre decoupee en niveaux (cf figure 9.1).

Niveau 1

Niveau 2

Niveau 3

Fig. 9.1 Representation en niveaux

9.2 Exemples et applications

9.2.1 les pieces de monnaie

Soit 8 pieces de monnaies, dont une est fausse (elle est plus legere que lesautres). On possede deux balances. La balance 1 permet de savoir quel plateauest le plus lourd ; la balance 2 possede 3 etats (>,


66/168

! "# $% &'()

(1,2,3,4) (5,6,7,8)

(1,2) (3,4) (5,6) (7,8)

(1) (2) (3) (4) (5) (6) (7) (8)

1 2 3 4 5 6 7 8

Fig. 9.2 Arbre de decision de la balance 1

9.2.2 Arithmetique

On sinteresse a levaluation dexpressions arithmetiques, en respectant lespriorites des differents operateurs. Soit lexpression arithmetique (A) :

(A) =aex b(y + 1)

2

Le probleme est lordre devaluation, car a b = b a. Il est alors necessairedordonner.

Sur larbre de la figure 9.3 page suivante correpondant a lexpression (A),chaque sommet du graphe est soit une donnee (literale ou numerique), soit unoperateur. Les operateur possedent au minimum 2 successeurs (sauf operateurunaires). Les donnees nont aucun sucesseur ; ce sont les feuilles de larbre.

Arborescence ordonnee

Soit E un ensemble fini, on note O(E) lensemble des kuplets ordonneesdelements de E.

G = (E, ), ou est une application de E dans O(E) est un graphe ordonne surE.A tout graphe ordonne (E, ), on peut faire correspondre le graphe (E, ) telque (x) = { elements du kuplet (x)}. On a G = (E, ) une arborescenceordonnee (ou arborescence plane) si (E, ) est une arborescence.

65


67/168

/

2

* *

bexpa

x y 1

+

Fig. 9.3 Arbre devaluation arithmetique

9.2.3 Arbre de recherche

Soit D un ensemble appele domaine, muni dune relation dordre totale (quelon notera ). Soit X D et n D. La question que lon se pose est de savoirsi appartient a lensemble X.On peut par exemple prendre D = { lensemble des mots de la langue francaise}, X une partie de ces mots (par exemple lensemble des mots dune page web),et lon prend lordre lexicographique usuel.

Si X est represente sous forme dune liste, la resolution du probleme n X?

seffectue en O(|X|). Si X est represente sous forme dun tableau de booleen, laresolution seffectue en O(1) mais lemcombrement memoire est en O(|D|). Si Xest sous forme dune arborescence binaire, la recherche seffectue dans le pire descas en O(|X|), mais si larborescence est equilibree, la recherche est en O(log|X|).On a alors realise un index

Exemple i:

66


68/168

12

6 9

8 15

13 17

Arbre de recherche sur N, pour la relation . X = {6, 8, 9, 12, 15, 13, 17}

9.3 Arbre de poids minimum

9.3.1 Poids

Pour chaque arc , on associe une valeur, le poids de larc. Soit G = (E, ),

un graphe connexe et sans boucles. Soit P une application de R, telle queu , P(u) est appele poids de larc u.

Le graphe (E, , P) est appele graphe pondere. Soit un graphe partiel

de G, P() =

u P(u) definit le poids du graphe partiel.

Soit (E, ) un graphe partiel de G qui soit un arbre. On dit que (E, ) est un

arbre de poids maximum sur G, si tel que (E, ) soit un arbre, on a larelation suivante :

P() P()

Soit (E, ) un graphe partiel de G qui soit un arbre. On dit que (E, ) est un

arbre de poids minimum sur G, si tel que (E, ) soit un arbre, on a larelation suivante :

P() P()

Exemple i:

67


69/168

3

4

3

5

6

35

6

Un graphe pondere et son arbre de poids maximum.

Un arbre de poids maximum pour G = (E,, P) est un arbre de poids minimumpour G = (E, , P).

Remarque: On peut se demander combien darbres peut-on construire a partir

dun graphe. Cayley a apporte la reponse en 1889. Soit G = (E, ) avec |E| = n,on peut construire nn2 arbres sur G

9.3.2 Proprietes des arbres de poids maximum

Soit (E, ) un graphe connexe et sans boucle. Soit P lapplication de ponde-

ration associe a ce graphe. SoitA

tel que (E,

A) soit un arbre.On prend u un arc appartenant a mais pas A, Cu designe lensemble des arcs

de A formant une chane entre les extremites de u.On prend v un arc appartenant a A, v designe lensemble des arcs de \ A ayant

leur extremites dans 2 composantes connexes differentes de (E, A\{v}).

les 2 proprietes suivantes sont equivalentes et caracterisent un arbre de poidsmaximum :

1. u \ A, P(u) minCu P().

2. v A, P(v) maxv P().

Exemple ii:

On se propose detudier le graphe suivant :

68


70/168

v1

u1

3

2

v2 5

u3

6v3

5

u2

1

4

v4

3

u4

On veut verifier si larbre represente par les arcs en pointilles est bien un arbre

de poids maximum.

Cu1 = v1, v2 v1 = u1Cu2 = v2, v3 v2 = u1, u2, u3

Cu3 = v2, v3, v4 v3 = u2, u3, u4Cu4 = v3, v4 v4 = u3, u4

On a P(u1) = 3 > P(v1) = 2, la propriete 1 nest donc pas verifie. De plusP(v2) = 5 < P(u3) = 6, la propriete 2 nest pas verifiee. Larbre represente nestdonc pas un arbre de poids maximum

9.4 Algorithmes de Kruskal

Nous allons voir des algorithmes qui permettent dextraire les arbres de poidsmaximum dun graphe.

9.4.1 Algorithme de Kruskal-1

Soit G = (E, ) un graphe connexe et sans boucle, et P une application de

ponderation de sur R.On note = {u1, u2, un} avec i, P(ui) P(ui+1) (Les sommets sont triespar ordre decroissant).

Soit la famille i definie par :

0 =

i = i1 {ui} si (E, i1 {ui}) est sans cyclesi1 sinonAlors n est un arbre de pois maximum.Chaque i se construit en rajoutant larc ui a un nouveau graphe G

si le grapheG est sans cycle, cest a dire sil conserve ses proprietes darbre. Comme lonrajoute les arcs les plus valorisant au debut, on est sur davoir un arbre de poidsmaximum.On na pas forcement besoin de tout calculer, on peut sarreter quand |i| = n1.

69


71/168

complexite

Il faut dabord constituer une liste triee par ordre decroissant des arcs du

graphe. Cette operation seffectue au mieux en O(nlog(n)). Le test pour savoir siun graphe est sans cycles et en O(n + m). Comme ce test est realise m fois aupire, la complexite de lalgorithme de Kruskal-1 est en :

O(m(m + n) + n log(n)) = O(m(m + n))

9.4.2 Algorithme de Kruskal-2

Cette algorithme procede de facon identique, mais au lieu de construire unnouveau graphe avec les arcs les plus couteux, il procede en enlevant du graphedorigine les arcs les moins valorisants. La condition de suppression dun arc ui ne

secrit plus tant que (E, i) est sans cycle mais tant que (E, \{ui}) est connexe.Pour la meme raison, les arcs doivent etre tries par ordre croissant. La complexitede lalgorithme de Kruskal-2 est la meme que celle de Kruskal-1.

9.4.3 Algorithme de Prim

Lalgorithme de Prim fonctionne ainsi :

1: T = , A = {x E}

2:while

|T| n 1do

3: e = (u, v), tel que u A et v / A et e de cout minimal.

4: A = A {v}

5: T = T e

6: end while

70


72/168

Chapitre 10

Plus courts chemins

10.1 Definition

10.1.1 Reseau

Nous allons travailler sur un graphe sans boucle G = (E, , l) avec l lapplica-

tion poids ( R). Lapplication p associe a chaque arc un reel appele longueurde larc.(E, , l) est un reseau.

Soit = (x0, x1, xn) un chemin dans G. On definit la longueur de par :

l() =

xi,xi+1

l({xi, xi+1})

10.1.2 Plus court chemin

Soient x et y deux sommets de E. Dans la recherche dun plus court cheminde x a y, trois cas peuvent se presenter :

Il nexiste aucun chemin de x a y (si x et y appartiennent a deux compo-santes connexes differentes de G).

Il existe un chemin de x a y mais pas de plus court chemin.

Il existe un plus court chemin de x a y.Exemple i:

71


73/168

x y

2

4

1

1

2

Il nexiste pas de plus court chemin de x a y. Cest a dire que pour tout chemin de x a y, on peut trouver un chemin tel que l() < l().

Remarque: Un plus court chemin dans G = (E, , l) est un plus long chemin

dans G = (E, , l), et reciproquement.

Circuit absorbant

Un circuit de longueur negative est appele cycle absorbant. Dans lexempleprecedent, il existe un cycle absorbant.Si une composante connexe presente un cycle absorbant, alors il nexiste pas deplus court chemin entre deux points de cette composante.

Soit R = (E, , l) un reseau. Soit s E, une condition necessaire et suffisantepour quil existe un plus court chemin entre s et tout point de E\{s} est :

1. s est une racine de (E, ) et,

2. Il ny a pas de circuit absorbant dans R.

10.2 Problematique du plus court chemin

Il y a 3 problematiques a la recherche dun plus court chemin : Soient x et y deux sommets de E, trouver un plus court chemin de x a y, Soit i E, trouver les longueurs (j) des plus courts chemin de i a j,

j E\{i}.

Trouver les longueurs des plus courts chemins de i a j, i, j E.Pour resoudre le probleme (1) on doit dabord resoudre (2) avec i = x.

72


74/168

10.2.1 Graphe des plus courts chemin

Soit R = (E, , l) un reseau sans cycle absorbant, soit i E. On definit

i : E R {} definie par :i(x) = la longueur dun plus court chemin de i a x sil existei(x) = sinon

Soit (E, , l) le reseau defini par :

=

(x, y) , l({x, y}) = i(y) i(x)

(E, , l) est appele graphe des plus courts chemins de i. est constitue des arcs

faisant partie dun plus courts chemin de i a un sommet de E.Un plus court chemin de i a x dans R est un chemin de i a x dans (E, ).Exemple i:

x0 x1

x2 x3

x4

x5

x6

3

2

3

52

1

2

1

42

On peut construire lapplication x0(x)

x x0(x)x0 0x1 3x2 x3 7x4 5x5 6

x6 8Le graphe des plus court chemins est alors :

73


75/168

x0 x1

x2 x3

x4

x5

x6

3

2

1

2

1

2

Arborescence de plus courts chemins

Soit R = (E, , l) un reseau sans cycles absorbant. Soit i E et (E, ) legraphe des plus courts chemins defini precedemment. On dit que (E, A) est une

arborescence des plus courts chemins pour R si : E = {x E, i(x) = } (E, A) est une arborescence ayant pour racine le sommet i.

A

Remarque: En general une arborescence des plus courts chemins nest pas un arbrede poids minimum.

10.3 Algorithme de Floyd

Cet algorithme permet de calculer la longueur du plus court chemin dans unreseau R = (E, , l), pour tout couple de sommets (x, y). On notera Ek lensembleconstitue des k premiers sommets de E(k n). On considere la matrice L0 = (l0ij )telle que l0ii = 0 et si i = j :

l0ij =

l(i, j) si (i, j) 0 si i = j+ sinon

On considere la matrice Lk = (lkij) ou lkij represente la longueur minimum des

chemins de i a j dont les sommets intermediaires sont dans Ek.

Pour k = 0, on pose Ek = , on voit alors que L

0

correspond bien a L

k

aveck = 0. Ainsi Ln constitue la solution du probleme, cest a dire que lnij est bien lalongueur du plus court chemin de i a j dans lensemble En = E.Pour calculer Lk on utilise lequation de recurrence suivante (on supposera quele graphe est sans circuit absorbant) :

lkij = min

lk1ik + lk1kj , l

k1ij

Ce probleme peut se resoudre en utilisant la programmation dynamique. Sa com-plexite est en O(n3) (avec n = |E|) en temps de calcul, et O(n2) en memoire.

74


76/168

En effet on na pas besoin de memoriser chaque matrice Lk mais seulement lamatrice courante et la precedente.

Pour detecter la presence de circuit absorbant, il suffit de regarder sil existeun sommet x tel que l(x, x) 0. En supposant qua letat initial L0ii = 0, onapplique la relation de recurrence sur toute la matrice et lon regarde si deselements diagonaux sont inferieurs a 0.Lorsque lequation de recurrence a ete appliquee pour former les n matrices Ln,on a alors lnij qui est egal a la longueur dun plus court chemin du sommet i ausommet j (sil existe, sinon).

10.4 Algorithme de Bellman

Nous allons etudier lalgorithme de Bellman pour calculer les plus courtschemins dans un reseau a longueurs quelconques. Cet algorithme ainsi que celuide Dijkstra ne calculent pas la longueur du plus court chemin pour tout couplede point (x, y) G, mais seulement la longueur des plus courts chemin dunsommet inital i a tout autre sommet x du graphe.But : soit R = (E, , l), i E, calculer i.Lidee est quun chemin de i a x dans R passe necessairement par un y 1(x).La longueur dun plus court chemin de i a x passant par y est :

i(x) = i(y) + l(y, x)

Et donc :i(x) = min

y1(x){i(y) + l(y, x)}

10.4.1 Algorithme en pseudo language

Donnees : E, , 1, l , i EResultat : ,CIRCABS

1: CIRCABS= FAUX; 0(i) = 0 ; 1(i) = 0 ; k = 1

2: for all x E\{i} do3: 0(x) =

4: 1(x) =

5: end for

6: for all x E tel que i 1(x) do

7: 1(x) = l(i, x)

8: end for

75


77/168

9: while k < n + 1 et x E tel que k(x) = k1(x) do

10: k = k + 1

11: for all x E do12: k = min

k1(x), k1(y) + l(y, x); y 1(x)

13: end for

14: end while

15: if k = n + 1 then

16: CIRCABS= V RAI

17: end if

Cet algorithme renvoit egalement dans la variable CIRCABS la presencedun cycle absorbant.

Complexite

Linitialisation de la ligne 1 est en temps constant O(1) La boucle dinitialisation des lignes 2 a 5 est en O(n) La boucle dinitialisation des lignes 6 a 8 est en O(n + m) Le corps de boucle principale est execute n + 1 fois au maximum. La com-

plexite de levaluation de la ligne 9 est en O(n) et le corps de la boucle 9 a14 est en O(n + m).

Au total, la complexite de lalgorithme de Bellman est O(n(n + m)).Remarque: La complexite de lalgorithme de Bellman dans le cas dun graphedense (m = n2) devient O(n3).

10.4.2 Exemple dexecution

Exemple i:

76


78/168

1

2

3

4

5

6

7

8

2

2

2

2

1

4

2

3

Construisons k pas a pas pour lalgorithme de Bellman avec i = 1.

1 2 3 4 5 60 0 1 0 7 8 2 0 7 8 11 8 93 0 7 6 10 8 94 0 7 6 10 8 8

10.4.3 Justification

Lidee est que la longueur dun chemin du sommet i a nimporte quel sommetx est :

i(x) = miny1(x)

{i(y) + l(y, x)}

Cete formule locale marche pour tout le graphe, et il faut lappliquer jusqua sta-bilite (ou jusqua n iterations, dans ce cas il y a presence de cycle absorbant).

On appelle kchemin un chemin possedant au plus k arcs. Dans lalgorithme de

Bellman, ki (x) represente la longueur dun au plus kchemin de i a x (silexiste, sinon).Pour prouver cette proposition, nous allons proceder par recurrence.La propriete est trivialement verifiee pour k = 0 et k = 1. Supposons quelle estverifiee jusqua letape k 1 et placons-nous a letape k.Soit Ck lensemble des sommets y tels quil existe un kchemin de i a y.

77


79/168

Si x / Ck, y 1(x), y / Ck1. Donc dapres lequation de recurrence aletape k, k(x) = k1(y)y

1(x) = . Si x C

ket x = i alors y 1(x) tel que y C

k1. Donc

k1(y) < .

Tout kchemin de i a x passe par un y 1(x). Un plus court kcheminde i a x est compose un plus court k 1chemin de i a un sommet y 1(x)et de larc (y, x) de longueur l. Il a pour longueur k1(y) + l(y, x). Lalongueur dun plus court kchemin de i a x est donc :

miny1(x)

k1i (y) + l(y, x)

Quand il existe, un plus court chemin de i a x possede au plus n 1 arcs (avecn = |E|). En effet un plus court chemin ne peut etre quun chemin elementaire(ne comportant pas de circuit).

Si a la fin de lalgo, k n, alors x E, il existe un plus court chemin de i a x. Ilny pas de circuit absorbant. Si pour k = n + 1, x E tel que n1(x) = n(x),alors il nexiste pas de plus court chemin entre i et x, donc le graphe presente uncycle absorbant.

Remarque: Pour implementer lalgorithme de Bellman, il suffit de 2 tableaux : courant et precedent. Les acces a ces tableaux se font par exemple grace aune instruction du type k%2 ou k%2 signifie k modulo 2.

10.5 Algorithme de Dikstra

Lalgorithme de Dijkstra permet de trouver le plus court chemin dans unreseau (E, , l) sans cycle absorbant. Dans un tel reseau on a lequivalence sui-vante :

i, x E2 un chemin de i a x un plus court chemin de i a x

Lalgorithme de Dijkstra necessite egalement que tous les arcs soient positifsou nuls.

Le principe de lalgorithme est le suivant : Soit R = (E, , l), pour tout u ,l(u) 0. Soit i E sommet initial de la recherche. S designe lensemble des

sommets x de E pour lesquelles la longueur dun plus court chemin de i a x a etecalcule.Initalement S = {i}. (i) = 0.

On appelle Schemin un chemin partant de i et ayant tous ses sommets dansS sauf le dernier.Soit Y = E\S, y Y, (y) est la longueur dun plus court Schemin de i a y.On selectionne y dans Y tel que (y) = minyY

(y).

78


80/168

10.5.1 Algorithme en pseudo language

Donnees : E, , l , i E

Resultat : , S

1: S = {i}, (i) = 0, k = 1, x1 = i

2: for all x E\{i} do

3: (x) =

4: end for

5: while k < n et (xk) < do

6:for all y (xk) tel que y / S do

7: (y) = min [(y), (xk) + l(xk, y)]

8: end for

9: Extraire un sommet x / S tel que (x) = min[(y)y / S]

10: k = k + 1, xk = x, S = S {xk}.

11: end while

Complexite

Nous prendrons S sous la forme dun tableau de booleen Les boucles dinitialisation des ligne 1 et 2 a 4 sont en O(n) Le corps de la boucle principale (ligne 5 a 11) est execute n fois.

La complexite de lalgorithme de Dijsktra est en O(n2).

10.5.2 Exemple dexecution

Exemple i:

79


81/168

a

b

c

d

e

f

2

8

5

3

1

41

1

1

1

Construisons S pas a pas pour lalgorithme de Dijkstra avec i = a.

S k x y{a} 1 a b, c

{a, b} 2 b c, d{a,b,d} 3 d c, e, f

{a,b,d,f} 4 f /{a,b,c,d,f} 5 c e

{a,b,c,d,e,f} 6 e /A la fin de lalgo, les valeurs des couts des plus courts chemins sont :

Sommet a b c d e f Cout 0 2 5 3 7 4

10.6 Plus courts chemins (Exploration largeur)

Nous nous placons dans le cas dun reseau R = (E, , l) tel que pour tout

arc u dans , lapplication de ponderation soit egale a une constante strictementpositive. On prendra l(u) = c = 1.

Pour trouver la longueur du plus court chemin dun sommet i a tout autresommet x (sil existe), il existe un algorithme en temps lineaire O(n+m) se basantsur la propriete de constance de lapplication de ponderation. Cest lalgorithmedit dexploration-largeur.Il consiste a parcourir le graphe par couches successives a partir de i et deproche en proche selon ses sucesseurs. La longueur du plus court chemin a x estalors le nombre minimal de couches parcourues pour aller de i a x (multiplie parla constante c).

80


82/168

10.6.1 Algorithme en pseudo langage

On prendra pour cet algorithme l(u) = 1u

Donnees : E, , i EResultat : , S

1: (i) = 0, S = {i}, T = 0, k = 1

2: for all x E do

3: (x) =

4: end for

5: while S = do

6: for all x S do

7: for all y (x) tel que (y) = do

8: (y) = k

9: T = T {y}

10: end for

11: end for

12: S = T, T = 0

13: k = k + 1

14: end while

10.7 Graphes sans circuits : GSC

10.7.1 Definit

Documents

ProgDynamique