Variables et types
4 (+1) types de base :
•Booléens : True, False
•Entiers
•Flottants
•Caractères
•Pointeurs
On construit d’autres types :
•Listes
•Tableaux
•Chaînes de caractères
•Etc.
Variables et types Variable : quelque chose en mémoire, d’un des types précédents
Opérations :
•Initialiser (Obligatoire)
•Modifier sa valeur
•La supprimer
•Exemple :
fct inutile ():
a ← 0 # initialisation
a ← 1
return a
Syntaxe du pseudo-code
•Affecta4ons : ← , pas =
•Comparaisons : =, ≠, ≤, ≥, etc.
•Pour une fonction : fct nom_de _la fonction (arguments)
•On termine avec : return
•Délimiteurs : indentation (comme en Python)
Syntaxe du pseudo-code
•Structures de contrôle : if, for, while
•Opérateurs logiques sur les booléens : and, or, not, xor
•Pour s’amuser :
a ← 5
b ← 4
res ← ( a = b ) xor a < 10 )
Structure des données
•Piles (FILO ou LIFO)
•Files (FIFO)
•Files de priorité
•Dictionnaires
•Ensembles
•Arbres
•Graphes
Attention
•Les « listes » de Python ne sont ni des piles, ni des files, ni des tableaux,
ni des listes
•Elles ont une structure hybride, mélangeant les propriétés des
structures de données précédentes
Piles•Priorité LIFO ou FILO
•Push()
•Pop()
Exemple :
res ← CreerPileVide() # res=[]
res.push(n) # res=[n]
res.push(p) #res=[p,n]
tmp ← res.pop() # tmp=p ; res=[n]
Push
Pop
Files•Priorité FIFO
•Enqueue()
•Dequeue()
Exemple :
res ← CreerFileVide() # res=[]
res.enqueue(n) # res=[n]
res.enqueue(p) #res=[p,n]
tmp ← res.dequeue () # tmp=n ; res=[p]
Enqueue Dequeue
Files et piles en pratique•Pile : liste chaînée
•File : liste double-chaînée
Files de priorité•Un élément : (valeur, priorité)
•Ordre dans la file : donné par la priorité
•Créer_file_de_priorite_vide()
•Enqueue()
•Dequeue()
•Enqueue en O( log(n) ) ou O(n)
•Dequeue en O ( log(n) )
Enqueue Dequeue2 5 7 91
Enqueue4
Implémentation par tas maximum
•Invariant de tas : fils ≤ père
•D ≤ B et E ≤ B
•F ≤ C
•B ≤ A et C ≤ A
A
B C
D E F
Enqueue
9
7
4 2 1 8
5
Enqueue
9
8
4 2 1 7
5
Dequeue
9
8
4 2 1 7
5
Dequeue
9
8
4 2 1 7
5
Dequeue
7
8
4 2 1
5
Dequeue
7
8
4 2 1
5
Dequeue
8
7
4 2 1
5
Tableaux•Un élément : une valeur repérée par son indice
•Creer_tableau( taille )
•Accéder à un élément
•Modifier un élément
•Intérêt :
� Rapide
� semblable aux vecteurs/matrices
•/!\ : la multiplication usuelle est la multiplication terme à terme
Tableaux : un exemplefct exemple (n) :
res ← creer_tableau(n)
res[0] ← 1
for i=1 to n-1 :
res[i] ← 2 * res[i-1]
return res
Dictionnaires•Un élément : (clé : valeur)
•Add( clé : valeur )
•Pop( clé )
•Accès comme sur un tableau : dict[ clé ]
•Add en O(1)
•Accès et Pop en O( 1 + α ) (α : taux de remplissage du dictionnaire)
•Intérêt :
� Indexer par autre chose que des entiers
� De taille variable
Dictionnaires : un exemplecita4ons ← { ‘Hervé Biausser’ : ‘Nous sommes la meilleure école
d’ingénieurs de France.’ ; ‘John Cagnol’ : ‘Vous pensez aller où comme ça
?’ }
citations.add( ‘Luca Pacioli’ : ‘Résultat et trésorerie ne sont pas
synonymes.’ )
citations[ ‘John Cagnol’ ]
>>> ‘Vous pensez aller où comme ça ?’
Ensembles•Comme en mathématiques
•Opérations ensemblistes usuelles
•AUB en O( #(AUB) )
•A∩B en O( #(AUB) )
Syntaxe du pseudo-code•Listes, files, files de priorité : variable.méthode( argument_si_besoin )
•Tableaux : tab[indice]
•Dictionnaires : dict.add( clé : valeur ), dict.pop( clé ), dict[ clé ]
•Ensembles
Compléxité•Tn = O(f)
•Tn = Ω(f) ssi f = O(Tn)
•Tn = Ɵ(f) ssi Tn = O(f) et f = O(Tn)
En pratique, on utilise pour f :
•1•log2(n)
•n•n.log2(n)
•n2, n3…
•2n et pire…
Compléxité : exemplesfct fact (n) :
res ← 1
for i=1 to n :
res ← res * i
return res
fct fact_rec (n) :
if n=0 or n=1 :
return 1
else :
return n * fact_rec(n-1)
Compléxité : exemplesfct mult (vect_A, vect_B) :
n ← vect_A.taille()
res ← matrice(n,n)
for i=1 to n :
for j=1 to n :
res[i][j] ← vect_A[i] * vect_B[j]
return res
Compléxité : les réflexes à avoir
•On ne cherche que des ordres de grandeur, asymptotiquement
•C’est plus simple avec un O qu’avec Ɵ, mais moins précis
•2 complexités : temporelle (par défaut, la plus courante) et spatiale
•En général :
�1 boucle : O(n)
�2 boucles imbriquées : O(n2)
•On n’aime pas les complexités exponentielles.
Complexité : le réflexeSi la question demande une complexité en n.log(n) :
Il existe des tris en n.log(n)
C’est souvent un tri des données qu’il faut utiliser
Quelques conseils
•Expliquer l’idée, le principe d’un algorithme avant de l’écrire
•Commenter le code (de préférence d’une autre couleur)
•Donner des noms explicites aux variables
•Attention aux collisions (espaces de noms réservé)
�Exemple : “mini” et pas “a”, ni “min”
•Soigner la présentation (indentation, laisser des espaces…)
Méthodes vues en cours
Méthode gloutonneMéthode récursiveDiviser pour mieux régnerProgrammation dynamique
Méthodes vues en cours
Méthode gloutonneMéthode récursiveDiviser pour régnerProgrammation dynamique
Méthode gloutonne
Principe : Construction d’une solution par une suite de choix optimaux localement, sans retour en arrière ni exploration de plusieurs possibilités
Méthode gloutonne
Méthode souvent simple voire intuitiveRésout un problème rapidement (complexité faible)Ne donne pas nécessairement la solution optimale
Principe : Construction d’une solution par une suite de choix optimaux localement, sans retour en arrière ni exploration de plusieurs possibilités
Exemple : vous avez une courbe, vous voulez un algorithme qui vous en donne un maximum
Qu’est-ce que vous faites ?
Exemple : vous avez une courbe, vous voulez un algorithme qui vous en donne un maximum
Qu’est-ce que vous faites ?
Vous vous placez en un point, et vous cherchez à monter jusqu’à ce que vous ne puissiez plus monter plus haut.
Exemple : vous avez une courbe, vous voulez un algorithme qui vous en donne un maximum
Qu’est-ce que vous faites ?
Vous vous placez en un point, et vous cherchez à monter jusqu’à ce que vous ne puissiez plus monter plus haut.
Et comment choisir par quel côté monter ?
Exemple : vous avez une courbe, vous voulez un algorithme qui vous en donne un maximum
Qu’est-ce que vous faites ?
Vous vous placez en un point, et vous cherchez à monter jusqu’à ce que vous ne puissiez plus monter plus haut.
Et comment choisir par quel côté monter ?
A chaque itération, vous montez du côté où la pente est la plus forte
En partant de A avec cette méthode : en quel point arrive-t-on ?
En partant de A avec cette méthode : en quel point arrive-t-on ?
En partant de A avec cette méthode : en quel point arrive-t-on ?
On a trouvé un maximum
MAIS
Ce n’est pas le meilleur maximum
Exemple : le rendu de monnaie
on dispose d’un système monétaireon doit rendre une certaine somme en utilisant cette monnaieon cherche à minimiser le nombre de pièces utilisées
ex : en eurosS = (1 ; 2 ; 5 ; 10 ; 20 ; 50)
rendre 18 =
Exemple : le rendu de monnaie
on dispose d’un système monétaireon doit rendre une certaine somme en utilisant cette monnaieon cherche à minimiser le nombre de pièces utilisées
ex : en eurosS = (1 ; 2 ; 5 ; 10 ; 20 ; 50)
rendre 18 = 10 + 5 + 2 + 1
Exemple : le rendu de monnaie
on dispose d’un système monétaireon doit rendre une certaine somme en utilisant cette monnaieon cherche à minimiser le nombre de pièces utilisées
ex : en eurosS = (1 ; 2 ; 5 ; 10 ; 20 ; 50)
rendre 18 = 10 + 5 + 2 + 1
ex : en monnaie plus exotiqueS = (1 ; 3 ; 7 ; 19 ; 51)
rendre 18 =
Exemple : le rendu de monnaie
on dispose d’un système monétaireon doit rendre une certaine somme en utilisant cette monnaieon cherche à minimiser le nombre de pièces utilisées
ex : en eurosS = (1 ; 2 ; 5 ; 10 ; 20 ; 50)
rendre 18 = 10 + 5 + 2 + 1
ex : en monnaie plus exotiqueS = (1 ; 3 ; 7 ; 19 ; 51)
rendre 18 = 7 + 7 + 3 + 1
Plutôt facile, vous le faites naturellement à chaque fois que vous rendez la monnaie.Quel algorithme utilisez-vous intuitivement pour trouver ces réponses ?
Vous prenez la pièce la plus grande qui ne dépasse pas le montant à rembourserVous la donnez, il vous reste maintenant une somme plus petite à rembourserVous recommencez
Par exemple : Je dois 18€
Vous prenez la pièce la plus grande qui ne dépasse pas le montant à rembourserVous la donnez, il vous reste maintenant une somme plus petite à rembourserVous recommencez
ETAPE 1 :Plus grande pièce : 10€Je dois : 18 - 10 = 8€
Par exemple : Je dois 18€
Vous prenez la pièce la plus grande qui ne dépasse pas le montant à rembourserVous la donnez, il vous reste maintenant une somme plus petite à rembourserVous recommencez
ETAPE 1 :Plus grande pièce : 10€Je dois : 18 - 10 = 8€
ETAPE 2 :Plus grande pièce : 5€Je dois : 8 - 5 = 3€
Par exemple : Je dois 18€
Vous prenez la pièce la plus grande qui ne dépasse pas le montant à rembourserVous la donnez, il vous reste maintenant une somme plus petite à rembourserVous recommencez
ETAPE 1 :Plus grande pièce : 10€Je dois : 18 - 10 = 8€
ETAPE 2 :Plus grande pièce : 5€Je dois : 8 - 5 = 3€
ETAPE 3 :Plus grande pièce : 2€Je dois : 3 - 2 = 1€
Par exemple : Je dois 18€
Vous prenez la pièce la plus grande qui ne dépasse pas le montant à rembourserVous la donnez, il vous reste maintenant une somme plus petite à rembourserVous recommencez
ETAPE 1 :Plus grande pièce : 10€Je dois : 18 - 10 = 8€
ETAPE 2 :Plus grande pièce : 5€Je dois : 8 - 5 = 3€
ETAPE 3 :Plus grande pièce : 2€Je dois : 3 - 2 = 1€
ETAPE 4 :Plus grande pièce : 1€Je dois : 1 - 1 = 0€
Par exemple : Je dois 18€
C’est fini !
fct rendu_monnaie_glouton(v,S):
n ← S.longueur()
solution ← créer_pile_vide()
while v=!0 :
p ← plus_grande_pièce(v,S)
v ← v–p
solution.push(p)
return solution
Arguments :v est la valeur à rendre, un entier positifS est un tableau contenant les valeurs du système monétaire
fct plus_grande_pièce(v,S):
n ← S.longueur()-1
p ← S[n]
while v<p and n≥0
n ← n-1
p ← S[n]
return p
Arguments :v est la valeur à rendre, un entier positifS est un tableau contenant les valeurs du système monétaire
Quelles sont les limites de la méthode gloutonne ?
Quelles sont les limites de la méthode gloutonne ?
Elle ne rend pas systématiquement la solution optimale
Quelles sont les limites de la méthode gloutonne ?
Elle ne rend pas systématiquement la solution optimale
Dans notre système monétaire, c’est pourtant le cas : il est canonique.Prenons l’exemple d’un autre système :
S = (1 ; 3 ; 4)rendre 6 = 4 + 1 + 1
une solution optimale aurait été 6 = 3 + 3
Quelles sont les limites de la méthode gloutonne ?
Elle ne rend pas systématiquement la solution optimale
Dans notre système monétaire, c’est pourtant le cas : il est canonique.Prenons l’exemple d’un autre système :
S = (1 ; 3 ; 4)rendre 6 = 4 + 1 + 1
une solution optimale aurait été 6 = 3 + 3
Cependant, on trouve une solution généralement satisfaisante en peu de temps
Méthodes vues en cours
Méthode gloutonneMéthode récursiveDiviser pour régnerProgrammation dynamique
Récursivité
Principe : la fonction s’appelle elle-même, mais sur un problème plus simple à chaque itération jusqu’à atteindre une condition d’arrêt
Récursivité
Principe : la fonction s’appelle elle-même, mais sur un problème plus simple à chaque itération jusqu’à atteindre une condition d’arrêt
fct factorielle(n)
if n=1 or n=0
return 1
else
return n*factorielle(n-1)
Exemple : la fonction factorielle
L’algorithme du rendu de monnaie en récursif :
L’algorithme du rendu de monnaie en récursif :
fct rendu_monnaie_recursif(v,S,solution)
n ← S.longueur()-1
p ← S[n]
if v=0
return solution
else
while v>p
v ← v-p
solution.push(p)
return rendu_monnaie_recursif(v,S[0:n-1],solution)
Arguments : v est un entier positifS est un tableau contenant les valeurs du système monétairesolution est une pile vide
On remarque que l’algorithme précédent était à la fois récursif et glouton
On remarque que l’algorithme précédent était à la fois récursif et glouton
Le récursivité est plus un choix de style qu’une véritable méthode de programmationEn général, elle est équivalente aux boucles while/for
Cependant, n’hésitez pas à la privilégier aux boucles car il est souvent plus aisé d’en vérifier la terminaison et la complexité
Méthodes vues en cours
Méthode gloutonneMéthode récursiveDiviser pour régnerProgrammation dynamique
Diviser pour régner
Principe : Le problème est divisé en sous-problèmes, et on choisit de n’en traiter qu’une partie
Diviser pour régner
Principe : Le problème est divisé en sous-problèmes, et on choisit de n’en traiter qu’une partie
Exemple :la dichotomie
fct dichotomie(L,a)
n ← L.longueur()
if n=1
return L[0]
else
if L[n//2]>a
return dichotomie(L[0:(n//2)-1],a)
else
return dichotomie(L[n//2:n-1],a)
Chiffre choisi : 7
Chiffre choisi : 7
Premier pivot : 6
Chiffre choisi : 7
Premier pivot : 6
Plus grand ? nonOn en élimine 5
Chiffre choisi : 7
Premier pivot : 6
Plus grand ? nonOn en élimine 5
Deuxième pivot : 8
Chiffre choisi : 7
Premier pivot : 6
Plus grand ? nonOn en élimine 5
Deuxième pivot : 8
Plus grand ? ouiOn en élimine 3
Situation précédente :
Situation précédente :
Troisième pivot : 7
Situation précédente :
Troisième pivot : 7
Plus grand ? nonOn en élimine un
Situation précédente :
Troisième pivot : 7
Plus grand ? nonOn en élimine un
La liste restante est de longueur 1, c’est fini !
A chaque étape, on a abandonné une moitié du problème
Le tri rapideUn autre exemple :
Le tri rapide
Complexité en nlog(n)
Principe : choix d’un pivotséparation de la liste en deux : la partie avant le pivot, et celle aprèstri des deux sous-listesconcaténation des sous-listes
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Théorème maîtres’applique dans le cadre du “diviser pour régner” uniquement
énoncé : dans le cas d’un problème de dimension n, résolu par un algorithme qui le divise en a sous-problèmes de taille n/b, on a :
avec f la complexité de la division puis recombinaison du problème
f(n)
f(n/b) f(n/b) f(n/b)
… … … … … … … … …
O(1) O(1) O(1) O(1) O(1) O(1) O(1)
a = 3
Théorème maîtres’applique dans le cadre du “diviser pour régner” uniquement
énoncé : dans le cas d’un problème de dimension n, résolu par un algorithme qui le divise en a sous-problèmes de taille n/b, on a :
avec f la complexité de la division puis recombinaison du problème
Théorème maîtres’applique dans le cadre du “diviser pour régner” uniquement
énoncé : dans le cas d’un problème de dimension n, résolu par un algorithme qui le divise en a sous-problèmes de taille n/b, on a :
avec f la complexité de la division puis recombinaison du problème
on a : si et alors
si et alors
si et alors
et pour n assez grand,
Mais qui est f ?
Mais qui est f ?
f est le coût de gestion en dehors des appels récursifsc’est-à-dire la complexité de tout ce qui n’est pas lié à l’appel de la fonction
Pour bien comprendre, prenons un exemple.
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Qu’est-ce qui est lié à l’appel récursif ?
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Qu’est-ce qui est lié à l’appel récursif ?
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Le tri rapide
Qu’est-ce qui est lié à l’appel récursif ?
Que vaut donc f ?
Le tri rapide
Qu’est-ce qui est lié à l’appel récursif ?
Que vaut donc f ?
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Le tri rapide
Qu’est-ce qui est lié à l’appel récursif ?
Que vaut donc f ?
On doit donc calculer la complexité de ces fonctions annexes
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2 Concaténation : en O(n)
Fonctions annexes
fct plus_grand_strict_que_le_pivot(pivot,T)
n ← T.longueur()
i ← 0
S ← créer_tableau(n,0)
for element in T
if element > pivot
S[i] ← element
i ← i + 1
return S[0:i]
fct plus_grand_strict_que_le_pivot(pivot,T)
n ← T.longueur()
i ← 0
S ← créer_tableau(n,0)
for element in T
if element > pivot
S[i] ← element
i ← i + 1
return S[0:i]
Fonctions annexes
une boucle for
Complexité en O(n)
Le tri rapide
On a trouvé f(n), quelle est la suite ?
f(n) = O(n)
Théorème maîtres’applique dans le cadre du “diviser pour régner” uniquement
énoncé : dans le cas d’un problème de dimension n, résolu par un algorithme qui le divise en a sous-problèmes de taille n/b, on a :
avec f la complexité de la division puis recombinaison du problème
on a : si et alors
si et alors
si et alors
et pour n assez grand,
Le tri rapide
On a trouvé f(n), quelle est la suite ?
f(n) = O(n)
log𝑏(𝑎) ?
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
Le tri rapide
fct tri_rapide(T)
n ← T.longueur()
if n=1
return T
else
pivot ← T[0]
T1 ← plus_petit_que_le_pivot(pivot,T[1:n-1])
T2 ← plus_grand_strict_que_le_pivot(pivot,T[1:n-1])
tri1 ← tri_rapide(T1)
tri2 ← tri_rapide(T2)
return tri1 + [pivot] + tri2
On a deux listes, de taille moyenne n/2
a=2b=2
Le tri rapide
On a trouvé f(n), quelle est la suite ?
f(n) = O(n)
log𝑏(𝑎) = log2(2) = 1
On est donc dans le cas 2 avec k = 0 donc…
Théorème maîtres’applique dans le cadre du “diviser pour régner” uniquement
énoncé : dans le cas d’un problème de dimension n, résolu par un algorithme qui le divise en a sous-problèmes de taille n/b, on a :
avec f la complexité de la division puis recombinaison du problème
on a : si et alors
si et alors
si et alors
et pour n assez grand,
Le tri rapide
On a trouvé f(n), quelle est la suite ?
f(n) = O(n)
log𝑏(𝑎) = log2(2) = 1
On est donc dans le cas 2 avec k = 0 donc…
Le tri rapide
On a trouvé f(n), quelle est la suite ?
f(n) = O(n)
log𝑏(𝑎) = log2(2) = 1
On est donc dans le cas 2 avec k = 0 donc…
On retrouve la fameuse complexité en nlog(n) !
Méthodes vues en cours
Méthode gloutonneMéthode récursiveDiviser pour régnerProgrammation dynamique
Programmation dynamique
Principe : on cherche la solution la plus optimale au problème, en divisant le problème en sous-problèmes et en cherchant la solution optimale pour chacun d’eux
« toute politique optimale est composée de sous-politiques optimales »Richard Bellman
Programmation dynamique
Principe : on cherche la solution la plus optimale au problème, en divisant le problème en sous-problèmes et en cherchant la solution optimale pour chacun d’eux
Quelle différence avec diviser pour régner ?
« toute politique optimale est composée de sous-politiques optimales »Richard Bellman
Programmation dynamique
Principe : on cherche la solution la plus optimale au problème, en divisant le problème en sous-problèmes et en cherchant la solution optimale pour chacun d’eux
Quelle différence avec diviser pour régner ?
« toute politique optimale est composée de sous-politiques optimales »Richard Bellman
Les sous-problèmes ne sont pas nécessairement indépendants !
Qu’est-ce que ça veut dire ?
mettons qu’on veuille calculer 3 parmi 5 en utilisant le triangle de Pascal, on a :
si on veut le calculer simplement par “diviser pour régner”, qu’est-ce qui se passe ?
fct Pascal(k,n)
if k=0 or k=n
return 1
else
return Pascal(k-1,n-1)+Pascal(k-1,n)
Calcul de k parmi n
l’algorithme veut calculer : il fait appel à lui-même et calcule et
Pour calculer , il calcule et
Pour calculer , il calcule et
5
2
4
2
5
3
fct Pascal(k,n)
if k=0 or k=n
return 1
else
return Pascal(k-1,n-1)+Pascal(k-1,n)
5
2
4
2
5
1
4
1
4
1
3
1
Calcul de k parmi n
Quel est l’inconvénient de l’algorithme utilisé ?
5
3
5
1
5
2
4
1
3
1
4
2
4
1
Quel est l’inconvénient de l’algorithme utilisé ?
5
3
5
1
5
2
4
1
3
1
4
2
4
1
Le calcul de 1 parmi 4 est effectué deux fois !
Quelle serait la solution ?
5
3
5
1
5
2
3
1
4
2
4
1
Faire en sorte que cette valeur soit stockée en mémoireEt réutilisée pour le calcul de la deuxième branche
fct Pascal_dynamique(k,n)
T ← créer_matrice(k,n,0)
for i=0 to n
T[0][i] ← 1
T[i][i] ← 1
for j=0 to n
i=1
while i≤k and i<n
T[i][j] ← T[i-1][j-1]+T[i-1][j]
i ← i+1
return T[k][n]
Le triangle de Pascal en programmation dynamique :
Un autre exemple : la pyramide de nombre
Objectif : En partant du sommet, arriver à la base en maximisant le total des nombres traversés
comment feriez-vous avec un algorithme glouton ?
Solution de cette pyramide :
Total : 3 + 7 + 4 + 9 = 23
On choisit le plus grand nombre à chaque embranchement
Pour le sommet :on n’a pas le choix
On choisit le plus grand nombre à chaque embranchement
Pour le sommet :on n’a pas le choix
7 > 4 donc on choisitd‘aller à gauche
On choisit le plus grand nombre à chaque embranchement
Pour le sommet :on n’a pas le choix
7 > 4 donc on choisitd‘aller à gauche
4 > 2 donc on choisit d’aller à droite
On choisit le plus grand nombre à chaque embranchement
Pour le sommet :on n’a pas le choix
7 > 4 donc on choisitd‘aller à gauche
4 > 2 donc on choisit d’aller à droite
9 > 5 donc on choisitd‘aller à droite
On remarque qu’on a trouvé la solution optimale. Est-ce toujours le cas ?
Non ! La méthode gloutonne donne une solution "presque" optimale
Par exemple :
Non ! La méthode gloutonne donne une solution "presque" optimale
Par exemple :
Algorithme glouton : 19
Non ! La méthode gloutonne donne une solution "presque" optimale
Par exemple :
Algorithme glouton : 19 Solution optimale : 23
Première solution : algorithme naïf
Comment trouver la solution optimale ?
Première solution : algorithme naïf
on parcourt toutes les branches et on voit ce que donne chaque possibilité
Comment trouver la solution optimale ?
Première solution : algorithme naïf
on parcourt toutes les branches et on voit ce que donne chaque possibilité
Quelle est sa complexité ?
Comment trouver la solution optimale ?
Première solution : algorithme naïf
on parcourt toutes les branches et on voit ce que donne chaque possibilité
Quelle est sa complexité ?
Si on note n la hauteur de la pyramide, il y a2^(n-1) chemins possibles, on a donc une complexité exponentielle…
Comment trouver la solution optimale ?
Première solution : algorithme naïf
on parcourt toutes les branches et on voit ce que donne chaque possibilité
Quelle est sa complexité ?
Si on note n la hauteur de la pyramide, il y a2^(n-1) chemins possibles, on a donc une complexité exponentielle…
On peut mieux faire.
Comment trouver la solution optimale ?
Solution :
Programmation dynamique
Comme pour le calcul de k parmi n, on remarque que certains calculs sont exécutés
plusieurs fois
Programmation dynamique
Comme pour le calcul de k parmi n, on remarque que certains calculs sont exécutés
plusieurs fois
Programmation dynamique
Astuce : ne pas partir du sommet mais de la base de la pyramide
Certains calculs sont inutiles
Quel que soit le chemin choisi pourarriver en 4…
Certains calculs sont inutiles
… les chemins possibles à partir de 4 sontLes même
Quel que soit le chemin choisi pourarriver en 4…
Certains calculs sont inutiles
… les chemins possibles à partir de 4 sontLes même
Quel que soit le chemin choisi pourarriver en 4…
On ne va donc pas s’intéresser aux chemins menant à 4 !
On garde juste en mémoire la valeur du meilleur chemin possible pour arriver en 4
On garde juste en mémoire la valeur du meilleur chemin possible pour arriver en 4
Ici, c’est celui de gauche : on remplace donc 4 par 9 = 4+5
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
Et on obtient…
… 23 : on a bien trouvé le résultat optimal en seulement 7 étapes !
Programmation dynamique
Procédé permettant de trouver une solution optimale
Programmation dynamique
Procédé permettant de trouver une solution optimale
Fonctionne bien lorsque le problème est basé sur des sous-problèmes identiques
Programmation dynamique
Procédé permettant de trouver une solution optimale
Fonctionne bien lorsque le problème est basé sur des sous-problèmes identiques
Calcul ascendant : on part des sous-problèmes les plus petits
Programmation dynamique
Procédé permettant de trouver une solution optimale
Fonctionne bien lorsque le problème est basé sur des sous-problèmes identiques
Calcul ascendant : on part des sous-problèmes les plus petits
On les stock dans un tableau
Petit bilan :
Petit bilan :
A utiliser quand vous cherchez un optimum local et non global
Donne un résultat rapidement et simplement
Méthode gloutonne
Petit bilan :
A utiliser quand vous voulez
A privilégier dans beaucoup de cas car la terminaison et la complexité sont plus simples à démontrer
A utiliser quand vous cherchez un optimum local et non global
Donne un résultat rapidement et simplement
Méthode gloutonne Récursion
Petit bilan :
A utiliser quand vous pouvez scinder le problème en sous-problèmes indépendants
Penser au Théorème Maître et à la complexité en nlog(n) du tri rapide
A utiliser quand vous voulez
A privilégier dans beaucoup de cas car la terminaison et la complexité sont plus simples à démontrer
A utiliser quand vous cherchez un optimum local et non global
Donne un résultat rapidement et simplement
Méthode gloutonne Récursion
Diviser pour régner
Petit bilan :
A utiliser quand vous cherchez un optimum globalETque vous pouvez scinder le problème en sous-problèmes dépendants
A utiliser quand vous pouvez scinder le problème en sous-problèmes indépendants
Penser au Théorème Maître et à la complexité en nlog(n) du tri rapide
A utiliser quand vous voulez
A privilégier dans beaucoup de cas car la terminaison et la complexité sont plus simples à démontrer
A utiliser quand vous cherchez un optimum local et non global
Donne un résultat rapidement et simplement
Méthode gloutonne
Programmation dynamique
Récursion
Diviser pour régner
GRAPHES ET ALGORITHMES- GRAPHES
- ARBRES
- REPRÉSENTATION MACHINE
- PARCOURS ET RECOUVREMENT
LES GRAPHESGRAPHES
ARBRES
Un graphe ? C’est quoi ?Formellement : Un couple G = (V,E) où V (vertices) représente les sommets et E (edges) représente les arêtes entre chaque sommet
En SI , les réseaux sont souvent représentés par des graphes
Réseaux routiers, …
Différents types de graphes
Exemple : Amis facebookNous avons 5 personnes : A,B,C,D et E
Les personnes mises en amis sur Facebook sont reliées par une arête
Si le lien d’amitié est important (copine, famille, etc) , l’arête est pondérée à 2
Propriétés et vocabulaire des graphesDegré (d’un sommet) : nombre d’arête auxquelles appartiennent le sommet
Adjacence : Reliés par une arête
Chemin : Suite de sommet reliant deux sommets
Longueur : somme des poids d’un chemin
Cycle : Chemin entre un sommet et lui-même (sans repasser par la même arête)
Différence connexe / fortement connexe :
- Connexe : Graphe non orienté ; tout les sommets sont reliés par un chemin
- Fortement connexe : Graphe orienté ; tout les sommets sont reliés par un chemin
Composante connexe : Sous-graphe connexe d’un graphe général
Un type particulier de graphe :Les arbres
Un arbre est un graphe connexe , acyclique et non orienté souvent doté d’un sommet particulier appelé racine. Chaque sommet est appelé un nœud
Vocabulaire des Arbres :
Racine : Nœud sans antécédent
Feuille : Nœud sans successeur
Forêt : Chaque nœud a au plus un antécédent
Arborescence : Arbre avec une unique racine
Profondeur d’un nœud : Distance à la racine
Hauteur d’un arbre : Plus grande hauteur entre une feuille et la racine
Exemple d’arbre
Arbre de type Forêt , Arborescence
Feuilles = F1, … , F13
Exemple d’arbre
Arbre de type Forêt , Arborescence
Feuilles = F1, … , F13
Profondeur de F8 = 3
Exemple d’arbre
Arbre de type Forêt , Arborescence
Feuilles = F1, … , F13
Profondeur de F8 = 3
Hauteur de l’arbre = 5
Exemple d’arbre
Arbre de type Forêt , Arborescence
Feuilles = F1, … , F13
Profondeur de F8 = 3
Hauteur de l’arbre = 5
Profondeur entre les Nœuds A et B = 2
Propriétés et Arbres particuliersChaque nœud est accessible depuis la racine par un chemin unique
ARBRES PARTICULIERS:
Arbre binaire
Arbre binaire de recherche
Arbre équilibré
Arbre complet
Arbre presque complet
ARBRE BINAIRE
Chaque nœud a au plus deux successeurs
Soit h la hauteur et N le nombre de nœuds :
On a toujours : ℎ ≤ 𝑁 ≤ 2ℎ − 1
ARBRE BINAIRE DE RECHERCHE
C’est un arbre binaire ordonné :
Le fils gauche a toujours une valeur inférieur au père,
Le fils droit une valeur supérieur au père.
Rechercher une valeur dans un tel arbre est très facile !
ARBRE équilibréA chaque nœud, la différence de profondeur entre les sous arbres n’excède pas 1
Graphe équilibré
Graphe non équilibré
ARBRE Complet
Un arbre est complet si toutes les feuilles sont à la profondeur h depuis la racine
Tout les nœuds ont une profondeur 3 depuis la racine
ARBRE PRESQUE COMPLETSoit un arbre de F feuilles. Soit 1 ≤ 𝑝 ≤ 𝐹:
Les p premières feuilles ont une profondeur h depuis la racine
Les autres ont une profondeur h-1 depuis la racine
Exemple d’arbre presque complet :En gros , tout les étages sont pleins sauf le dernier
IMPLEMENTATION DES GRAPHES
MATRICE D’ADJACENCE
0 1 1 1 1 01 0 1 0 0 01 1 0 1 0 11 0 1 0 0 01 0 0 0 0 10 0 1 0 1 0
A B C D E F
F E
D
C
B
A
Si u et v sont lié ,M(u,v)=M(v,u)=1Sinon M(u,v)=M(v,u)=0
Complexité spatiale en 𝑂(|𝑉|2)
Liste d’adjacence
Ordre : A,B,C,D,E,F
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,E
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,EB A,C
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,EB A,CC A,B,D,F
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,EB A,CC A,B,D,FD A,C
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,EB A,CC A,B,D,FD A,CE A,F
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,EB A,CC A,B,D,FD A,CE A,FF C,E
Liste d’adjacence
Ordre : A,B,C,D,E,FVoisins:A B,C,D,EB A,CC A,B,D,FD A,CE A,FF C,E
Liste d’adjacence du graphe :[ [ B,C,D,E ] , [ A,C ] , [ A,B,D,F ] , [ A,C ] , [ A,F ] , [ C,E ]]
Complexité spatiale en 𝑂(2|𝐸|)
Implémentation des arbres
Principe du même genre que liste d’adjacence :
Liste de relation père/fils (antécédent/successeur)
Racine[ fils1[ . , . ] , fils2[ . , . ] ]
Implémentation des arbres
4[]6[]5[]4[]
On crée d’abord les feuilles :
4, 5, 6 et 7
Implémentation des arbres
7[]6[]5[]4[]
On crée ensuite l’étage du dessus
On écrit toujours les successeurs du poids le plus petit vers le plus grand (de la gauche vers la droite)
3[ 6[], 7[] ]2[ 4[], 5[] ]
Implémentation des arbres
7[]6[]5[]4[]
On crée enfin la racine3[ 6[], 7[] ]2[ 4[], 5[] ]
1[ 2[ 4[], 5[] ], 3[ 6[], 7[] ] ]
CAS PARTICULIER : Graphe d’état
Prenons une situation initiale S avec des variables a, b, c :
Le but est de représenter les différentes évolutions possibles de S avec un ensemble d’opérations possibles sur les variables pour atteindre un objectif.
CAS PARTICULIER : Graphe d’étatExemple: On dispose d’un sac a dos qui peut transporter 15 kilos, et de divers objets de poids différent, le but est de remplir le sac avec le plus d’objets possible.
Objets : 3kg , 4kg , 5kg et 11kg Représentation du sac:[ . , . , . , . ]3 4 5 11
Opération possible : ajouter un objet
CAS PARTICULIER : Graphe d’état
S = [0,0,0,0]
S = [0,1,0,0] S = [0,0,1,0]S = [1,0,0,0] S = [0,0,0,1]
Etape 0 : Etat initial
Etape 1 : On met un objet dans le sac
3kg 4kg 5kg 11kg
CAS PARTICULIER : Graphe d’état
S = [0,0,0,0]
S = [0,1,0,0] S = [0,0,1,0]S = [1,0,0,0] S = [0,0,0,1]
Etape 0 : Etat initial
S = [0,0,2,0]
S = [1,1,0,0]
S = [0,1,0,1]
S = [0,0,3,0] P = 15kg
P = 15kg
…
S = [5,0,0,0] P = 15kg
ALGORITHMES SUR LES GRAPHES
- PARCOURS
- ARBRE COUVRANT DE POIDS MINIMAL
- PLUS COURT CHEMIN
Remarque essentielle:Pour des raisons de simplicités évidentes :
Dans tout les algorithmes, seront considérées déjà implantées les fonctions de bases associées aux graphes, comme Neighbors() (voisins) , Weight(u,v) ou w(u,v) (poids de l’arête reliant u à v).
On considérera également dans le cas des algorithmes traités que tout les graphes sont à un état initial où les sommets sont non traités (sinon on rajoute une boucle en début de code pour initialiser le graphe)
PARCOURS DE GRAPHE- DEPTH FIRST SEARCH
- BREADTH FIRST SEARCH
Parcours en profondeur (DFS) Le parcours en profondeur d’un arbres est le plus simple à coder car on peut l’implémenter de manière récursive
Principe : On part d’un sommet et on prend un chemin. Lorsqu’on arrive dans une impasse (fils déjà traités ou en traitements) , on revient au sommet précédent et on examine les autres fils.
Fct DFS-Iterativ(G,s):P <- CreateStack()P.push(s)Processed(s)WHILE (NOT P.Empty()) DO
P.pop(s)IF NotLabelled(s)
Label(s)FOR v IN Neighbour(s) DO
P.push(v)Processed(v)
Parcours en profondeur récursif:De manière récursive, on fait le parcours en profondeur de tout les fils du nœud , et on recommence jusqu’à tomber sur un sommet déjà marqué:
Fct DFS (G):
FOR s IN Vertices(G) DO
SI NotLabelled(s) DO
DFS_Recursiv(G,s);
Processed(s);
Fct DFS_Recursiv (G,s):
Label(s);
FOR s_son IN Neighbour(s) DO
IF NotLabelled(s_son)
DFS_Recursiv(G,s_son);
Processed(s);
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
Tout les voisins de D sont déjà marqués :On revient on dernier sommet avec un voisin non marqué.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
En traitementTraitéNon traité
Parcours en profondeur récursif:Exemple : Supposons qu’on parte du sommet A, et que pour chaque sommet, on suive l’ordre alphabétique.
Tout les sommets sont traités !
Ordre de traitement avec algorithme DFS:A,B,C,D,F,E
Complexité temporelle en 𝑂(|𝐸| + |𝑉| )
Tri TopologiqueExemple d’application du parcours en profondeur sur des Graphes Orientés Acycliques
Il permet d’ordonner les sommets de telle sorte que chaque sommet apparaisse avant ses successeurs dans cet ordonnancement
Il est nécessaire lors de l’implémentation avec un algorithme DFS de rajouter dans celui-ci une variable de « temps » pour savoir quand chaque sommet a été traiter et les ordonner
Des Tris topologiques de ce graphe donneraient par exemple:
- 5,7,11,3,8,2,9,10- 7,5,3,11,10,8,2,9- 3,7,8,5,11,10,9,2
Parcours en largeur (BFS)Principe : On part d’un sommet S, on liste ses voisins et on les explore un par un, et on continue jusqu’à ce que l’arbre soit totalement traité (peut servir a déterminer la connexité d’un graphe).
On y utilise la structure de file.Fct BFS(G,s):
F <- CreateQueue();F.Enqueue(s);Label(s);WHILE (NOT F.Empty()) DO
v <- F.Dequeue();Processed(v);Print(v); FOR u IN Neighbour(v) DO
IF NotLabeled(u) DOF.Enqueue(u);Label(u);
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
File de traitement:[A]
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
On explore tout les voisins de A :B,C,D et EFile de traitement:
[A,B,C,D,E]
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
On considère A traitéPuis on explore les voisins de BFile de traitement:
[B,C,D,E]File traitée:[A]
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
B est ensuite TraitéOn explore les voisins de C:On ajoute F à la file
File de traitement:[C,D,E,F]File traitée:[A,B]
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
C est traitéOn passe à DFile de traitement:
[D,E,F]File traitée:[A,B,C]
Parcours en largeur (BFS)Reprenant notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
Puis à EFile de traitement:[E,F]File traitée:[A,B,C,D]
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
En traitementTraitéNon traité
Et Enfin à FFile de traitement:[F]File traitée:[A,B,C,D,E]
Parcours en largeur (BFS)Reprenons notre exemple de tout à l’heure en partant toujours du sommet A:
On a traité le Graphe dans cet ordre : A,B,C,D,E,F
Alors qu’avec le DFS, on avait:A,B,C,D,F,E
Complexité temporelle en 𝑂 |𝐸| + |𝑉|Même que l’algorithme DFS
Propriétés de l’algorithme BFS
L’algorithme BFS peut être utilisé comme algorithme de plus court chemin (on en reparlera dans la partie appropriée)
Sur le problème du rendu de monnaie, l’algorithme BFS donne toujours la solution optimale (se vérifie par récurrence) lorsque l’on modélise le problème par un graphe d’état comme expliqué précédemment :
Rendu : R = [ . , . , . ]
1 2 5
A chaque étape on rajoute un pièce jusqu’à avoir le rendu désiré (7€ par exemple)
Remarques sur les structures utiliséesDans les deux algorithmes, on peut remarquer l’utilisation des fonctions « Label() » , « NotLabelled() » et « Processed() »
Il est important de savoir comment on peut les implémenter.
Comme dans mes exemples, le plus simple est de donner une couleur (ou une valeur) à chaque sommet où chacune représente un état entre Non traité , En traitement et Traité.
De plus, un peut créer une liste « parents » où l’on insère les sommets dans l’ordre où ils sont traités afin d’obtenir « l’arbre parent » , qui représente le chemin suivi lors du parcours
(ou liste « Traités »)
En traitementTraitéNon traité
ARBRE COUVRANT DE POIDS MINIMAL (ARPM ou MST)
Définition et propriétésPrenons un graphe pondéré :
Définition et propriétésPrenons un graphe pondéré :
Celui-ci par exemple
Définition et propriétésPrenons un graphe pondéré :
Notre but est de relier tout les sommets, avec un arbre (donc sans aucun cycle) composé a partir d’arêtes du graphe.Cet arbre « couvrant » devant être minimal, l’objectif est de trouver un arbre dont le poids est minimisé par rapport à tout les arbres couvrants possibles.
Définition et propriétés
Un arbre couvrant minimalP = 4
Définition et propriétés
Un arbre couvrant minimalP = 4
Un arbre couvrant non minimalP = 6
Pourquoi rechercher un tel Arbre?Certains problèmes de la vie de tout les jours nécessitent de trouver de tels arbres:
Par exemple, connecter un réseau téléphonique en utilisant le moins de longueur de câble possible , au choix pour joindre des pattes sur un circuit imprimé, etc …
Dans des domaines plus abstrait ils peuvent servir au partitionnement de données ou au traitement d’image
Algorithme de PrimUn premier algorithme pour chercher de tels arbres est l’algorithme de Prim du nom de son auteur Robert C. Prim.
C’est une sorte d’algorithme glouton qui garantie de toujours donner une solution optimal (donc un arbre couvrant minimal).
Principe:
On part d’un sommet A quelconque du graphe, et on sélectionne l’arête de plus faible poids connecté à ce sommet (on a donc 2 sommets A et B dans notre arbre).
On sélectionne parmi toutes les arêtes n’appartenant pas a notre arbre connectées à A ou à B celle de poids minimal.
On continue jusqu’à contenir tout les sommets du graphe.
Algorithme de PrimPseudo-Code : Fct Prim(G,w,s)
FOR v IN V(G)color(v) <- WHITEkey(v) <- infinityp(v) <- NIL
Q <- øcolor(s) <- GRAYInsert(Q, s)key(s) <- 0WHILE (NOT Q.Empty() ) DO
u <- ExtractMin(Q)FOR v IN Neighbors(u)
IF color(v) = WHITE color(v) <- GRAYInsert(Q,v)key(v) <- w(u,v)p(v) <- u
ELSEIF color(v) = GRAYIF key(v) > w(u,v)
key(v) <- w(u,v)p(v) <- u
color(v) <- BLACKRETURN(p)
Complexité temporelle en:
Avec une liste d’adjacence𝑂 |𝐸||𝑉|
Avec un tas binaire en file de priorité𝑂 |𝐸|𝑙𝑜𝑔|𝑉|
Avec un tas de Fibonacci𝑂 𝐸 + |𝑉|𝑙𝑜𝑔|𝑉|
Algorithme de PrimExemple: Reprenons notre graphe pondéré du tout début
A
E
D
C
B
On choisit un sommet au hasard, par exemple, le sommet A (sur une liste plus ou moins ordonné, on prendra le premier élément par exemple)
En traitementTraitéNon traité
Algorithme de PrimExemple: Reprenons notre graphe pondéré du tout début
A
E
D
C
B
On sélectionne l’arête de poids la plus faible sur notre sous ensemble ( ici singleton A)Et on rajoute le sommet B au sous ensemble
En traitementTraitéNon traité
Algorithme de PrimExemple: Reprenons notre graphe pondéré du tout début
A
E
D
C
B
Sur le sous ensemble (A,B) , on sélectionne l’arête de poids le plus faibleEt on ajoute le sommet D au sous ensemble (et l’arête)
En traitementTraitéNon traité
Algorithme de PrimExemple: Reprenons notre graphe pondéré du tout début
A
E
D
C
B
On continueUne fois que tout les voisins d’un sommets sont ajoutés au sous ensemble, le sommet est traité
En traitementTraitéNon traité
Algorithme de PrimExemple: Reprenons notre graphe pondéré du tout début
A
E
D
C
B
Et enfin, on ajoute le dernier sommetEt on obtient un arbre couvrant de poids minimal (MST , Minimum Spanning Tree)
En traitementTraitéNon traité
Algorithme de KruskalL’algorithme Kruskal est un autre algorithme de recherche d’arbre couvrant minimal mais il utilise une structure de donnée particulière non vue en cours le Union-Find
Principe:
A chaque sommet s du graphe, on créé un singleton {s} . Ensuite on ordonne toutes les arêtes du graphe par ordre croissant de poids.
On prend la première, dont les sommets sont u et v et on forme l’ensemble {u}U{v}.
On continue, mais si en choisissant une arête, on tombe sur un sommet qui appartient déjà à un ensemble plus gros, on fait l’union entre les ensembles des deux sommets.
Grossièrement , on crée des sous arbres qu’on réunis en utilisant des arêtes de faible poids
Algorithme de KruskalPseudo-Code:
Fct Kruskal(G,w):A <- ∅FOR v IN V(G)
Makeset(v)E <- sort(E(G)) # on trie les arêtes par poids croissant
FOR (u,v) IN EIF Find(u) ≠ Find(v)
A <- A U {(u,v)}Union(u,v)
RETURN(A)
Les fonctions Makeset, Find et Union sont des fonctions de la structure Union-Find
Makeset() = créé une classe d’équivalenceFind() = détermine la classe d’équivalence d’un élémentUnion() = Réunit deux classes d’équivalences
Complexité temporelle en 𝑂 |𝐸|𝑙𝑜𝑔|𝐸|
Algorithme de KruskalExemple:
Ordre des arêtes :1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (C,H) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
On génère le Find-Union :
[ {A}, {B}, {C}, {D}, {E}, {F}, {G}, {H} ]
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (C,H) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A}, {B}, {C}, {D}, {E}, {F}, {G}, {H} ]
On prend la première arête de la liste et on modifie le Find-Union
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (C,H) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B}, {C}, {D}, {E}, {F}, {G}, {H} ]
On prend la suivanteEt on remodifie le tout
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (C,H) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B, C}, {D}, {E}, {F}, {G}, {H} ]
Et ainsi de suite
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (C,H) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B, C}, {D}, {E, G}, {F}, {H} ]
A et C sont dans le même sous ensemble, donc on ne prend pas (A,C), on passe à la suivante
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (C,H) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B, C}, {D}, {E, G, F}, {H} ]
On continue
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (D,E) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B, C , H}, {D}, {E, G, F} ]
On continue
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (D,E) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B, C , H}, {D, E, G, F} ]
A partir d’ici, tout les sommets sont dans le même ensemble
2
Algorithme de KruskalExemple: Ordre des arêtes :
1 : (A,B) , (B,C) , (E,G)2 : (A,C) , (E,F) , (H,C)3 : (D,E) , (F,H) , (G,H)4 : (G,C)7 : (A,E)
Find-Union :[ {A, B, C , H, D, E, G, F} ]
On obtient donc un arbre couvrant minimal de notre graphe
2
ALGORITHME DE PLUS COURT CHEMIN
Définition et propriétésSoit un graphe G(V,E) pondéré (ou non).
Le poids d’un chemin est la somme des poids des arêtes qui le constituent ( nombre d’arêtes si le graphe n’est pas pondéré)
Soit u et v deux sommet d’une même composante connexe de G, le plus court chemin de v à u est le chemin dont le poids est minimal
Plusieurs algorithmes donnent de tels chemin, mais on a besoin de quelques propriétés.
Définition et propriétésSous chemin d’un plus court chemin :
Notons 𝑐 = (𝑢0, 𝑢1, … , 𝑢𝑛−1, 𝑢𝑛) un plus court chemin de 𝑢0 à 𝑢𝑛 .
Alors ∀ 𝑖, 𝑗 ∈ 0, 𝑛 , 𝑐𝑖,𝑗 = 𝑢𝑖 , … , 𝑢𝑗 est un plus court chemin de 𝑢𝑖 à 𝑢𝑗
(se démontre par l’absurde assez facilement)
Propriété :
Dans un graphe pondéré positif, un plus court chemin ne peut pas contenir de cycle
On peut donc se contenter d’étudier les chemin de tailles 𝑉 − 1 (Arbres)
RelaxationPrenons un graphe pondéré simple A l’état initial, en partant, du sommet s (on a pas
exploré le graphe) , on a les distances aux sommets adjacents :
d(s,a)=3d(s,b)=2d(s,c)=7
La relaxation consiste à regarder parmi les adjacents des voisins de s s’il ne sont pas plus proches des autres voisins de s
Par exemple, ici, on peut regarder b le voisin de s pour voir si en passant par b, on est pas plus proche de c
RelaxationPrenons un graphe pondéré simple C’est en effet le cas :
d(s,c) > d(s,a) + w(b,c)
En pseudo code, on obtient cette fonction :
Fct Relax (c,b,w):IF d(s,c) > d(s,b) + w(b,c)
d(s,c) <- d(s,b) + w(b,c)c.parent <- b;
Remarque :Un plus court chemin est invariant par relaxation
Une fois la relaxation réalisée pour tout les sommets, on obtient un arbre de plus court chemin de racine s
Complexité:𝑂 1
Algorithme de DijkstraL’algorithme de Dijkstra en s s’applique sur un graphe pondéré positif et crée un arbre de plus court chemin enraciné en s , appelé arbre de Dijkstra en s.
Le principe est d’effectuer un parcours en largeur et une relaxation de chaque voisins à chaque sommet traité.
Nous auront besoin pour cela d’une fonction qui initialise les distance à l’infinie
Fct InitGraph (G,s):FOR v IN V(G)
d(s,v) <- infinityv.parent <- NIL
d(s,s) = 0
Complexité:
𝑂 |𝑉|
Algorithme de Dijkstra
Pseudo – Code :
Fct Dijkstra(G,w,s):InitGraph(G,s)DT <- ∅Q <- V(G)WHILE (NOT Q.Empty()) DO
u <- ExtractMin(Q)T <- T U {u}FOR v IN Neighbors(u)
Relax(u,v,w)
Cette algorithme créé un arbre (modélisé par la relation parent de la fonction Relax) enraciné en s qui donne les plus courts chemins entre s et les autres sommets.
Complexité :
Si Q est réalisé par une liste𝑂 |𝑉|²
Si Q est réalisé par un tas 𝑂 |𝐸|𝑙𝑜𝑔|𝑉|
Algorithme de DijkstraReprenons ce graphe et créons son arbre de Dijkstra enraciné en A
On créé notre file de priorité
A 0
B ∞
C ∞
D ∞
E ∞
F ∞
G ∞
H ∞
2
Algorithme de DijkstraOn traite le haut de la file de priorité
B ∞
C ∞
D ∞
E ∞
F ∞
G ∞
H ∞
0
2
Algorithme de DijkstraOn traite le haut de la file de priorité
B 1
C ∞
D ∞
E ∞
F ∞
G ∞
H ∞
0
2
Algorithme de DijkstraOn traite le haut de la file de priorité
B 1
E 7
C ∞
D ∞
F ∞
G ∞
H ∞
0
2
Algorithme de DijkstraOn traite le haut de la file de priorité
B 1
E 7
C 2
D ∞
F ∞
G ∞
H ∞
0
2
Algorithme de DijkstraOn traite le haut de la file de priorité
C 2
E 7
D ∞
F ∞
G ∞
H ∞0
1
2
Algorithme de DijkstraOn traite le haut de la file de priorité
E 7
D ∞
F ∞
G ∞
H ∞
0
1
2
2
Algorithme de DijkstraOn traite le haut de la file de priorité
H 4
E 7
D ∞
F ∞
G ∞
0
1
2
2
Algorithme de DijkstraOn traite le haut de la file de priorité
H 4
E 7
G 6
D ∞
F ∞
0
1
2
2
Algorithme de DijkstraOn traite le haut de la file de priorité
G 6
E 7
D ∞
F ∞
0
1
2
2
4
Algorithme de DijkstraOn traite le haut de la file de priorité
G 6
E 7
F 7
D ∞
0
1
2
2
4
Algorithme de DijkstraOn traite le haut de la file de priorité
E 7
F 7
D ∞
0
1
2
2
46
Algorithme de DijkstraOn traite le haut de la file de priorité
F 7
D 10
0
1
2 F 7
D ∞2
46
7
Algorithme de DijkstraOn traite le haut de la file de priorité
F 7
D 10
0
1
2
2
46
7
Algorithme de DijkstraOn traite le haut de la file de priorité
D 10
0
1
2
2
46
7
7
Algorithme de DijkstraOn obtient notre arbre de Dijkstra enraciné en A
0
1
2
2
46
7
7
10 0
1 2 7
1046
7
Graphes pondérés quelconquesDe manière général :
Les graphes pondérés peuvent être orientés, voire pondérés de poids négatifs (ce qui complique particulièrement leur étude)
Dans le cas d’un arbre pondéré de poids négatifs, Dijkstra ne fonctionne plus !
Particulièrement si dans le graphe il existe un cycle de poids total négatif, Dijkstra boucle à l’inifni.
Algorithme de Bellman FordC’est un algorithme de plus court chemin non limité aux arêtes de poids positifs. De plus il détecte s’il y a un cycle négatif dans le graphe.
Inconvénient : Complexité plus élevé que Dijkstra
Principe :
On relaxe toutes les arêtes 𝑉 − 1 fois
Si la situation est stable, on a les plus courts chemin à la source
Si on peut encore relaxer les arêtes, c’est qu’on a un cycle de poids négatif
Algorithme de Bellman FordPseudo – Code:
Fct BellmanFord (G,w,s):InitGraph(G,s)FOR i <-1 TO 𝑉 − 1
FOR (u,v) IN 𝐸(𝐺)Relax (u,v,w)
FOR (u,v) IN 𝐸(𝐺)IF d(s,v) < d(s,u) + w(u,v)
RETURN FalseRETURN True
Complexité en 𝑂(|𝐸||𝑉| )
Par exemple sur ce Graphe:
Algorithme de Floyd WarshallAlgorithme de plus court chemin :
Programmation dynamique avec une Matrice de pondération !
(Peu utile pour le CF)
QUELQUES EXERCICES
Plus courts chemins et Arbres couvrant
A B C D E F
0 6 9 11 5 9
6 0 3 6 5 2
9 3 0 0 4 4
11 6 0 0 5 6
5 5 4 5 0 8
9 2 4 6 8 0
Déterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
Déterminer un arbre recouvrant de poids minimal par application de l'algorithme de Prim partant du nœud F.
Déterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
Plus courts chemins et Arbres couvrant
A B C D E F
0 6 9 11 5 9
6 0 3 6 5 2
9 3 0 0 4 4
11 6 0 0 5 6
5 5 4 5 0 8
9 2 4 6 8 0
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
Première arête : (B,F)
Tri des arêtes :2 : (B,F)3 : (B,C)4 : (C,E) , (C,F)5 : (B,E) , (D,E) , (A,E)6 : (B,A) , (B,D) , (D,F)8 : (E,F)9 : (A,F) , (C,A)11 : (A,D)
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
2ème arête : (B,C)
Tri des arêtes :2 : (B,F)3 : (B,C)4 : (C,E) , (C,F)5 : (B,E) , (D,E) , (A,E)6 : (B,A) , (B,D) , (D,F)8 : (E,F)9 : (A,F) , (C,A)11 : (A,D)
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
3ème arête : (C,E)
Tri des arêtes :2 : (B,F)3 : (B,C)4 : (C,E) , (C,F)5 : (B,E) , (D,E) , (A,E)6 : (B,A) , (B,D) , (D,F)8 : (E,F)9 : (A,F) , (C,A)11 : (A,D)
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
4ème arête : (D,E)
Tri des arêtes :2 : (B,F)3 : (B,C)4 : (C,E) , (C,F)5 : (B,E) , (D,E) , (A,E)6 : (B,A) , (B,D) , (D,F)8 : (E,F)9 : (A,F) , (C,A)11 : (A,D)
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
Dernière arête : (A,E)
Tri des arêtes :2 : (B,F)3 : (B,C)4 : (C,E) , (C,F)5 : (B,E) , (D,E) , (A,E)6 : (B,A) , (B,D) , (D,F)8 : (E,F)9 : (A,F) , (C,A)11 : (A,D)
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Kruskal.
Résultat :
Tri des arêtes :2 : (B,F)3 : (B,C)4 : (C,E) , (C,F)5 : (B,E) , (D,E) , (A,E)6 : (B,A) , (B,D) , (D,F)8 : (E,F)9 : (A,F) , (C,A)11 : (A,D)
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Primpartant du nœud F.
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Primpartant du nœud F.
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Primpartant du nœud F.
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Primpartant du nœud F.
Plus courts chemins et Arbres couvrantDéterminer un arbre recouvrant de poids minimal par application de l'algorithme de Primpartant du nœud F.
c
Remarque : on a le même arbre que par Kruskal
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
F 0
A ∞
B ∞
C ∞
D ∞
E ∞
0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
A 9
B ∞
C ∞
D ∞
E ∞0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
B 2
A 9
C ∞
D ∞
E ∞0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
B 2
A 9
C 4
D ∞
E ∞0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
B 2
A 9
C 4
D 6
E ∞0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
B 2
A 9
C 4
D 6
E 50
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
C 4
A 9
D 6
E 8
2 0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
C 4
A 8
D 6
E 7
2 0
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
D 6
A 8
E 7
2 0
4
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
E 7
A 8
2 0
4
6
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
A 8
2 0
4
6
7
Plus courts chemins et Arbres couvrantDéterminer les plus courts chemins de F à tout autre nœud du graphe en utilisant l'algorithme de Dijkstra.
On obtient notre arbre de Dijkstra enraciné en F
2 0
4
6
7
8
Plus courts chemins et Arbres couvrantDonner un exemple d'un graphe pondéré tel que un arbre recouvrant de poids minimal de ce graphe diffère de tous ses arbres de Dijkstra.
Plus courts chemins et Arbres couvrantDonner un exemple d'un graphe pondéré tel que un arbre recouvrant de poids minimal de ce graphe diffère de tous ses arbres de Dijkstra.
L’arbre en vert est un arbre recouvrant de poids minimal pour le graphe G
Et pourtant aucun de ses arbres de Dijkstra ne pourra être égal à cet arbre.
Cela se démontre par l’absurde en supposant que cet arbre est un de ses arbres de Dijkstra (peu importe le sommet, on arrive à une contradiction)
Plus courts chemins et Arbres couvrantProuver qu'un arbre de Dijkstra et un arbre recouvrant de poids minimal (ARPM) ont toujours au minimum une arête en commun.
Démonstration par l’absurde :
Supposons qu’un arbre de Dijkstra et un arbre recouvrant minimal n’aient aucune arête en commun.
Soit s tel que l’arbre de Dijkstra soit enraciné en s. Soit (𝑢0, 𝑢1, … , 𝑢𝑛−1, 𝑢𝑛) l’ensemble des voisins de s tels que l’arête entre eux et s soit dans l’arbre de Dijkstra.
Par définition, ces trois arêtes sont les plus court chemins entre les 𝑢𝑖 𝑑𝑒 (𝑢0, 𝑢1, … , 𝑢𝑛−1, 𝑢𝑛) et s.
Or si aucune de ces trois arêtes n’est dans l’ARPM , alors il existe un chemin plus court pour atteindre s
Contradiction !
Chemin de fer
Demain, Mario doit voyager de Rennes à Grenoble pour participer à un concours de programmation. Mario a peur d'arriver en retard, et cherche donc le train qui arrive à Grenoble le plus tôt possible. Mario ne veut pas non plus arriver en avance à la gare, donc si plusieurs trains arrivent à Grenoble à la même heure, il prendra celui qui part le plus tard de Rennes. Mario vous demande de l'aider pour choisir son train.
On vous donne une table des horaires des trains à partir de laquelle vous devez calculer le train avec l'horaire d'arrivée au plus tôt et le temps de parcours le plus court. Heureusement, Mario voyage souvent et sait donc changer de train sans perdre de temps (pour un coût 0 !).
Chemin de ferEn entrée, vous prendrez une description du problème consistant en 3 parties :
1) description des villes interconnectées par train:
Une première ligne donne V le nombre de villes, puis V lignes avec un nom de ville par ligne.
2) description des lignes:
Une première ligne avec un nombre T indiquant le nombre de lignes de chemin de fer, puis pour chacune des T lignes de chemin de fer, une ligne avec Ti indiquant le nombre de villes sur la ligne de chemin de fer suivie de Ti lignes avec sur chaque ligne, l'heure de passage au format hhmmsuivi du nom de la ville.
3) les données spécifiques:
Une ligne avec l'heure de départ au plus tôt, puis une ligne avec la ville de départ de Mario, puis une ligne avec l'heure d'arrivée.
Chemin de fer
En graphe (V=3 et T=3):Structure du fichier (Comme proposé au dessus)
VNomV1.NomVvTT1Hhmm NomVilleT1,1.Hhmm NomVilleT1,T1.TtHhmm NomVilleTt,1.Hhmm NomVilleTt,TtDépart plus tôtVille départHeure arrivée
V lignes
T1 lignes
Tt lignes
T paquets
Chemin de ferEn graphe (V=3 et T=3):
Les arêtes sont pondérées par les temps de trajets
On a de plus des contraintes supplémentaire dont on tiens compte dans l’algorithme:
Heure d’arrivée Ville de départHeure de départ au plus tôt
Solution : Faire du backtracking(Partie 4 )
Problèmes avec les graphesOn a peu parlé des Graphes pondérés , mais deux notions essentielles apparaissent:
Les puits
Les sources
Si un graphe admet une source, il n’y a aucun chemin menant à s (donc pas de plus court):
Une source est une composante connexe à elle seule
Un autre problème sur les graphe (tel que celui du chemin de fer) ne peut être résolu avec les algorithmes présentés ici : La coloration (Ce problème est présenté en partie 4)
Coloration de graphe,backtracking,
branch and bound
par Aymeric ‘Bébert’ Bernard
Coloration de graphe
Coloration de graphe : définitions
Comment colorer un graphe de telle sorte que deux nœuds adjacents soient de couleur différente ?
Couleur : nombre entier, généralement entre 0 et n-1
χ(G) : nombre minimal de couleurs pour colorer G
Coloration de graphe : graphe biparti
Il existe une partition des sommets du graphe en deux ensembles G1, G2 telle que toute arête relie un sommet de G1 à un sommet de G2
Graphe biparti : χ(G) = 2 (graphe colorable avec 2 couleurs)
Coloration de graphe : graphe bipartiComment savoir si un graphe est biparti ?
→ On parcourt le graphe, et à chaque changement de profondeur on changede couleur, Si ce n’est pas possible, le graphe n’est pas biparti
Coloration de graphe : comment faire ?
Quel algorithme permet de colorer un graphe ?Quid de l’optimalité ?
Deux algorithmes principaux :- Algorithme glouton, naïf, non optimal mais rapide- Backtracking, complexité élevée mais permet d’avoir
un résultat optimal
Coloration de graphe : algorithme glouton
Algorithme glouton : avance étape par étape, choisit une solution optimale localement, sans souci d’optimalité globale.
Principe : on parcourt le graphe, et à chaque nœud on assigne la première couleur possible (en fonctions des voisins déjà colorés).
Problème : le nombre de couleurs dépend du nœud de départ, de la manière de parcourir le graphe…
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées :
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées :
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées :
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2, 3
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2, 3 → 4 couleurs
Coloration de graphe : algorithme glouton
Exemple :
Et pourtant…
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2
Coloration de graphe : algorithme glouton
Exemple :
Couleurs utilisées : 0, 1, 2 → 3 couleurs
Coloration de graphe : algorithme gloutonfunction greedyColor(G):| c ← 0| …| …| …| …| …| …| …| …| …| …| …| …| …| return c
Coloration de graphe : algorithme gloutonfunction greedyColor(G):| c ← 0| for i ← 0 to n-1:| | …| | …| | …| | …| | …| | …| | …| | …| | …| | …| | …| | …| return c
Coloration de graphe : algorithme gloutonfunction greedyColor(G):| c ← 0| for i ← 0 to n-1:| | forbiddenColors ← tableau(c,False)| | for n in neighbors(G[i]) if n.color != None:| | | forbiddenColors[n.color] ← True| | …| | …| | …| | …| | …| | …| | …| | …| | …| return c
Coloration de graphe : algorithme gloutonfunction greedyColor(G):| c ← 0| for i ← 0 to n-1:| | forbiddenColors ← tableau(c,False)| | for n in neighbors(G[i]):| | | if n.color != None:| | | | forbiddenColors[n.color] ← True| | k ← c| | for j ← c-1 downto 0 if not(forbiddenColors[j]):| | | k ← j| | …| | …| | …| | …| | …| return c
Coloration de graphe : algorithme gloutonfunction greedyColor(G):| c ← 0| for i ← 0 to n-1:| | forbiddenColors ← tableau(c,False)| | for n in neighbors(G[i]):| | | if n.color != None:| | | | forbiddenColors[n.color] ← True| | k ← c| | for j ← c-1 downto 0 if not(forbiddenColors[j]):| | | k ← j| | if k = c:| | | c = c+1| | | G[i].color ← c| | else:| | | G[i].color ← k| return c
Coloration de graphe : algorithme glouton
Le nombre de couleurs utilisé ≤ Δ(G) +1(Δ(G) = degré de G = nombre maximal d’arêtes partant d’un nœud)
Complexité : Θ(|V|+|E|)
Le backtracking(et son application à la coloration de graphe)
Le backtracking : schéma général
Principe général : revenir légèrement en arrière sur les décisions prises en cas de blocage
Utilisé surtout dans la programmation sous contraintes :- Colorer un graphe- Problème des n dames- Résolution d’une grille de sudoku- Mise en place d’emplois du temps- …
Le backtracking : schéma général
On veut créer un algorithme qui renvoie True si une solution à notre problème (avec ses contraintes) existe, et False sinon(variante : stocker une ou toutes les solutions trouvées et les renvoyer).
« revenir légèrement en arrière » : par récursivité, on ne crée pas de fonction que revient explicitement sur une étape précédente !
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d): # s situation courante, d profondeur courante| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| -- si s est solution, on renvoie True --
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True # ou stocker si on veut stocker toutes les solutions| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d): | if isSolution(s):| | return True| -- sinon, on veut parcourir les situations de profondeur d+1 --| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d): | if isSolution(s):| | return True| for n in nextSituations(s):| | …| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | -- appel récursif pour la situation n, à une profondeur d+1 --| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | if backtrack(n,d+1): # solution trouvée dans cette branche !| | | …| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | if backtrack(n,d+1):| | | -- on fait remonter l’information dans la recursion --| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | if backtrack(n,d+1):| | | return True| …
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | if backtrack(n,d+1):| | | return True| -- si aucune de ces situations n’est possible, renvoyer False --
Le backtracking : schéma général
Schéma de l’algorithme :
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | if backtrack(n,d+1):| | | return True| return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : illustration du principe
1 function backtrack(s,d):2 | if isSolution(s):3 | | return True4 | for n in nextSituations(s):5 | | if backtrack(n,d+1):6 | | | return True7 | return False
Le backtracking : attention
Lors d’une mise en place d’un algorithme de backtracking, faire attention aux points suivants :- Soigner la situation d’arrêt (valable pour tout algorithme récursif )- Si le problème peut présenter un cycle (on peut revenir à un état déjà traité),
il faut trouver un moyen de repérer les états déjà parcourus (attribut, stockage dans un dictionnaire,…)
- La complexité du backtracking est exponentielle, en Θ(bd) avec `b` le facteur de branchement et `d` la profondeur maximale de récursion.
Le backtracking : coloration de graphe
function backtrack(s,d):| if isSolution(s):| | return True| for n in nextSituations(s):| | if backtrack(n,d+1):| | | return True| return False
maxColor = n
function backtrackColor(G,k): # k : noeud courant| if k = |V(G)|:| | return True| for c ← 0 to maxColor:| | V(G)[k].color ← c| | if not c in [n.color for n in neighbors(V(G)[k])]:| | | if backtrackColor(G,k+1):| | | | return True| V(G)[k].color ← -1 # décolorer le sommet| return False
L’algorithme renvoie True si le graphe est colorable avec maxColor couleurs.
Le backtracking : coloration de graphe optimale
A partir de cet algorithme, il est possible d’obtenir χ(G)
maxColor = n
function backtrackColor(G,k):| if k = |V(G)|:| | return True| for c ← 0 to maxColor:| | V(G)[k].color ← c| | if not c in [n.color for n in neighbors(V(G)[k])]:| | | if backtrackColor(G,k+1):| | | | return True| V(G)[k].color ← -1| return False
maxColor ← ∞
function backtrackColorOpt(G,k):| if k = |V(G)|:| | maxColor ← min(maxColor,countColors(G))| for c ← 0 to maxColor:| | V(G)[k].color ← c| | if not c in [n.color for n in neighbors(V(G)[k])]:| | | backtrackColorOpt(G,k+1):| V(G)[k].color ← -1
Branch and bound(séparation et évaluation)
Branch and bound : principeBranch : séparer l’ensemble des solutions en ensembles plus petitsBound : évaluer ces sous-ensembles et n’explorer que ceux pouvant contenir une solution meilleure que la meilleure solution courante (par majoration).
Cela nous donne encore une fois une structure d’arbre, dans lequel seules les branches les plus prometteuses vont être parcourues (on parle d’élagage, d’arbre de décision,…)
« solution courante » : on stocke la meilleure solution trouvée jusqu’à présent par l’algorithme.
Branch and bound : comment s’y prendre ?Comment savoir si un ensemble de solutions ne contient pas de solution optimale ?
→ Déterminer une borne inférieure pour le coût des solutions de cet ensemble (s'il s'agit d'un problème de minimisation).Si cette borne inférieure est de coût supérieur au coût de la meilleure solution courante, le sous-ensemble ne contient pas d'optimum.
Branch and bound : complexité
Utilisations :- Problèmes d’optimisation- IA (échecs,…)
En théorie la même que celle du backtracking : exponentielle, en Θ(bd)En pratique, on peut arriver bien plus vite à une solution optimale (ou acceptable, on peut s’arrêter quand on veut)
Branch and bound : exemple
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32Nombre x1 x2 x3 x4
Poids maximal : 130Nombre d’objet maximal : 4
On veut maximiser :4x1 + 5x1 + 6x1 + 2x1
Sous la contrainte :33x1 + 49x1 + 60x1 + 32x1 ≤ 130
Branch and bound : exemple
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32Nombre x1 x2 x3 x4
Fonction d’évaluation pour ce problème (critère de choix pour le prochain nœud) : maximiser coût/poids
Ici item 1 a un coût/poids maximal, on va commencer par ajouter des items 1
Branch and bound : exemple
> x1 = 3 : on ne peut plus rien mettre dans le sac, on a donc une (meilleure) solution à 12
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
12
Meilleure solution : 12
Branch and bound : exemple
> x1 = 2 : item 2 a maintenant le meilleur coût/poids.Evaluation : 2*4 + 5/49 x (130 - 2x33) = 14,5314,53 > 13 = 12+1 donc on a potentiellement une meilleure solution, on sépare le nœud
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
Meilleure solution : 12
14,53
12
Branch and bound : exemple
>> x1 = 2, x2 = 1 : on ne peut plus rien ajouter, solution à 2x4 + 5 = 13, c’est une meilleure solution
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
Meilleure solution : 13
14,53
12
13
Branch and bound : exemple
>> x1 = 2, x2 = 0 : l’item 3 a maintenant le meilleur coût/poids.Evaluation : 2*4 + 0 + 6/60 x (130 - 2x33) = 14,414 > 13+1 donc on a potentiellement une meilleure solution, on sépare le nœud
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
Meilleure solution : 13
12
14,5313
14,4
Branch and bound : exemple
>>> x1 = 2, x2 = 0, x3 = 1 : on ne peut plus rien ajouter, solution à 2x4 + 6 = 14, c’est une meilleure solution
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
Meilleure solution : 14
12
14,5313
14,4 14
Branch and bound : exemple
> x1 = 1 : évaluation 4 + 5/49 x (130 – 33) = 13,89On n’aura pas de meilleure solution dans cette branche (branche élaguée)
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
Meilleure solution : 14
12
14,5313
14,4 14
13,89
Branch and bound : exemple
> x1 = 0 : évaluation 5/49 x 130 = 13,27On n’aura pas de meilleure solution dans cette branche (branche élaguée)
item 1 item 2 item 3 item 4coût 4 5 6 2
poids 33 49 60 32
Meilleure solution : 14
12
14,5313
14,4 14
13,89
13,27
Branch and bound : algorithme
function solveBB(problem):| activeNodes ← getActiveNodes(problem)| best ← -∞| while activeNodes != []:| | n = choseActiveNode(activeNodes) # à définir| | if estSolution(n):| | | best ← max(best,n)| | else:| | | children ← split(n)| | | for f in children:| | | | e ← eval(f) # à définir| | | | if e > best:| | | | | activeNodes.add(f)| return best
Indécidabilité
Propriété indécidable : on ne peut ni la démontrer, ni la réfuter
Un exemple en informatique : le problème de l’arrêt
Existe-t-il un programme qui, étant donné en entrée un programme
informatique quelconque, détermine si ce programme termine ?
Problème de l’arrêt
���� ���, �� = �1siprogs′arrêtepourl′entréech0sinon
On pose alors :
"#�$%&��' (ch) :
Si ���� ��, �� = 1Alors Faire une boucle infinie
Sinon Terminer
10ème problème de Hilbert
•23 problèmes proposés par Hilbert en 1900
•10ème : Existe-t-il un algorithme permettant de trouver toutes les
solutions d’une équation diophantienne ?
•1970 : théorème de Matiiassevitch -> impossible
Problèmes P et NP
•Classe P
� On connaît un algorithme de résolution en temps polynomial
•Classe NP
� On sait vérifier une solution en temps polynomial
� On ne connaît pas d’algorithme de résolution en temps polynomial
� On ne sait pas s’il en n’existe pas
•Classe NP-complète
� Tous les problèmes de classe NP se ramènent à un de ceux-ci par
réduction polynomiale
Problème du voyageur de commerce
P = NP ?
Prix de 1 000 000 $
Bonnes révisions à tous !