IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Introduction aux algorithmes et aux structures de données

En 1976, le livre Algorithms + Data Structures = Programs paraît : le postulat posé par ce titre est bien qu'un algorithme n'est rien s'il n'a pas de structure de données appropriée pour stocker ses données. On étudiera, dans cette introduction, tant les algorithmes principaux (tri, graphes - le bien connu Dijkstra mais aussi Bellman-Ford pour la recherche de plus court chemin) que des structures de données très fréquentes sur lesquelles viennent se construire des solutions élaborées à des problèmes complexes (pile, file, dictionnaire, etc.). De même, puisqu'étudier un algorithme ne permet pas de résoudre tous les problèmes, on envisagera quelques techniques fréquentes pour en trouver (chaque technique ayant ses spécificités et sa manière de vivre : certaines sont applicables partout mais avec des temps d'exécution importants, d'autres seront plus rapides mais demanderont un temps d'apprentissage plus élevé ainsi que certaines caractéristiques pour le problème).

On n'utilisera à cette fin aucun langage de programmation précis, plutôt du pseudocode, afin de se focaliser sur les algorithmes, non sur leur implémentation. On développera des outils d'analyse de ces algorithmes (complexité et correction) pour les appliquer dans les parties suivantes.
On suppose que le lecteur a déjà des connaissances en programmation de base (algorithmes et structures de données de base - liste liée, liste doublement liée, tableau, etc.) et souhaite découvrir plus d'algorithmes et de structures de données avec une approche plus théorique que pratique - seul du pseudocode anglais sera présenté.

11 commentaires Donner une note à l´article (5)

Article lu   fois.

L'auteur

Profil ProSite personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Introduction et définitions de base

I-A. Algorithme

Un algorithme est une suite finie et non ambiguë d'opérations visant la résolution d'un problème. On le formule généralement comme la transformation d'un ensemble de valeurs d'entrée en un ensemble de valeurs de sortie.

Un algorithme est dit totalement correct lorsque, pour chaque instance d'un problème, il se termine en produisant la bonne sortie. Il sera dit partiellement correct si, quand il se termine, il donne la bonne sortie, sans assurer qu'il se termine. Il sera approximatif s'il ne donne qu'une approximation de la solution (comme les algorithmes numériques).

Pour tout algorithme, on se pose finalement trois questions : sa correction, sa vitesse d'exécution et la possibilité de faire mieux.

I-B. Structure de données

Une structure de données est une méthode de stockage et d'organisation des données pour en faciliter l'accès et la modification. Elle regroupe des données à gérer et un ensemble d'opérations qu'on peut leur appliquer. En général, il existe plusieurs manières de représenter ces données et plusieurs implémentations de leur manipulation.

L'interface sera définie dans un type de données abstrait (TDA). Il spécifie précisément la nature et les propriétés des données à stocker et les modalités des opérations.

I-C. Récursivité

Un algorithme est dit récursif s'il s'invoque lui-même (directement ou non - récursif multiple). Cela permet de simplifier l'expression de certains algorithmes.

Une procédure sera récursive terminale si elle n'effectue plus aucune opération après s'être invoquée récursivement.

II. Outils d'analyse des algorithmes

II-A. Analyse de la correction

La correction d'un algorithme s'étudie par rapport à un problème donné. Un algorithme sera correct pour une instance d'un problème s'il produit une solution correcte pour cette instance. Il sera correct pour un problème s'il est correct pour toute instance de ce problème.

II-A-1. Types d'analyse

On peut vérifier cette correction de manière empirique, en testant concrètement l'algorithme (il faut alors l'implémenter et trouver suffisamment d'instances du problème), ou de manière formelle, mathématique. On se focalisera sur cette deuxième approche.

II-A-2. Analyse formelle

Une assertion est une relation entre les variables qui est vraie à un moment dans l'exécution. Notamment, on compte les pré- et postconditions (conditions que doivent remplir les données d'entrée et de sortie) kitxmlcodeinlinelatexdvp{P}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp{Q}finkitxmlcodeinlinelatexdvp.

Ainsi, un code sera correct si le triplet de Hoare kitxmlcodeinlinelatexdvp{P} code {Q}finkitxmlcodeinlinelatexdvp est vrai. Pour vérifier cette propriété, on insère des assertions kitxmlcodeinlinelatexdvpP_{n}finkitxmlcodeinlinelatexdvp décrivant l'état des variables à chaque étape du programme et on vérifiera que cette suite de triplet est correcte :

kitxmlcodelatexdvp\{P\}\quad S_{1}\quad\{P_{1}\}finkitxmlcodelatexdvp kitxmlcodelatexdvp\{P_{1}\}\quad S_{2}\quad\{P_{3}\}finkitxmlcodelatexdvp kitxmlcodelatexdvp\dotsfinkitxmlcodelatexdvp kitxmlcodelatexdvp\{P_{n-1}\}\quad S_{n}\quad\{Q\}finkitxmlcodelatexdvp

Pour les boucles, on mettra en évidence une assertion particulière, kitxmlcodeinlinelatexdvp{I}finkitxmlcodeinlinelatexdvp , l'invariant de boucle, qui décrit l'état du programme pendant l'exécution. Cet invariant est vrai après l'initialisation de la boucle, après chaque itération (kitxmlcodeinlinelatexdvp\text{{I et B} code {I}}finkitxmlcodeinlinelatexdvp est vrai) et à la sortie de la boucle (kitxmlcodeinlinelatexdvp\text{{I et non B} fin {I}}finkitxmlcodeinlinelatexdvp est vrai). En général, l'algorithme découle de l'invariant, de l'idée de base à la conception.

II-A-3. Terminaison des boucles

Une fois qu'on a prouvé que la boucle était correcte, il faut s'assurer qu'elle se termine. On cherchera donc une fonction de terminaison kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp :

  • définie sur base des variables de l'algorithme ;
  • à valeur naturelle ;
  • décroissante suite à l'exécution du corps de la boucle ;
  • à valeur positive tant que le gardien de la boucle est vrai.

Ainsi, quand kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp atteindra zéro, on aura infirmé le gardien et la boucle sera terminée.

II-A-4. Preuve par induction et algorithmes récursifs

La preuve par induction se passe en deux étapes :

  • cas de base : on montre explicitement que la propriété est vraie pour une série d'instances ;
  • cas inductif : on suppose que la propriété est vraie pour les instances précédentes du problème et on montre qu'elle l'est aussi pour l'instance suivante.

Cette manière de procéder est correcte, car le corps des naturels kitxmlcodeinlinelatexdvp\mathbb{N}finkitxmlcodeinlinelatexdvp est bien ordonné par la relation kitxmlcodeinlinelatexdvp\leqfinkitxmlcodeinlinelatexdvp (dans tout sous-ensemble de kitxmlcodeinlinelatexdvp\mathbb{N}finkitxmlcodeinlinelatexdvp, il y a un plus petit élément).

II-B. Analyse de la complexité en temps

On peut la mesurer de manière expérimentale en implémentant l'algorithme et en le lançant sur des instances du problème. Cependant, les temps de calcul vont largement dépendre de l'implémentation, de la machine, du compilateur, des données, etc.

On préférera donc une manière plus théorique de procéder, sur base d'un modèle de calcul abstrait, la RAM (Random Access Machine). Les types de base sont limités aux entiers et nombres flottants avec une taille maximale. Une série d'opérations de base est définie ; chacune prend un temps constant et une série d'instructions est toujours exécutée de manière sérielle.

On distingue plusieurs types de calcul de complexité : le cas le plus défavorable (on considère le temps maximal pour toute instance d'une certaine taille), le plus favorable (on considère le temps minimal pour toute instance d'une certaine taille) et moyen (on considère le temps pour toute instance d'une certaine taille pondéré par la probabilité de cette instance).

II-C. Analyse asymptotique

On se contentera d'une analyse asymptotique, en considérant des instances très grandes. Cela simplifiera les calculs : on ne garde que le terme dominant en en ignorant le coefficient. En effet, même en augmentant considérablement la puissance de calcul, cela ne fera pas varier de manière significative le temps d'exécution de l'algorithme.

On utilisera trois notations :

  • kitxmlcodeinlinelatexdvpO(g)=\left\{ f\,\Big|\,\exists c>0,\, n_{0}\geq1\,:\,0\leq f(n)\leq c\times g(n),\,\forall n\geq n_{0}\right\}finkitxmlcodeinlinelatexdvp, on définit une borne supérieure asymptotique à la fonction ;
  • kitxmlcodeinlinelatexdvp\Omega(g)=\left\{ f\,\Big|\,\exists c>0,\, n_{0}\geq1\,:\,0\leq c\times g(n)\leq f(n),\,\forall n\geq n_{0}\right\}finkitxmlcodeinlinelatexdvp, on définit une borne inférieure asymptotique à la fonction ;
  • kitxmlcodeinlinelatexdvp\Theta(g)=\left\{ f\,\Big|\,\exists c_{1}>0,\, c_{2}>0,\, n_{0}\geq1\,:\,0\leq c_{1}\times g(n)\leq f(n)\leq c_{2}\times g(n),\,\forall n\geq n_{0}\right\}finkitxmlcodeinlinelatexdvp, on définit une borne serrée asymptotique à la fonction.

II-D. Analyse asymptotique serrée

On peut utiliser une analyse asymptotique plus précise que les notations introduites précédemment : par exemple, kitxmlcodeinlinelatexdvp2\, n=O\left(n^{2}\right)finkitxmlcodeinlinelatexdvp, alors que, asymptotiquement, la différence entre les deux fonctions est énorme. Avec la notation kitxmlcodeinlinelatexdvpOfinkitxmlcodeinlinelatexdvp, seules quelques constantes kitxmlcodeinlinelatexdvpcfinkitxmlcodeinlinelatexdvp peuvent convenir pour satisfaire kitxmlcodeinlinelatexdvp0\leq f\left(n\right)\leq c\, g\left(n\right)finkitxmlcodeinlinelatexdvp. En notation kitxmlcodeinlinelatexdvpofinkitxmlcodeinlinelatexdvp, cette relation est valable pour toute constante kitxmlcodeinlinelatexdvpc>0finkitxmlcodeinlinelatexdvp.

On introduit donc les notations suivantes.

  • kitxmlcodeinlinelatexdvpo\left(g\right)=\left\{ f\,\Big|\,\forall c>0,\exists n_{0}>0:0\leq f\left(n\right)<c\, g\left(n\right),\forall n\geq n_{0}\right\} finkitxmlcodeinlinelatexdvp ; notamment, cela implique que kitxmlcodeinlinelatexdvp\lim\limits _{n\to\infty}\dfrac{f\left(n\right)}{g\left(n\right)}=0finkitxmlcodeinlinelatexdvp.
  • kitxmlcodeinlinelatexdvp\omega\left(g\right)=\left\{ f\,\Big|\,\forall c>0,\exists n_{0}>0:0\leq c\, g\left(n\right)<f\left(n\right),\forall n\geq n_{0}\right\} finkitxmlcodeinlinelatexdvp ; notamment, cela implique que kitxmlcodeinlinelatexdvp\lim\limits _{n\to\infty}\dfrac{f\left(n\right)}{g\left(n\right)}=\inftyfinkitxmlcodeinlinelatexdvp.

III. Algorithmes de tri

III-A. Types de tri

On peut assigner une série d'adjectifs aux algorithmes de tri en fonction de leurs caractéristiques :

  • interne : en mémoire centrale, par opposition à externe (où les données ne sont pas accessibles aussi rapidement) ;
  • de tableau : qui trie une structure de données offrant un accès constant à ses éléments ;
  • générique : qui peut trier n'importe quel type d'objets comparables, sans hypothèse sur leur valeur ;
  • comparatif : basé sur la comparaison des clés des éléments ;
  • itératif : basé sur un ou plusieurs parcours itératifs du tableau, par opposition à récursif ;
  • en place : qui modifie directement la structure en cours de tri sans la dupliquer ;
  • stable : qui conserve l'ordre relatif des éléments égaux.

III-B. Tri par insertion

L'invariant : on considère la partie A[1..j-1] du tableau triée. À chaque itération, on va insérer la clé A[j] à sa bonne place en décalant d'un rang vers la droite tous les éléments plus grands que cette clé. Une fois qu'on trouve un élément égal ou plus petit, on l'insère juste après.

Cet algorithme a une complexité kitxmlcodeinlinelatexdvp\Theta(n^{2})finkitxmlcodeinlinelatexdvp dans les pire et moyen cas ; dans le meilleur, il suffit de comparer tous les éléments et la complexité est de kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp.

Tri par insertion : InsertionSort(A)
Sélectionnez
for j = 2 to A:length
	key = A[j]
	// Insert A[j] into the sorted sequence A[1..j-1].
	i = j - 1
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i + 1] = key

III-C. Tri par fusion

On sépare le tableau en deux sous-tableaux de même taille, que l'on trie récursivement ; ensuite, on fusionne les deux sous-tableaux en gardant l'ordre (application du principe de diviser pour régner). Le cas de base correspond au tri d'un seul élément, qui ne nécessite aucune opération.

Pour la fusion des tableaux, on prend trois paramètres tels que kitxmlcodeinlinelatexdvpp\leq q<rfinkitxmlcodeinlinelatexdvp, en sachant que les deux sous-tableaux à fusionner (A[p..q] et A[q+1..r]) sont déjà triés.

Tri par fusion : MergeSort(A, p, r)
Sélectionnez
if p < r
	q = round down (p+r)/2
	MergeSort(A, p, q)
	MergeSort(A, q + 1, r)
	Merge(A, p, q, r)
Fusion de tableaux : Merge(A, p, q, r)
Sélectionnez
n1 = q - p + 1
n2 = r - q
Let L[1..n1 + 1] and R[1..n2 + 1] be two new arrays
for i = 1 to n1
	L[i] = A[p + i - 1]
for j = 1 to n2
	R[j] = A[q + j]

L[n1 + 1] = 1
R[n2 + 1] = 1

i = 1
j = 1
for k = p to r
	if L[i] <= R[j]
		A[k] = L[i]
		i = i + 1
	else
		A[k] = R[j]
		j = j + 1

III-D. Tri rapide

Il s'agit d'un tri en place et non stable appliquant le principe du diviser pour régner. Sa complexité est kitxmlcodeinlinelatexdvpO(n^{2})finkitxmlcodeinlinelatexdvp dans le pire cas, bien que le cas moyen soit de la complexité optimale kitxmlcodeinlinelatexdvpO(n\,\log n)finkitxmlcodeinlinelatexdvp, le pire cas étant rare.

Le principe : pour trier un certain tableau A[p..r], on choisit un pivot (généralement le dernier élément, A[r]). Ensuite, on partitionne le tableau de telle sorte que tout élément de A[p..q-1] soit inférieur ou égal au pivot, déplacé en A[q], ainsi qu'à tout élément de A[q+1..r]. On applique ensuite récursivement l'algorithme sur chacun des deux demi-tableaux. Pour partitionner, on parcourt le tableau de gauche à droite ; on initialise la position future du pivot q à p, le début du sous-tableau à trier ; si l'élément courant est plus petit que le pivot, on le met à la position q et on incrémente q. Au final, on échange le dernier élément traité avec celui à la position q.

On peut en imaginer une série de variantes, notamment sur le choix du pivot : un élément au hasard, la médiane de trois éléments, etc. Cela diminue la chance de tomber dans le pire cas sans modifier la complexité tant que le choix s'effectue en temps constant.

On peut aussi remarquer que l'algorithme est lourd pour de petits tableaux (une vingtaine d'éléments), pour lesquels on pourra privilégier un algorithme plus naïf (par insertion, par exemple).

Tri rapide : QuickSort(A, begin, end)
Sélectionnez
if begin < end
	q = Partition(A, begin, end)
	QuickSort(A, begin, q - 1)
	QuickSort(A, q + 1, end)
Partition : Partition(A, p, r)
Sélectionnez
x = A[r]
i = p - 1
for j = p to r - 1
	if A[j] <= x
		i = i + 1
		swap(A[i];A[j])
swap(A[i + 1], A[r])
return i + 1

III-E. Tri par tas

III-E-1. Arbre

Un arbre est un graphe dirigé constitué d'un ensemble de nœuds reliés par des arcs. Ce graphe est connexe et acyclique. S'il est non vide, alors il possède un nœud distingué et unique, la racine. Un chemin est une séquence de nœuds dont toute paire consécutive est un arc de l'arbre. La hauteur d'un arbre est la distance entre la feuille la plus éloignée et la racine.

Un arbre ordonné est un arbre dans lequel l'ensemble des fils de chacun de ses nœuds est ordonné.

Un arbre est dit binaire si chacun de ses nœuds possède au plus deux fils (un gauche et un droit, le gauche précédent le droit).

Un arbre est dit parfait ou complet si toutes ses feuilles sont à la même distance de la racine.

Un arbre binaire entier ou propre (full ou proper) est un arbre binaire dans lequel tous les nœuds internes possèdent exactement deux fils. Pour ces arbres, on dispose de quelques propriétés :

  • le nombre de nœuds externes est égal au nombre de nœuds internes plus une unité ;
  • le nombre de nœuds internes est égal à kitxmlcodeinlinelatexdvp\frac{n-1}{2}finkitxmlcodeinlinelatexdvp, où kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est le nombre de nœuds ;
  • le nombre de nœuds à la profondeur (niveau) kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp est inférieur ou égal à kitxmlcodeinlinelatexdvp2^{i}finkitxmlcodeinlinelatexdvp ;
  • la hauteur de l'arbre est inférieure ou égale au nombre de ses nœuds internes.

On peut lier la hauteur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp et le nombre de nœuds kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp pour un arbre binaire entier par

kitxmlcodelatexdvpn\in\Omega(h)finkitxmlcodelatexdvp kitxmlcodelatexdvpn\in O(2^{h})finkitxmlcodelatexdvp

De manière équivalente,

kitxmlcodelatexdvph\in O(n)finkitxmlcodelatexdvp kitxmlcodelatexdvph\in\Omega(\log n)finkitxmlcodelatexdvp

III-E-2. Tas

Un arbre binaire complet (aussi dit tas) est un arbre binaire tel que, notant kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp la hauteur de l'arbre :

  • pour tout kitxmlcodeinlinelatexdvpi\in[0\,;\, h-1]finkitxmlcodeinlinelatexdvp, il y a exactement kitxmlcodeinlinelatexdvp2^{i}finkitxmlcodeinlinelatexdvp nœuds à la profondeur kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp ;
  • une feuille a une profondeur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp ou kitxmlcodeinlinelatexdvph-1finkitxmlcodeinlinelatexdvp ;
  • les feuilles de profondeur maximale sont tassées sur la gauche.

Un tas binaire est un arbre binaire complet tel que :

  • à chaque nœud est associée une clé ;
  • la clé de chaque nœud est supérieure ou égale à celle de ses fils (la propriété d'ordre du tas).

Un tas (un arbre binaire complet kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp entrées et de hauteur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp) dispose des propriétés suivantes :

  • kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est supérieur ou égal à la taille de l'arbre complet de hauteur kitxmlcodeinlinelatexdvph-1finkitxmlcodeinlinelatexdvp plus une unité, soit kitxmlcodeinlinelatexdvp2^{h}finkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est inférieur ou égal à la taille de l'arbre complet de hauteur kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp, soit kitxmlcodeinlinelatexdvp2^{h+1}-1finkitxmlcodeinlinelatexdvp.

On peut également écrire

kitxmlcodelatexdvp2^{h}\leq n\leq2^{h+1}-1finkitxmlcodelatexdvp kitxmlcodelatexdvph=\left\lfloor \log_{2}n\right\rfloorfinkitxmlcodelatexdvp

III-E-3. Interface

Pour un tas kitxmlcodeinlinelatexdvpHfinkitxmlcodeinlinelatexdvp, on définit les opérations suivantes :

  • kitxmlcodeinlinelatexdvpH.heapSizefinkitxmlcodeinlinelatexdvp : le nombre de clés de kitxmlcodeinlinelatexdvpHfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpBuildMaxHeap(A)finkitxmlcodeinlinelatexdvp : construire un tas à partir du tableau kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpHeapInsert(H,\, key)finkitxmlcodeinlinelatexdvp : insérer la valeur kitxmlcodeinlinelatexdvpkeyfinkitxmlcodeinlinelatexdvp dans le tas kitxmlcodeinlinelatexdvpHfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpHeapExtractMax(H)finkitxmlcodeinlinelatexdvp : récupérer la clé maximale.

III-E-4. Implémentation par un tableau

On peut représenter un tas de manière compacte par un tableau A : la racine de l'arbre est le premier élément, on peut accéder relativement aux autres éléments par ces quelques fonctions (elles renvoient l'indice à consulter).

  • kitxmlcodeinlinelatexdvpParent(i)=\left\lfloor \frac{i}{2}\right\rfloor finkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpLeft(i)=2\times ifinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpRight(i)=2\times i+1finkitxmlcodeinlinelatexdvp.

La propriété d'ordre du tas impose ainsi kitxmlcodeinlinelatexdvp\forall i,\, A[Parent(i)]\geq A[i]finkitxmlcodeinlinelatexdvp.

On peut alors implémenter les quelques méthodes du tas.

kitxmlcodeinlinelatexdvpMaxHeapifyfinkitxmlcodeinlinelatexdvp considère que les deux sous-arbres du nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp sont des tas et réarrange l'arbre pour qu'il soit un tas (il fait descendre l'élément kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp jusqu'à ce que l'arbre respecte la propriété d'ordre). Ensuite, on appelle récursivement l'algorithme du côté de l'élément qui a été déplacé (le cas échéant). Vu le lien entre la hauteur de l'arbre et le nombre de nœuds, on a une complexité de kitxmlcodeinlinelatexdvp\Theta(h)=\Theta(\log n)finkitxmlcodeinlinelatexdvp.

Restauration de la propriété de tas maximal : MaxHeapify(A, i)
Sélectionnez
l = Left(i)
r = Right(i)

if l <= A.heapSize and A[l] > A[i]
	largest = l
else
	largest = i

if r <= A.heapSize and A[r] > A[largest]
	largest = r

if largest 6= i
	swap(A[i];A[largest])
	MaxHeapify(A; largest)

kitxmlcodeinlinelatexdvpBuildMaxHeapfinkitxmlcodeinlinelatexdvp construit un tas à partir d'un tableau : à partir du premier nœud qui a un successeur (gauche, s'il n'y en a qu'un), on réorganise le tas et on remonte jusqu'à la racine. On effectue kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp appels à kitxmlcodeinlinelatexdvpMaxHeapifyfinkitxmlcodeinlinelatexdvp, d'où une complexité de kitxmlcodeinlinelatexdvpO(n\,\log n)finkitxmlcodeinlinelatexdvp ; une analyse plus fine sur un arbre binaire parfait atteint kitxmlcodeinlinelatexdvpO\left(\log n\right)finkitxmlcodeinlinelatexdvp.

Construction d'un tas maximal à partir d'un tableau : BuildMaxHeap(A)
Sélectionnez
A.heapSize = A.length
for i = (round down A.length/2) downto 1
	MaxHeapify(A, largest)

Pour l'insertion dans un tas, on insère l'élément à la fin (soit avec une clé infiniment négative), puis on le déplace jusqu'à la clé voulue.

Insertion : HeapInsert(A, key)
Sélectionnez
A.heapSize = A.heapSize + 1
A[A.heapSize] = - infinity
HeapIncreaseKey(A, A.heapSize, key)
Augmentation de la clé : HeapIncreaseKey(A, i, key)
Sélectionnez
if key < A[i]
	error new key is smaller than current key
A[i] = key
while i > 1 and A[Parent(i)] < A[i]
	swap(A[i], A[Parent(i)])
	i = Parent(i)

On peut également récupérer le maximum et l'éliminer du tas assez facilement (kitxmlcodeinlinelatexdvpO\left(1\right)finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpO\left(n\right)finkitxmlcodeinlinelatexdvp, respectivement : lecture et réorganisation).

Récupération du maximum : HeapMaximum(A)
Sélectionnez
return A[1]
Extraction du maximum : HeapExtractMax(A)
Sélectionnez
if A:heapSize < 1
	error \heap under
max = A[1]
A[1] = A[A.heapSize]
A:heapSize = A.heapSize - 1
MaxHeapify(A, 1) // rebuild the heap
return max

III-E-5. Tri par tas

À partir d'un tas, on récupère la racine, l'élément le plus élevé de tout le tas, on la remplace par le dernier élément. On place cette racine à la fin du tableau et on ne considère plus cette case comme partie du tas. On réordonne donc le reste du tableau comme un tas puis on recommence. Tout comme la construction d'un tas, cet algorithme a une complexité de kitxmlcodeinlinelatexdvp\Theta(n\,\log n)finkitxmlcodeinlinelatexdvp.

Tri par tas : HeapSort(A)
Sélectionnez
BuildMaxHeap(A)
for i = A.length downto 2
	swap(A[i], A[1])
	A.heapSize = A.heapSize - 1
	MaxHeapify(A, 1)

III-F. Résumé

Algorithme Complexité au pire cas Complexité moyenne Complexité au meilleur cas Tri en place ?
Tri par insertion kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\right)finkitxmlcodeinlinelatexdvp oui
Tri par sélection kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp oui
Tri à bulles kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp oui
Tri par fusion kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp non
Tri rapide kitxmlcodeinlinelatexdvp\Theta\left(n^2\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp oui
Tri par tas kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta\left(n\,\log n\right)finkitxmlcodeinlinelatexdvp oui

IV. Structures de données élémentaires

Une structure de données est une manière d'organiser et de stocker l'information pour en faciliter certaines opérations comme l'accès. Elle dispose d'une interface, un ensemble de procédures d'ajout, retrait, réorganisation, etc. des données. Elle conserve des données et des métadonnées (utilisées pour améliorer l'efficacité du traitement).

Un type de données abstrait est une définition des propriétés et de l'interface de la structure. Il admet généralement plusieurs implémentations, qui feront varier la complexité des opérations.

On distingue généralement deux types d'opérations : l'accès (en ce compris la recherche : minimum, élément suivant, etc.) et la modification (ajout, suppression, etc.).

IV-A. Pile

En anglais, stack.

Une pile est un ensemble dynamique d'objets accessibles selon une discipline LIFO. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpisEmpty(S)finkitxmlcodeinlinelatexdvp : renvoie vrai si et seulement si la pile kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp est vide ;
  • kitxmlcodeinlinelatexdvppush(S,\, x)finkitxmlcodeinlinelatexdvp : pousse la valeur kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp sur la pile kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvppop(S)finkitxmlcodeinlinelatexdvp : extrait et renvoie la valeur au sommet de la pile kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp.

On l'implémente généralement :

  • avec un tableau (bien que sa taille soit, a priori, de taille fixée). Complexité en temps des procédures : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ; en espace : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp. Cela signifie que la pile ne pourra pas grandir ; ici, ce n'est pas un avantage ;
  • avec une liste liée. Complexité en temps des procédures : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ; en espace : kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp.

IV-B. File

En anglais, queue.

Une file est un ensemble dynamique d'objets accessibles selon une discipline FIFO. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpenqueue(Q,\, s)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à la file kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpdequeue(Q)finkitxmlcodeinlinelatexdvp : retire l'élément à la tête de la file kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp.

On l'implémente généralement avec :

  • un tableau circulaire. Complexité en temps des procédures : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ; en espace : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ;
  • une liste liée. Complexité en temps des procédures : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ; en espace : kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp.

IV-C. File double

En anglais, double-ended queue ou deque.

Une file double est une collection ordonnée d'objets offrant la possibilité d'insérer ou d'extraire un élément à la tête ou à la queue. Il s'agit d'une généralisation des piles et files. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpinsertFirst(Q,\, x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp au début de la file double kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpinsertLast(Q,\, x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp à la fin de la file double kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpremoveFirst(Q)finkitxmlcodeinlinelatexdvp : extrait l'élément situé au début de la file double kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpremoveLast(Q)finkitxmlcodeinlinelatexdvp : extrait l'élément situé à la fin de la file double kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp.

On l'implémente généralement avec une liste liée. Complexité en temps des procédures : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ; en espace : kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp.

IV-D. Liste

Une liste est un ensemble dynamique d'objets ordonnés accessibles relativement les uns aux autres, sur base de leur position. Il s'agit d'une généralisation des piles, files et files doubles. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpinsertFirst(L,\, x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp au début de la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpinsertLast(L,\, x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp à la fin de la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpinsertAfter(L,\, p,\, x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp après kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp dans la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpinsertBefore(L,\, p,\, x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp avant kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp dans la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpremoveFirst(L)finkitxmlcodeinlinelatexdvp : extrait l'élément situé au début de la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpremoveLast(L)finkitxmlcodeinlinelatexdvp : extrait l'élément situé à la fin de la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpremove(L,\, p)finkitxmlcodeinlinelatexdvp : extrait l'élément situé à la position kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp de la liste kitxmlcodeinlinelatexdvpLfinkitxmlcodeinlinelatexdvp.

On l'implémente d'une manière similaire à la file double à l'aide d'une liste doublement liée et des sentinelles. Complexité en temps des procédures : kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp ; en espace : kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp.

IV-E. Vecteur

Un vecteur est un ensemble dynamique d'objets occupant des rangs entiers successifs permettant la consultation, le remplacement, l'insertion et la suppression d'éléments à des rangs arbitraires. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpat(V,\, r)finkitxmlcodeinlinelatexdvp : retourne l'élément situé au rang kitxmlcodeinlinelatexdvprfinkitxmlcodeinlinelatexdvp dans le vecteur kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpreplace(V,\, r,\, x)finkitxmlcodeinlinelatexdvp : remplace l'élément situé au rang kitxmlcodeinlinelatexdvprfinkitxmlcodeinlinelatexdvp dans le vecteur kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp par kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp et retourne l'élément remplacé ;
  • kitxmlcodeinlinelatexdvpinsert(V,\, r,\, x)finkitxmlcodeinlinelatexdvp : insère l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp au rang kitxmlcodeinlinelatexdvprfinkitxmlcodeinlinelatexdvp dans le vecteur kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpremove(V,\, r)finkitxmlcodeinlinelatexdvp : extrait l'élément situé au rang kitxmlcodeinlinelatexdvprfinkitxmlcodeinlinelatexdvp du vecteur kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp, en diminuant le rang des objets suivants ;
  • kitxmlcodeinlinelatexdvpsize(V)finkitxmlcodeinlinelatexdvp : renvoie la taille du vecteur.

On peut l'implémenter à l'aide d'une liste liée ou d'un tableau extensible (généralement préféré pour des temps d'accès constants ; lors de la réallocation du tableau, il faudra veiller à doubler la taille pour amortir ce coût).

IV-F. File à priorité

Une file à priorité est un ensemble dynamique d'objets classés par ordre de priorité, permettant d'extraire un objet ayant la plus grande priorité. Cela suppose un ordre total défini sur les clés. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpinsert(S,x)finkitxmlcodeinlinelatexdvp : insérer l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp dans la file kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpmaximum(S)finkitxmlcodeinlinelatexdvp : récupérer l'élément de kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp ayant la plus grande clé ;
  • kitxmlcodeinlinelatexdvpextractMaximum(S)finkitxmlcodeinlinelatexdvp : supprimer et renvoyer l'élément de kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp ayant la plus grande clé.

On peut l'implémenter à l'aide d'un tableau classique (insertion en kitxmlcodeinlinelatexdvpO(n)finkitxmlcodeinlinelatexdvp, vu qu'il faut garder le tableau trié ; extraction en kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp ; complexité en espace : kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp), d'une liste liée (mêmes complexités en temps ; en espace : kitxmlcodeinlinelatexdvpO(n)finkitxmlcodeinlinelatexdvp) ou d'un tas (renvoi du premier élément en kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp, il s'agit de récupérer l'élément maximal ; extraction du premier élément en kitxmlcodeinlinelatexdvpO(\log n)finkitxmlcodeinlinelatexdvp, vu qu'il faut restaurer la propriété de tas ; changement de clé d'un élément en kitxmlcodeinlinelatexdvpO(\log n)finkitxmlcodeinlinelatexdvp ; insertion en kitxmlcodeinlinelatexdvpO(\log n)finkitxmlcodeinlinelatexdvp ; complexité en espace : kitxmlcodeinlinelatexdvpO(n)finkitxmlcodeinlinelatexdvp).

V. Dictionnaires

V-A. Type de données abstrait

Un dictionnaire est un ensemble dynamique d'objets possédant des clés comparables, on supposera un ordre total sur ces clés. L'objectif est de minimiser le coût pour l'insertion et l'accès ainsi que pour le stockage. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpsearch(S,k)finkitxmlcodeinlinelatexdvp : retourne un pointeur kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp vers un élément de kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp tel que kitxmlcodeinlinelatexdvpx.key\,=\, kfinkitxmlcodeinlinelatexdvp ou kitxmlcodeinlinelatexdvpnilfinkitxmlcodeinlinelatexdvp s'il n'y a pas de tel objet ;
  • kitxmlcodeinlinelatexdvpinsert(S,x)finkitxmlcodeinlinelatexdvp : ajoute l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp dans le dictionnaire kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpdelete(S,x)finkitxmlcodeinlinelatexdvp : retire l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp du dictionnaire kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp.

V-A-1. Implémentations naïves

V-A-1-a. Liste liée

On stocke les paires clé-valeur dans une liste liée. Les complexités seront linéaires pour l'insertion, la recherche et la suppression : à chaque fois, il faut parcourir la liste pour trouver si un élément correspond (pour insertion juste après, renvoi ou suppression).

V-A-1-b. Vecteur trié

Si on a un ordre total sur les clés, on peut stocker les données dans un vecteur maintenu trié. Insertion et suppression requièrent une recherche et un décalage de tous les éléments, leur complexité reste linéaire. La recherche peut être optimisée avec une recherche dichotomique (kitxmlcodeinlinelatexdvpO(\log n)finkitxmlcodeinlinelatexdvp).

V-B. Arbre

Les arbres binaires de recherches permettront d'implémenter une insertion et une recherche efficaces dans un dictionnaire (logarithmique dans le cas moyen, mais toujours linéaire dans le pire cas tant qu'on n'équilibre pas).

V-B-1. Type de données abstrait

Un arbre est constitué de nœuds, accessibles les uns par rapport aux autres selon leur position ; les données sont associées à ces nœuds. Son interface est constituée de :

  • kitxmlcodeinlinelatexdvpparent(T,n)finkitxmlcodeinlinelatexdvp : renvoie le parent de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp, sauf si kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est la racine ;
  • kitxmlcodeinlinelatexdvpchildren(T,n)finkitxmlcodeinlinelatexdvp : renvoie une structure de données des fils de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpleft(T,n)finkitxmlcodeinlinelatexdvp : renvoie le fils gauche de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre binaire kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpright(T,n)finkitxmlcodeinlinelatexdvp : renvoie le fils droit de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre binaire kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvproot(T)finkitxmlcodeinlinelatexdvp : renvoie la racine de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpisRoot(T,n)finkitxmlcodeinlinelatexdvp : renvoie vrai si de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est la racine de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpisInternal(T,n)finkitxmlcodeinlinelatexdvp : renvoie vrai si de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est un nœud interne de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpisExternal(T,n)finkitxmlcodeinlinelatexdvp : renvoie vrai si de l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est un nœud externe de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpgetData(T,n)finkitxmlcodeinlinelatexdvp : renvoie les données associées à l'élément kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp dans l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ;
  • kitxmlcodeinlinelatexdvpsize(T)finkitxmlcodeinlinelatexdvp : renvoie le nombre de nœuds de l'arbre kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp.

V-B-2. Implémentation d'un arbre binaire

V-B-2-a. Vecteur

Tout l'arbre est représenté par un vecteur, où chaque position est indiquée par l'index : la racine est à la position kitxmlcodeinlinelatexdvp1finkitxmlcodeinlinelatexdvp, le successeur gauche d'un nœud de rang kitxmlcodeinlinelatexdvprfinkitxmlcodeinlinelatexdvp sera à l'index kitxmlcodeinlinelatexdvp2\, rfinkitxmlcodeinlinelatexdvp, le successeur droit au rang kitxmlcodeinlinelatexdvp2\, r+1finkitxmlcodeinlinelatexdvp.

Cependant, si l'arbre binaire n'est pas complet, on aura des trous : la complexité en espace pour le stockage de kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp nœuds sera de kitxmlcodeinlinelatexdvpO(2^{n})finkitxmlcodeinlinelatexdvp, au lieu de kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp pour un arbre binaire complet. Les opérations auront une complexité en temps de kitxmlcodeinlinelatexdvpO\text{(1)}finkitxmlcodeinlinelatexdvp.

V-B-2-b. Structure liée

Pour chaque nœud kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp de l'arbre binaire, on retient un champ de données (kitxmlcodeinlinelatexdvpn.datafinkitxmlcodeinlinelatexdvp), un pointeur vers le nœud parent (kitxmlcodeinlinelatexdvpn.parentfinkitxmlcodeinlinelatexdvp) et un pointeur pour chaque fils (kitxmlcodeinlinelatexdvpn.leftfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpn.rightfinkitxmlcodeinlinelatexdvp). Cette manière de procéder peut s'extrapoler facilement à des arbres non binaires ; on utilisera un champ kitxmlcodeinlinelatexdvpn.keyfinkitxmlcodeinlinelatexdvp pour retenir la clé de l'élément. On aura une complexité en espace de kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp, vu qu'on ne crée que les éléments nécessaires ; les opérations auront une complexité en temps de kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp.

V-B-3. Parcours en profondeur

On va descendre dans l'arbre avant d'aller visiter les nœuds voisins.

V-B-3-a. Parcours infixe (en ordre)

Chaque nœud est visité après son fils gauche et avant son fils droit.

Parcours infixe d'un arbre binaire : InorderTreeWalk(x)
Sélectionnez
if x != nil
	InorderTreeWalk(x.left)
	walk(x.key)
	InorderTreeWalk(x.left)
V-B-3-b. Parcours préfixe (en préordre)

Chaque nœud est visité avant ses fils.

Parcours préfixe d'un arbre binaire : PreorderTreeWalk(x)
Sélectionnez
if x != nil
	walk(x.key)
	InorderTreeWalk(x.left)
	InorderTreeWalk(x.left)
V-B-3-c. Parcours postfixe (en postordre)

Chaque nœud est visité après ses fils.

Parcours postfixe d'un arbre binaire : PostorderTreeWalk(x)
Sélectionnez
if x != nil
	InorderTreeWalk(x.left)
	InorderTreeWalk(x.left)
	walk(x.key)
V-B-3-d. Complexité

Tous les parcours en profondeur ont une complexité en temps de kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp. En effet, on doit parcourir au moins une fois chaque nœud :

kitxmlcodelatexdvpT(n)=\Omega(n)\,;finkitxmlcodelatexdvp

kitxmlcodeinlinelatexdvpn_{L}finkitxmlcodeinlinelatexdvp étant le nombre de nœuds à gauche et kitxmlcodeinlinelatexdvpdfinkitxmlcodeinlinelatexdvp une constante, on a la récursion

kitxmlcodelatexdvpT(n)\leq T(n_{L})+T(n-n_{L}-1)+d.finkitxmlcodelatexdvp

Par induction, on prouve alors que

kitxmlcodelatexdvpT(n)<(c+d)\, n,finkitxmlcodelatexdvp

avec

kitxmlcodelatexdvpc=T(0).finkitxmlcodelatexdvp

On a donc prouvé

kitxmlcodelatexdvpT(n)=O(n),finkitxmlcodelatexdvp

soit, vu la borne inférieure,

kitxmlcodelatexdvpT(n)=\Theta(n).finkitxmlcodelatexdvp

V-B-4. Parcours en largeur

On visite le nœud le plus proche de la racine qui n'a pas été visité, soit d'abord la racine, puis ses enfants, les nœuds du deuxième niveau et ainsi de suite. On peut l'implémenter à l'aide d'une file avec une complexité en temps de kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp :

Parcours en largeur d'un arbre binaire : BreadthTreeWalk(x)
Sélectionnez
Q = new empty queue
Enqueue(Q, x)
while not QueueEmpty(Q)
	y = Dequeue(Q)
	walk(y.key)
	if y.left != NIL
		Enqueue(Q, y.left)
	if y.right != NIL
		Enqueue(Q, y.right)

V-C. Arbre binaire de recherche

Un arbre binaire de recherche est une structure d'arbre binaire implémentant un dictionnaire dont les opérations sont en kitxmlcodeinlinelatexdvpO(h)finkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp étant la hauteur de l'arbre. La propriété d'arbre binaire de recherche est la suivante, exprimée pour deux nœuds kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp :

  • si kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est dans le sous-arbre de gauche de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, alors kitxmlcodeinlinelatexdvpy.key<x.keyfinkitxmlcodeinlinelatexdvp ;
  • si kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est dans le sous-arbre de droite de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, alors kitxmlcodeinlinelatexdvpy.key\geq x.keyfinkitxmlcodeinlinelatexdvp.

Un parcours infixe d'un tel arbre donnera les clés par ordre croissant.

Toutes les opérations auront une complexité dans le pire cas de kitxmlcodeinlinelatexdvpO(h)finkitxmlcodeinlinelatexdvp. En supposant que les éléments ont été insérés en ordre aléatoire, on peut montrer que kitxmlcodeinlinelatexdvph\in O(\log n)finkitxmlcodeinlinelatexdvp.

V-C-1. Recherche

Une recherche (récursive terminale ou itérative) dans un tel arbre aura une complexité kitxmlcodeinlinelatexdvpO(h)finkitxmlcodeinlinelatexdvp.

Recherche récursive terminale : TreeSearch(x, k)
Sélectionnez
if x == NIL or k == x.key
	return x
if k < x.key
	return TreeSearch(x.left, k)
else
	return TreeSearch(x.right, k)
Recherche itérative : IterativeTreeSearch(x, k)
Sélectionnez
x = T.root
while x != NIL and k != x:key
	if k < x.key
		x = x.left
	else
		x = x.right
return x

V-C-2. Maximum et minimum

Au vu de la propriété d'arbre binaire de recherche, la clé minimale est stockée dans le nœud le plus à gauche et la clé maximale dans le nœud le plus à droite.

Recherche du minimum : TreeMinimum(x)
Sélectionnez
while x.left != NIL
	x = x.left
return x
Recherche du maximum : TreeMaximum(x)
Sélectionnez
while x.right != NIL
	x = x.right
return x

V-C-3. Successeur

On veut, à partir d'un nœud kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, trouver le nœud contenant la valeur de clé suivante, selon un ordre arithmétique. Si le sous-arbre de droite du nœud existe, alors le successeur en est le minimum. Sinon, il s'agit du premier ancêtre kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp tel que kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp est dans le sous-arbre de gauche de kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp.

Recherche du successeur : TreeSuccessor(x)
Sélectionnez
if x.right != NIL
	return TreeMinimum(x.right)
y = x.parent
while y != NIL and x == y.right
	x = y
	y = y.parent
return y

V-C-4. Insertion

Pour insérer un élément, on recherche sa clé dans l'arbre et on l'insère là où la recherche s'est arrêtée dans le cas où elle n'existe pas encore.

Insertion : TreeInsert(T, z)
Sélectionnez
y = NIL
x = T.root
while x != nil
	y = x
	if z.key < x.key
		x = x.left
	else
		x = x.right
z.parent = y
if y == NIL
	// Tree T was empty
	T.root = z
elseif z.key < y.key
	y. left = z
else
	y.right = z

V-C-5. Suppression

Trois cas particuliers sont à considérer : un seul fils ou deux fils. S'il n'y a pas de fils, il suffit de supprimer toute référence au nœud. Le but est toujours de garder la propriété d'arbre binaire de recherche. Pour supprimer le nœud kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp :

  • s'il n'a qu'un seul fils : le remplacer par celui-ci ;

  • s'il a deux fils : rechercher le successeur kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp :

    • si kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est le fils droit de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, remplacer kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp par kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp et conserver le fils droit de kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp,
    • sinon, kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est dans le sous-arbre droit de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp sans en être la racine ; on remplace kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp par son propre fils droit et on remplace kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp par kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp.
Transplantation : Transplant(T, u, v)
Sélectionnez
if u.parent == NIL
	T.root = v
elseif u == u.parent.left
	u.parent.left = v
else
	u.parent.right = v
if v != NIL
	v.parent = u.parent
Suppression : TreeDelete(T, z)
Sélectionnez
if z.left == NIL
	Transplant(T, z, z.right)
elseif z.right == NIL
	Transplant(T, z, z.left)
else // z has two children
	y = TreeSuccessor(z)
	if y.parent != z
		Transplant(T, y, y.right)
		y.right = z.right
		y.right.parent = y
	// Replace z by y
	Transplant(T, z, y)
	y.left = z.left
	y.left.parent = y

V-C-6. Tri

Un tri dans l'ordre croissant correspond à un parcours infixe de l'arbre binaire de recherche. Sa complexité en temps est identique à celle du tri rapide, bien que sa complexité en espace soit plus importante, étant donné la structure sous-jacente.

Tri par arbre binaire de recherche : BinarySearchTreeSort(A)
Sélectionnez
T = new empty binary search tree
for i = 1 to n
	TreeInsert(T;A[i])
InorderTreeWalk(T:root)

V-D. Arbre équilibré

Pour obtenir une complexité moindre, il faut maintenir un invariant sur la structure de l'arbre et prouver qu'il garantit une hauteur kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp.

V-D-1. Arbre H-équilibré

On étudiera ici les arbres AVL (Adelson-Velskii-Landis), qui ont la propriété d'être H-équilibrés. Leur invariant est, pour tout sous-arbre kitxmlcodeinlinelatexdvpT'finkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp,

kitxmlcodelatexdvp\Big|h(g(T'))-h(d(T'))\Big|\leq1.finkitxmlcodelatexdvp

Les hauteurs des deux sous-arbres d'un nœud diffèrent au plus d'une unité. Un tel arbre aura une hauteur bornée par

kitxmlcodelatexdvph\in\Theta(\log n).finkitxmlcodelatexdvp

Précisément, on peut prouver que

kitxmlcodelatexdvp\log(n+1)\leq h+1\leq1,44\,\,\log(n+2).finkitxmlcodelatexdvp

V-D-2. Arbre AVL

Un arbre AVL (Adelson-Velskii-Landis) est un arbre binaire de recherche H-équilibré. En tant qu'arbre binaire de recherche, on peut utiliser l'algorithme des arbres binaires de recherche pour la recherche ; il aura une complexité de kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp, vu la propriété.

Pour l'insertion, on procèdera comme pour un arbre binaire classique) ; ensuite, on rétablira l'invariant au besoin à l'aide de rotations.

V-D-2-a. Rotations
Image non disponible
Rotations dans les arbres AVL.

Ces rotations sont implémentées à l'aide des algorithmes suivants.

Rotation gauche : LeftRotate(x)
Sélectionnez
r = x.right
x.right = r.left
r.left = x
return r
Rotation droite : RightRotate(x)
Sélectionnez
r = x.left
x.left = r.right
r.right = x
return r
V-D-2-b. Équilibrage

On prend kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, le nœud le plus bas violant l'invariant après insertion. Tous ses sous-arbres sont H-équilibrés, il y a cependant une différence de deux niveaux entre ses sous-arbres gauche et droit. Pour rétablir l'équilibre (en cas de déséquilibre à gauche ou à droite), on devra effectuer une ou deux rotations. Ainsi, l'insertion aura une complexité logarithmique par rapport au nombre de nœuds.

V-D-2-c. Tri

On peut utiliser un arbre AVL pour le tri : on insère successivement les éléments dans l'arbre et on effectue un parcours en ordre. On aura une complexité temporelle optimale (kitxmlcodeinlinelatexdvp\Theta(n\,\log n)finkitxmlcodeinlinelatexdvp), mais une complexité en espace linéaire (on doit allouer un arbre).

V-E. Table de hachage

V-E-1. Tableau à accès direct

On suppose que chaque élément est associé à une clé unique tirée d'un univers pas trop grand, kitxmlcodeinlinelatexdvpU=\{1\ldots m-1\}finkitxmlcodeinlinelatexdvp. Le dictionnaire est alors implémenté par le tableau kitxmlcodeinlinelatexdvpT[0\ldots m-1]finkitxmlcodeinlinelatexdvp, chaque position correspondant à une clé de l'univers. Si le dictionnaire contient un élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp avec la clé kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp, alors kitxmlcodeinlinelatexdvpT[k]finkitxmlcodeinlinelatexdvp contient un pointeur vers kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp. Sinon, kitxmlcodeinlinelatexdvpT[k]finkitxmlcodeinlinelatexdvp est un pointeur nul.

On a ainsi un dictionnaire à accès en temps constant, ainsi que la suppression et la recherche. Sa taille sera constante (kitxmlcodeinlinelatexdvp\Theta(\#U)finkitxmlcodeinlinelatexdvp), il ne pourra pas retenir plusieurs éléments avec la même clé. Si l'ensemble des clés utilisées est très inférieur à l'univers, alors on gaspille beaucoup de place.

V-E-2. Table de hachage

On utilise un tableau kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp de taille largement inférieure à la taille de l'univers. On placera l'élément kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp de clé kitxmlcodeinlinelatexdvpx.keyfinkitxmlcodeinlinelatexdvp à la position kitxmlcodeinlinelatexdvph(x.key)finkitxmlcodeinlinelatexdvp, où kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp est une fonction de hachage qui établit un lien entre l'univers kitxmlcodeinlinelatexdvpUfinkitxmlcodeinlinelatexdvp et l'ensemble des clés de kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp.

Cependant, on a un risque de collision : deux clés distinctes ont la même image par la fonction de hachage. Par le principe des tiroirs, cela se produit toujours lorsqu'on a plus d'éléments à stocker que la taille du tableau. Selon le paradoxe des anniversaires, c'est même très probable, même si la fonction de hachage répartit les clés de manière uniforme.

Deux solutions pour éviter les collisions : une fonction de hachage qui répartit de manière uniforme les clés ou un tableau de taille suffisante. Dans chaque cas, en cas de remplissage suffisant, la probabilité de collision restera élevée. Deux approches résolvent définitivement ce problème : l'adressage ouvert et l'adressage fermé.

V-E-3. Fonction de hachage

Idéalement, une fonction de hachage devrait être facile à calculer (en temps constant) et satisfaire l'hypothèse de hachage uniforme, ce qui n'est pas forcément facile à obtenir (on ne connaît généralement pas la distribution des clés et elles ne sont pas forcément indépendantes). Une telle fonction suppose que la clé est un nombre naturel (sinon, il faut la coder : par exemple, pour une chaîne de caractères, prendre la valeur ASCII de chaque caractère, la pondérer par kitxmlcodeinlinelatexdvp128^{i}finkitxmlcodeinlinelatexdvp et sommer).

V-E-3-a. Méthode de division

La fonction de hachage calcule le reste de la division entière de la clé par la taille de la table :

kitxmlcodelatexdvph(k)=k\mod\, m.finkitxmlcodelatexdvp

Cette manière de procéder est très rapide, mais dépend beaucoup du choix de kitxmlcodeinlinelatexdvpmfinkitxmlcodeinlinelatexdvp : si kitxmlcodeinlinelatexdvpm=2^{p}finkitxmlcodeinlinelatexdvp, alors le résultat ne dépend que des kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp bits les moins significatifs ; si kitxmlcodeinlinelatexdvpm=2^{p}-1finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp est une chaîne de caractères codée en base kitxmlcodeinlinelatexdvp2^{p}finkitxmlcodeinlinelatexdvp, alors permuter les caractères de kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp n'influence pas le résultat ; si les clés sont périodiques et kitxmlcodeinlinelatexdvpmfinkitxmlcodeinlinelatexdvp est non premier, on n'exploite qu'une partie des valeurs possibles (pour kitxmlcodeinlinelatexdvpm=100finkitxmlcodeinlinelatexdvp, l'image de kitxmlcodeinlinelatexdvp\{206,211,216,221\}finkitxmlcodeinlinelatexdvp sera kitxmlcodeinlinelatexdvp\{6,11,16,21\}finkitxmlcodeinlinelatexdvp).

V-E-3-b. Méthode de multiplication

Avec une constante kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp telle que kitxmlcodeinlinelatexdvp0<A<1finkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpk\, A\mod1finkitxmlcodeinlinelatexdvp est la partie fractionnaire de kitxmlcodeinlinelatexdvpk\, Afinkitxmlcodeinlinelatexdvp, on utilise la fonction

kitxmlcodelatexdvph(k)=\bigg\lfloor m\cdot(k\, A\mod1)\bigg\rfloorfinkitxmlcodelatexdvp

La valeur de kitxmlcodeinlinelatexdvpmfinkitxmlcodeinlinelatexdvp n'est plus critique, mais certaines valeurs de kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp fonctionnent mieux.

V-E-4. Chaînage (adressage fermé)

Simplement, on stocke les éléments qui ont le même hash dans une liste (doublement) liée. On aura une insertion (en début de liste) en temps constant, une suppression linéaire pour une liste liée ou constante pour une liste doublement liée, une recherche linéaire du nombre d'éléments dans la liste, du moins dans le pire cas.

Afin d'étudier la complexité dans le cas moyen, on définit le facteur de charge

kitxmlcodelatexdvp\alpha=\frac{n}{m}finkitxmlcodelatexdvp

où kitxmlcodeinlinelatexdvpmfinkitxmlcodeinlinelatexdvp est la taille du tableau et kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp le nombre d'éléments stockés. On supposera le hachage parfaitement uniforme : pour toute clé kitxmlcodeinlinelatexdvpk\in Ufinkitxmlcodeinlinelatexdvp, on a

kitxmlcodelatexdvpP\bigg(h(k)=i\bigg)=\frac{1}{m},\forall i\in\{0\ldots m-1\}finkitxmlcodelatexdvp

On considérera également que la fonction de hachage kitxmlcodeinlinelatexdvphfinkitxmlcodeinlinelatexdvp a une complexité temporelle kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp et que l'on insère les éléments en début de liste.

Ainsi, dans le cas moyen, que la recherche soit positive ou non, on aura une complexité temporelle de kitxmlcodeinlinelatexdvp\Theta(1+\alpha)finkitxmlcodeinlinelatexdvp (kitxmlcodeinlinelatexdvp\alphafinkitxmlcodeinlinelatexdvp pouvant être aussi bien inférieur à l'unité ou très grand, en fonction du remplissage). Si on a

kitxmlcodelatexdvpn\in O(m),finkitxmlcodelatexdvp

soit si kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp croît au moins linéairement avec la taille du tableau, on aura

kitxmlcodelatexdvp\alpha=\frac{O(m)}{m}=O(1).finkitxmlcodelatexdvp

Toutes les opérations seront kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp en moyenne.

V-E-4-a. Critique

On peut gérer un nombre illimité d'éléments et de collisions, les performances restant stables. On a cependant un surcoût lié à la gestion et au stockage des listes liées.

V-E-5. Sondage (adressage ouvert)

On stocke tous les éléments dans le tableau : une fois celui-ci rempli, on ne peut plus ajouter d'élément. Pour insérer une clé kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp, on sonde toutes les autres cases à partir de kitxmlcodeinlinelatexdvph(k,0)finkitxmlcodeinlinelatexdvp en suivant une fonction de sondage kitxmlcodeinlinelatexdvph(k,i)finkitxmlcodeinlinelatexdvp.

La fonction de hachage est ainsi définie sur kitxmlcodeinlinelatexdvpU\times[0\,;m-1]finkitxmlcodeinlinelatexdvp et telle que

kitxmlcodelatexdvp<h(k,0)\ldots h(k,m-1)>finkitxmlcodelatexdvp

est une permutation de kitxmlcodeinlinelatexdvp[0\,;m-1]finkitxmlcodeinlinelatexdvp.

Pour supprimer, on ne peut pas simplement mettre un pointeur nul à l'endroit qui vient d'être libéré, on ne saurait jamais si on doit poursuivre la recherche. On utilise donc une valeur spéciale : lors de la recherche, on sait qu'on devra continuer ; lors d'une insertion, la case est considérée vide. Ainsi, le temps de recherche ne dépend plus du facteur de charge, mais de la charge maximale de la table.

Une stratégie de sondage efficace donnera un hachage uniforme : chacune des permutations de kitxmlcodeinlinelatexdvp[0\,;1]finkitxmlcodeinlinelatexdvp a la même probabilité de correspondre à une clé. Cela est cependant dur à garantir, on se satisfera généralement du fait que l'on a une permutation.

  • Sondage linéaire : facile à implémenter, on se limite à aller voir la case suivante ; on crée ainsi un fort effet de grappe, pas d'uniformité ; on a la fonction

    kitxmlcodelatexdvph(k,i)=\bigg(h(k)+i\bigg)\mod m.finkitxmlcodelatexdvp
  • Sondage quadratique : à l'aide de deux constantes bien choisies (pour garder la propriété de permutation), on effectue un parcours quadratique de la table ; l'effet de grappe est toujours présent, bien que moins marqué ; on a la fonction

    kitxmlcodelatexdvph(k,i)=\bigg(h(k)+c_{1}\, i+c_{2}\, i^{2}\bigg)\mod m.finkitxmlcodelatexdvp
  • Double hachage : on utilise deux fonctions de hachage différentes, à bien choisir pour garder la permutation ; le résultat sera très proche de l'uniformité, bien meilleur que les techniques précédentes ; on aura la fonction

    kitxmlcodelatexdvph(k,i)=\bigg(h(k)+i\, h'(k)\bigg)\mod m.finkitxmlcodelatexdvp
V-E-5-a. Critique

Limitée par la taille du tableau, cette méthode est rapide et peu gourmande en mémoire, bien que plus ardue à implémenter pour éviter les grappes. Les suppressions sont problématiques et les performances dégringolent dès que la table est bien remplie (on peut envisager de créer une table plus grande pour stocker les éléments, mais cela empêche d'utiliser la table pendant un certain temps et il faut sélectionner une nouvelle fonction de hachage et réinsérer tous les éléments ; on garde cependant le même coût asymptotique si on double la taille, par amortissement).

V-F. Résumé

  Complexité en recherche Complexité en insertion Complexité en suppression
Implémentation Pire cas Cas moyen Pire cas Cas moyen Pire cas Cas moyen
Liste kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp
Vecteur trié kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp
Arbre binaire de recherche kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp
Arbre équilibré kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(\log n)finkitxmlcodeinlinelatexdvp
Table de hachage kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(n)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\Theta(1)finkitxmlcodeinlinelatexdvp

V-F-1. Arbres de recherche ou table de hachage ?

Une table de hachage est facile à implémenter, la seule solution disponible pour des clés non ordonnées, a des recherche et insertion très rapides en moyenne, mais gaspille de l'espace en faible facteur de charge ; dans le pire cas, les performances ne sont pas garanties.

Un arbre binaire de recherche (équilibré ou non ; ABR ou AVL) aura des performances garanties, ne gaspillera pas de mémoire, supportera plus d'opérations car les clés sont ordonnées, bien que l'accès et l'insertion soient plus lents en moyenne.

VI. Résolution de problèmes

VI-A. Force brute

Cette approche résout directement le problème à partir de sa définition ou d'une recherche exhaustive.

En appliquant la définition, elle mène aux tris à bulle et par sélection, de complexité quadratique ; par recherche exhaustive, on générera tous les tableaux possibles par permutation, on sélectionnera le premier à être ordonné : cette approche a une complexité temporelle de kitxmlcodeinlinelatexdvpO(n\cdot n!)finkitxmlcodeinlinelatexdvp.

Bien que parfois seule solution possible (problème du voyageur de commerce), il existe généralement de meilleures solutions. Cette technique est très simple et d'application très large, il s'agit donc d'un bon point de départ pour trouver d'autres algorithmes plus performants (faire mieux n'a pas toujours d'intérêt), plus élégants et créatifs.

VI-B. Diviser pour régner

On divise le problème en sous-problèmes plus faciles à résoudre (jusqu'au cas de base) que l'on fusionne pour obtenir la solution du problème original. On trouve donc trois étapes : diviser (diviser le problème), régner (résoudre récursivement les sous-problèmes jusqu'au cas de base, trivial à résoudre) et fusionner (à partir des solutions des sous-problèmes, trouver la solution du problème original).

Cette approche mène aux tris par fusion et rapide, deux algorithmes de complexité optimale (au lieu de quadratique par force brute).

Elle mène à des algorithmes efficaces, cette méthode est donc très utile, bien qu'elle ne soit pas toujours applicable.

VI-C. Programmation dynamique

On cherche à obtenir la solution optimale en combinant des solutions optimales de sous-problèmes se chevauchant. Il s'agit d'une généralisation de l'approche précédente : les sous-problèmes peuvent se chevaucher, dépendre l'un de l'autre. Notamment, quand le même sous-problème apparaît plusieurs fois, on s'arrange pour ne le résoudre qu'une seule en sauvegardant les solutions dans une table (on échange du temps de calcul contre de la mémoire). En général, on peut transformer un problème de complexité exponentielle en une classe polynomiale.

On en distingue deux cas : la programmation dynamique descendante avec mémoization (on résout le problème en partant des plus grandes instances de manière récursive en sauvegardant les résultats intermédiaires dans un tableau qui est passé à chaque appel) et la programmation dynamique ascendante (on résout d'abord les instances de petite taille jusqu'à la taille demandée, puis on retourne la valeur obtenue, sans récursivité).

Il est nécessaire de disposer de la propriété de sous-structure optimale : une solution optimale est composée de solutions optimales à des sous-problèmes.

La procédure générale consiste à définir de manière récursive la valeur à optimiser de la meilleure solution, puis à calculer ces valeurs pour reconstruire (à partir du tableau généré) une solution optimale (approche bottom-up).

On ne peut cependant pas utiliser la récursivité pour implémenter ces algorithmes de manière efficace : alors que l'approche diviser pour régner divise les problèmes en instances significativement plus petites (kitxmlcodeinlinelatexdvp\frac{n}{2}finkitxmlcodeinlinelatexdvp) et totalement indépendantes, la programmation dynamique n'en réduira la taille que de très peu (kitxmlcodeinlinelatexdvpn-1finkitxmlcodeinlinelatexdvp) tout en gardant une certaine dépendance.

VI-D. Approche gloutonne

On construit incrémentalement la solution en optimisant localement pour obtenir un optimum global. On doit donc effectuer à chaque fois un choix, alors que la programmation dynamique explore tous les choix possibles. En fonction des problèmes, des entrées et des paramètres, on pourrait n'obtenir qu'une bonne solution pas forcément optimale (on doit explorer tous les choix pour s'en assurer : programmation dynamique). Dans tous les cas, on ne récupérera qu'une solution optimale au problème.

Quand on a un choix local à faire, on effectue un choix glouton qui semble le meilleur immédiatement (sans jamais le remettre en question). Pour que l'algorithme soit correct, il faut donc prouver la propriété des choix gloutons optimaux (en effectuant ce choix de manière locale, on arrive toujours à une solution optimale). Pour que l'approche fonctionne, il faut aussi prouver la propriété de sous-structure optimale : une solution optimale du problème est composée de solutions optimales à des sous-problèmes. Si ces propriétés ne sont pas vérifiées, l'approche ne donnera pas forcément un optimal mais bien une approximation (on peut, dans certains cas, en caractériser la distance à l'optimal).

Quand un tel algorithme existe, il est très efficace et simple à implémenter. Cependant, quand il existe, sa correction peut être assez difficile à établir.

Par rapport à la programmation dynamique, on doit prouver la propriété des choix gloutons optimaux. Grâce à celle-ci, on n'aura pas besoin de résoudre plusieurs sous-problèmes : il est effectué avant de résoudre un sous-problème. Il n'y a pas besoin de stocker les résultats intermédiaires, la solution obtenue ne doit pas être recomposée.

VII. Graphes

VII-A. Définitions

Un graphe est un couple kitxmlcodeinlinelatexdvp(V,E)finkitxmlcodeinlinelatexdvp, où kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp est un ensemble de nœuds (sommets) et kitxmlcodeinlinelatexdvpE\subseteq V\times Vfinkitxmlcodeinlinelatexdvp un ensemble d'arcs (ou arêtes). Une arête est un ensemble de deux sommets kitxmlcodeinlinelatexdvp(u,v)finkitxmlcodeinlinelatexdvp. Un graphe non dirigé (ou non orienté) est caractérisé par une relation symétrique entre les sommets.

Deux nœuds sont adjacents s'ils sont liés par une même arête ; cette arête sera incidente à ces deux nœuds. Le degré d'un nœud est le nombre de ses arêtes incidentes. Le degré d'un graphe est le nombre maximal d'arêtes incidentes à un sommet.

Un graphe sera connexe s'il existe un chemin de tout sommet à tout autre (en suivant le sens des arêtes, le cas échéant). Une composante connexe d'un graphe non orienté est un sous-ensemble connexe maximal de ce graphe (si on ajoute un nœud du graphe étudié, il ne sera plus connexe).

Dans un graphe dirigé, une arête kitxmlcodeinlinelatexdvp(u,v)finkitxmlcodeinlinelatexdvp possède l'origine kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et la destination kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp. Cette arête sera sortante pour kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et entrante pour kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp. On définit ainsi les degrés entrant et sortant. Un graphe acyclique n'a aucun cycle : il n'est pas possible de suivre les arêtes du graphe à partir d'un sommet et de revenir à ce même sommet.

Un graphe simple ne possède pas de boucle composée d'une seule arête : kitxmlcodeinlinelatexdvp\forall v\in V,\,(v,v)\not\in Efinkitxmlcodeinlinelatexdvp. Un arbre est un graphe acyclique connexe. Un multigraphe est une généralisation des graphes pour laquelle il est permis de définir plus d'une arête liant un sommet à l'autre. Un graphe pondéré aura des arêtes annotées par des poids.

Un sommet kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp est accessible à partir de kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp si kitxmlcodeinlinelatexdvpu=vfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp est adjacent à kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp ou si kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp est adjacent à un sommet de kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp accessible à partir de kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp.

VII-B. Représentations

De manière très naïve, on pourrait représenter un graphe comme une liste de nœuds et d'arêtes, mais cette solution n'est pas la plus efficace.

On peut utiliser, pour chaque nœud, une liste d'adjacence : des listes liées pour chaque nœud indiquant les autres extrémités des arêtes. Si on associe un poids à chaque élément de la liste, on peut représenter un graphe pondéré ; on peut représenter indifféremment un graphe dirigé ou non (on insérera chaque arête deux fois). Pour un graphe kitxmlcodeinlinelatexdvpGfinkitxmlcodeinlinelatexdvp, on aura donc la liste de nœuds kitxmlcodeinlinelatexdvpG.Vfinkitxmlcodeinlinelatexdvp (kitxmlcodeinlinelatexdvp|V|finkitxmlcodeinlinelatexdvp éléments) et un tableau kitxmlcodeinlinelatexdvpG.Adjfinkitxmlcodeinlinelatexdvp de listes d'adjacence, tel que chaque sommet est représenté par un élément de ce tableau.

On peut aussi utiliser une matrice d'adjacence, le graphe étant alors entièrement représenté par une matrice kitxmlcodeinlinelatexdvpG.Afinkitxmlcodeinlinelatexdvp de dimension kitxmlcodeinlinelatexdvp|V|\times|V|finkitxmlcodeinlinelatexdvp. Cette matrice est telle que

kitxmlcodelatexdvp a_{ij}=\begin{cases} 1 & \text{ si }(i,j)\in E\\ 0 & \text{ sinon} \end{cases}. finkitxmlcodelatexdvp

Si le graphe est non dirigé, elle sera symétrique. On peut également représenter des graphes pondérés en mettant le poids à la place du booléen.

  Complexité en espace Complexité en temps d'accès à un sommet Complexité en temps du parcours des sommets Complexité en temps du parcours des arêtes Complexité en temps de la vérification de l'existence d'une arête
Liste d'adjacence kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|V|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|V|)finkitxmlcodeinlinelatexdvp
Matrice d'adjacence kitxmlcodeinlinelatexdvpO(|V|^2)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|V|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|V|^2)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp
Optimal kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|V|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(|E|)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvpO(1)finkitxmlcodeinlinelatexdvp

On préférera les listes d'adjacence pour des graphes creux (kitxmlcodeinlinelatexdvp|E|\ll|V|^{2}finkitxmlcodeinlinelatexdvp) ou de degré faible, alors qu'on utilisera des matrices d'adjacence pour des graphes denses (kitxmlcodeinlinelatexdvp|E|\approx|V|^{2}finkitxmlcodeinlinelatexdvp) ou pour des algorithmes désirant accéder aléatoirement aux arêtes.

VII-C. Parcours de sommets

On cherche à parcourir tous les sommets accessibles à partir d'un sommet donné. Dans un graphe non dirigé, seule la composante connexe contenant kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp est visitée ; s'il est dirigé, seule une partie de cette composante sera visitée.

VII-C-1. En largeur

On parcourt les sommets par ordre croissant de distance par rapport au sommet argument kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp : on visite kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp, puis ses voisins, puis les voisins des voisins, etc., jusqu'à avoir parcouru tous les sommets accessibles.

On devra retenir les sommets déjà visités pour éviter de partir en boucle infinie. De même, on doit retenir les sommets visités dont on n'a pas encore visité les voisins. Aussi, on devra retenir la distance d'un sommet kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp : elle sera finie si le sommet kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp a été visité. La file (structure LIFO) contiendra les sommets qui ont été visités, mais pas leurs voisins.

Chaque sommet sera visité au plus une fois (sa distance à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp sera alors finie et il ne sera plus parcouru). La boucle principale s'exécutera kitxmlcodeinlinelatexdvp|V|finkitxmlcodeinlinelatexdvp fois, la boucle interne kitxmlcodeinlinelatexdvp|E|finkitxmlcodeinlinelatexdvp fois en tout. La complexité totale sera de kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp.

Parcours en largeur : GraphBreadthFirstSearch(G, s)
Sélectionnez
for each vertex u in G.V n fsg
	u.d = infinity
s.d = 0
Q = new create empty Queue
Enqueue(Q, s)
while not QueueEmpty(Q)
	u = Dequeue(Q)
	for each v in G.Adj[u]
		if v.d = 1
			v.d = u.d + 1
			Enqueue(Q, v)

VII-C-2. En profondeur

On part d'un sommet et on suit toutes les arêtes incidentes sans les mettre en attente ; on revient en arrière dès que le sommet visité n'a plus de sommet adjacent.

On retient les sommets visités ; chacun sera empilé au plus une fois.

La boucle principale s'exécutera kitxmlcodeinlinelatexdvp|V|finkitxmlcodeinlinelatexdvp fois, la boucle interne kitxmlcodeinlinelatexdvp|E|finkitxmlcodeinlinelatexdvp fois en tout. La complexité totale sera de kitxmlcodeinlinelatexdvpO(|V|+|E|)finkitxmlcodeinlinelatexdvp.

Parcours en profondeur : GraphDepthFirstSearch(G, s)
Sélectionnez
for each vertex u in G.V n fsg
	u.visited = False
S = new create empty stack
Push(S, s)
while not StackEmpty(Q)
	u = Pop(S)
	if u.visited == False
		u.visited = True
		for each v in G.Adj[u]
			if v.visited == False
				Push(S, v)
Initialisation du parcours en profondeur récursif : DFS(G, s)
Sélectionnez
for each vertex u in G.V
	u.visited = False
DFSRec(G, s)
Parcours en profondeur récursif : DFSRec(G, s)
Sélectionnez
s.visited = True
for each v in G.Adj[s]
	if v.visited == False
		DFSRec(G, v)

VII-D. Plus court chemin

Avec le graphe dirigé kitxmlcodeinlinelatexdvpG=\left(V,E\right)finkitxmlcodeinlinelatexdvp et la fonction de poids associée kitxmlcodeinlinelatexdvpw:E\to\mathbb{R}finkitxmlcodeinlinelatexdvp (le poids peut être négatif, sauf pour certains algorithmes), on définit un chemin du sommet kitxmlcodeinlinelatexdvpv_{1}finkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpv_{k}finkitxmlcodeinlinelatexdvp comme une séquence de nœuds kitxmlcodeinlinelatexdvpp=\left\{ v_{1},v_{2}\dots v_{k}\right\}finkitxmlcodeinlinelatexdvp telle que chaque paire consécutive de ces nœuds forme une arête du graphe. Le poids associé à un chemin kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp sera la somme des poids des arêtes qui le composent :

kitxmlcodelatexdvpw\left(p\right)=\sum\limits _{i=1}^{k-1}w\left(v_{i},v_{i+1}\right).finkitxmlcodelatexdvp

Ainsi, un plus court chemin entre deux sommets sera le chemin de poids le plus faible. On note kitxmlcodeinlinelatexdvp\delta\left(u,v\right)finkitxmlcodeinlinelatexdvp le poids associé au plus court chemin entre kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp ; s'il n'existe pas de tel chemin, ce poids sera infini ; on peut définir ce symbole comme

kitxmlcodelatexdvp\delta\left(u,v\right)=\min\left(\left\{ w\left(p\right)\,\Big|\, p\text{ chemin de }u\text{ à }v\right\} \cup\{\infty\}\right).finkitxmlcodelatexdvp

On recense divers variantes du problème de recherche de plus court chemin :

  • origine unique : trouver tous les chemins les plus courts d'un sommet à tous les autres (algorithmes de Dijkstra et de Bellman-Ford ; pour un graphe dirigé acyclique : relâchement selon un ordre topologique, kitxmlcodeinlinelatexdvp\Theta\left(\left|V\right|+\left|E\right|\right)finkitxmlcodeinlinelatexdvp ; graphe dirigé et poids positifs : Dijkstra et kitxmlcodeinlinelatexdvp\Theta\left(\left|E\right|\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp ; graphe dirigé et poids quelconques : Bellman-Ford et kitxmlcodeinlinelatexdvp\Theta\left(\left|V\right|\cdot\left|E\right|\right)finkitxmlcodeinlinelatexdvp) ;
  • destination unique : trouver tous les chemins les plus courts de tous les sommets vers un sommet donné ;
  • paire unique : trouver le plus court chemin entre deux sommets (tous les algorithmes connus ont la même complexité asymptotique dans le pire cas que le problème d'origine unique) ;
  • toutes les paires : trouver tous les chemins les plus courts entre toutes les paires de sommets du graphe (algorithme de Floyd-Warshall, kitxmlcodeinlinelatexdvp\Theta\left(\left|V\right|^{3}\right)finkitxmlcodeinlinelatexdvp).

VII-D-1. Propriétés

VII-D-1-a. Propriété de sous-structure optimale

Tout sous-chemin d'un chemin le plus court est un chemin le plus court entre ses extrémités.

On peut le prouver par l'absurde : on prend un plus court chemin kitxmlcodeinlinelatexdvpp_{uv}finkitxmlcodeinlinelatexdvp entre kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp et un sous-chemin kitxmlcodeinlinelatexdvpp_{xy}finkitxmlcodeinlinelatexdvp défini entre ses extrémités kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp. S'il existe un chemin plus court que kitxmlcodeinlinelatexdvpp_{xy}finkitxmlcodeinlinelatexdvp entre kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp, on pourrait remplacer la portion kitxmlcodeinlinelatexdvpp_{xy}finkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpp_{uv}finkitxmlcodeinlinelatexdvp par ce chemin plus court et ainsi obtenir un chemin plus court que kitxmlcodeinlinelatexdvpp_{uv}finkitxmlcodeinlinelatexdvp entre kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp.

VII-D-1-b. Cycles

En cas de cycle de poids négatif (on parle également de cycle absorbant), on peut réduire autant que l'on veut le poids d'un chemin en y passant aussi souvent que nécessaire. Ainsi, si un chemin de kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp passe par un cycle négatif, on posera

kitxmlcodelatexdvp\delta\left(u,v\right)=-\infty.finkitxmlcodelatexdvp

Un chemin le plus court ne peut pas contenir de cycle. S'il a un poids négatif, on ne définit pas de chemin le plus court. S'il a un poids nul, il n'y a pas de raison d'utiliser ces cycles (et on ne les utilisera pas). S'il a un poids positif, on peut obtenir un chemin plus court en les supprimant.

VII-D-1-c. Inégalité triangulaire

Pour tous kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp dans kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp, on a

kitxmlcodelatexdvp\delta\left(u,v\right)\leq\delta\left(u,w\right)+\delta\left(w,v\right),\forall w\in V.finkitxmlcodelatexdvp

En effet, si on a un plus court chemin entre kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp, passer par un nouveau nœud supplémentaire ne peut être qu'indifférent ou négatif.

On dispose aussi d'un corollaire : l'origine kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp étant fixée, pour tout kitxmlcodeinlinelatexdvpu\in Vfinkitxmlcodeinlinelatexdvp,

kitxmlcodelatexdvp\delta\left(s,v\right)\leq\delta\left(s,u\right)+w\left(u,v\right),\forall v\in V.finkitxmlcodelatexdvp

VII-D-2. Problème d'origine unique

D'un graphe dirigé kitxmlcodeinlinelatexdvpGfinkitxmlcodeinlinelatexdvp et pondéré par la fonction de poids kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp, d'un sommet kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp (l'origine), on veut imposer à chaque sommet deux attributs : la plus grande distance de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à ce nœud (kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp) et le prédécesseur dans un plus court chemin (kitxmlcodeinlinelatexdvpv.\pifinkitxmlcodeinlinelatexdvp), pour former l'arbre des plus courts chemins partant de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp et reconstruire la solution optimale (par la propriété de sous-structure optimale, cette information est suffisante : on connaît un nœud, on y ajoute le chemin le plus court pour le nœud précédent et on a le chemin total ; par application récursive, on trouve le chemin optimal).

Par force brute, la résolution n'est pas forcément aisée : si on essaie tous les chemins possibles dans un graphe, on risque de tomber sur un cycle ; or, dans ce cas, le nombre de chemins est infini ! De même, on peut avoir un nombre de chemins exponentiel par rapport au nombre de sommets et d'arêtes (si on a kitxmlcodeinlinelatexdvpO\left(n\right)finkitxmlcodeinlinelatexdvp nœuds et que presque tous ont un degré deux, on aura kitxmlcodeinlinelatexdvpO\left(2^{n}\right)finkitxmlcodeinlinelatexdvp chemins, d'où la complexité de l'algorithme dans ce cas précis ; dans le pire cas, on peut monter à une complexité de kitxmlcodeinlinelatexdvpO\left(n^{n}\right)finkitxmlcodeinlinelatexdvp, si chaque nœud a un degré kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp, soit pour un graphe hyperconnexe).

VII-D-2-a. Schéma général d'un algorithme

On cherche d'abord à calculer les distances par rapport à un nœud. On se basera sur l'inégalité triangulaire. Après initialisation de toutes les distances à kitxmlcodeinlinelatexdvp\inftyfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp contiendra à chaque fois une estimation d'un plus court chemin de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp ; on maintiendra l'invariant

kitxmlcodelatexdvpv.d\geq\delta\left(s,v\right).finkitxmlcodelatexdvp

Chaque itération tentera d'améliorer l'estimation kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp pour converger vers la longueur du chemin le plus court.

Pour améliorer une arête, on utilisera une routine de relâchement (terme hérité de la programmation linéaire), afin de mettre à jour l'approximation si on se rapproche de l'optimum. L'algorithme verra sa complexité varier fortement en fonction du choix de l'arête : notamment, à la première itération, tout choix de nœud qui n'est pas directement accessible depuis l'itération conduira à ne rien faire (la longueur depuis l'origine étant infinie par initialisation).

La fonction de poids kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp est intégrée dans la structure de graphe.

Algorithme général de recherche de plus court chemin depuis une origine unique : SingleSource(G, s)
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

while there is one edge (u, v) such that v.d > u.d + w(u; v)
	Pick one edge (u,v)
	// Relaxation
	if v.d > u.d + G.w(u; v)
		v.d = u.d + w(u; v)
		v.p = u

Grâce aux propriétés ci-après, pour montrer qu'un algorithme de plus court chemin basé sur ce squelette est correct, il suffira de montrer que le choix des arêtes mènera bien à

kitxmlcodelatexdvpv.d=\delta\left(s,v\right),\forall v\in V.finkitxmlcodelatexdvp

On note que, si le gardien de la boucle autorisait l'égalité, l'algorithme partirait en boucle infinie, vu qu'il est attendu que kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp atteigne kitxmlcodeinlinelatexdvp\delta\left(s,v\right)finkitxmlcodeinlinelatexdvp sans descendre plus bas.

L'algorithme général maintient toujours l'invariant.

On peut le prouver par induction sur le nombre d'itérations. Après l'initialisation, l'invariant est respecté ; ensuite, pour chaque itération, avant le relâchement, on considère l'invariant respecté. Par l'inégalité triangulaire, on a alors

kitxmlcodelatexdvp\delta\left(s,v\right)\leq\delta\left(s,u\right)+\delta\left(u,v\right)\leq u.d+w\left(u,v\right).finkitxmlcodelatexdvp

Après l'assignation, si elle a lieu,

kitxmlcodelatexdvpv.d=u.d+w\left(u,v\right),finkitxmlcodelatexdvp

l'invariant est toujours respecté, car

kitxmlcodelatexdvpv.d\geq\delta\left(s,v\right).finkitxmlcodelatexdvp

L'algorithme général ne modifie plus kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp une fois l'optimum atteint.

On a toujours

kitxmlcodelatexdvpv.d\geq\delta\left(s,v\right)finkitxmlcodelatexdvp

et la relaxation ne peut que diminuer la valeur de kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp.

L'algorithme général s'arrête à des chemins d'au plus kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp arêtes après la kitxmlcodeinlinelatexdvpi^{\text{e}}finkitxmlcodeinlinelatexdvp itération.

En d'autres termes,

kitxmlcodelatexdvpv.d\leq\min\left\{ w\left(p\right)\,\Big|\,\left|p\right|\leq i\right\}.finkitxmlcodelatexdvp

On doit imposer un graphe sans cycle de poids négatif.

Avant la première itération,

kitxmlcodelatexdvpv.d=\infty.finkitxmlcodelatexdvp

Ensuite, on suppose qu'on a, avant l'itération kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp,

kitxmlcodelatexdvpv.d\leq\min\left\{ w\left(p\right)\,\Big|\,\left|p\right|\leq i-1\right\}.finkitxmlcodelatexdvp

Cette propriété reste vraie pendant toute l'itération, puisque le relâchement ne peut que faire diminuer kitxmlcodeinlinelatexdvpv.dfinkitxmlcodeinlinelatexdvp ; cette itération considère tous les chemins avec kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp arêtes ou moins en relaxant les arêtes entrantes en kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp, les poids ayant été calculés pour kitxmlcodeinlinelatexdvpi-1finkitxmlcodeinlinelatexdvp arêtes.

VII-D-2-b. Algorithme de Bellman-Ford

L'algorithme de Bellman-Ford se base sur la relaxation pour effectuer son travail et est l'algorithme le plus général pour résoudre ce problème. On considère les arêtes kitxmlcodeinlinelatexdvpe_{1},e_{2}\dots\, e_{m}finkitxmlcodeinlinelatexdvp dans un ordre quelconque et on effectue kitxmlcodeinlinelatexdvp\left|V\right|-1finkitxmlcodeinlinelatexdvp relaxations dans cet ordre précis. On aura donc le pseudocode suivant.

Algorithme de Bellman-Ford
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for i=1 to |G:V| - 1
	for each edge (u, v) in G.E
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

En supposant qu'on puisse parcourir les arêtes en kitxmlcodeinlinelatexdvpO\left(\left|E\right|\right)finkitxmlcodeinlinelatexdvp, puisque la boucle interne est exécutée exactement kitxmlcodeinlinelatexdvp\left|V\right|-1finkitxmlcodeinlinelatexdvp fois, l'algorithme aura une complexité kitxmlcodeinlinelatexdvp\Theta\left(\left|V\right|\left|E\right|\right)finkitxmlcodeinlinelatexdvp.

Cet algorithme implémente une approche par programmation dynamique de manière itérative. Si on note kitxmlcodeinlinelatexdvpv.d\left[i\right]finkitxmlcodeinlinelatexdvp la longueur du plus court chemin de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp utilisant au plus kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp arêtes, on a la formule récursive

kitxmlcodelatexdvp v.d\left[i\right]=\begin{cases} 0 & \text{si }v=s\text{ et }i=0\\ \infty & \text{si }v\neq s\text{ et }i=0\\ \min_{\left(u,v\right)\in E}\left\{ u.d\left[i-1\right]+w\left(u,v\right)\right\} & \text{sinon} \end{cases} finkitxmlcodelatexdvp
VII-D-2-b-i. Correction

Si le graphe ne contient pas de cycle négatif, l'algorithme de Bellman-Ford est correct. En d'autres termes, on a à la fin

kitxmlcodelatexdvpv.d=\delta\left(s,v\right),\forall v\in V.finkitxmlcodelatexdvp

Le graphe n'ayant pas de cycle de poids négatif, tout plus court chemin doit être simple (acyclique). Un tel chemin a au plus kitxmlcodeinlinelatexdvp\left|V\right|finkitxmlcodeinlinelatexdvp sommets, donc kitxmlcodeinlinelatexdvp\left|V\right|-1finkitxmlcodeinlinelatexdvp arêtes. Après kitxmlcodeinlinelatexdvp\left|V\right|-1finkitxmlcodeinlinelatexdvp itérations, on a

kitxmlcodelatexdvpv.d\leq\delta\left(s,v\right).finkitxmlcodelatexdvp

Or, par l'invariant, on a

kitxmlcodelatexdvpv.d\geq\delta\left(s,v\right),finkitxmlcodelatexdvp

d'où

kitxmlcodelatexdvpv.d=\delta\left(s,v\right).finkitxmlcodelatexdvp
VII-D-2-b-ii. Détection des cycles négatifs

On peut implémenter une recherche de cycles de poids négatif à la fin de l'algorithme ; il renverra une valeur booléenne vraie en cas de cycle négatif accessible depuis kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp.

Algorithme de Bellman-Ford et détection des cycles négatifs
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for i=1 to |G:V| - 1
	for each edge (u, v) in G.E
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

for each edge (u, v) in G.E
	if v.d > u.d + w(u, v)
		return False
return true
VII-D-2-b-iii. Graphe dirigé acyclique

On peut rendre l'algorithme plus efficace dans le cas d'un graphe dirigé acyclique.

Algorithme de Bellman-Ford pour des graphes dirigés acycliques
Sélectionnez
// Initialisation
L = TopSort(G)
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for each vertex u, taken in their order in L
	for each vertex v in G.Adj[u]
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u
VII-D-2-c. Parcours en largeur

Si les poids sont tous égaux à l'unité, un parcours en largeur suffit pour déterminer le plus court chemin en kitxmlcodeinlinelatexdvpO\left(\left|V\right|+\left|E\right|\right)finkitxmlcodeinlinelatexdvp. Pour simuler des chemins plus longs, on peut ajouter des nœuds intermédiaires ; si les poids sont des entiers dans l'intervalle kitxmlcodeinlinelatexdvp\left[1;W\right]finkitxmlcodeinlinelatexdvp, la complexité sera alors de kitxmlcodeinlinelatexdvpO\left(\left|V\right|+W\,\left|E\right|\right)finkitxmlcodeinlinelatexdvp, soit déjà un grand gain par rapport à l'algorithme de Bellman-Ford. On ira ainsi des nœuds adjacents à l'origine aux nœuds les plus excentrés.

Parcours en largeur et chemins les plus courts
Sélectionnez
for each vertex u in G.V\{s}
	u.d = 1
s.d = 0
Q = new empty Queue

Enqueue(Q, s)
while not QueueEmpty(Q)
	u = Dequeue(Q)
	for each v in G:Adj[u]
		if v.d = 1
			v.d = u.d + 1
			Enqueue(Q, v)
VII-D-2-d. Algorithme de Dijkstra

Partant de la structure d'un parcours en largeur, on peut utiliser une approche gloutonne en généralisant au passage à des poids positifs non entiers. On maintient un ensemble kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp de sommets dont le poids d'un plus court chemin à partir de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp est connu (utilité surtout théorique) ; à chaque étape, on ajoute un sommet kitxmlcodeinlinelatexdvpv\in V\setminus Sfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp dont la distance à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp est minimale. On met alors à jour les distances estimées des sommets adjacents à kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp, en maintenant une file à priorité minimale kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp pour déterminer l'ordre des éléments à traiter.

Algorithme de Dijkstra
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0
S = empty set
Q = new empty min priority queue from G.V

while not QueueEmpty(Q)
	u = QueueExtractMin(Q)
	S = union of S and {u}
	for each v 2 G:Adj[u]
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u
			QueueSetPriority(v, v.d)

Si la file à priorité est implémentée par un tas, l'extraction et l'ajustement de la clé sont réalisés en kitxmlcodeinlinelatexdvpO\left(\log n\right)finkitxmlcodeinlinelatexdvp. Chaque sommet est extrait de la file à priorité une et une seule fois, d'où une boucle principale en kitxmlcodeinlinelatexdvpO\left(\left|V\right|\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp, sans compter le relâchement. Chaque arête est parcourue une et une seule fois, ce qui entraîne au plus un ajustement de clé, d'où une boucle interne en kitxmlcodeinlinelatexdvpO\left(\left|E\right|\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp. En tout, on aura un algorithme de complexité kitxmlcodeinlinelatexdvpO\left(\left(\left|V\right|+\left|E\right|\right)\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp ; si on considère le graphe connexe, on peut la simplifier en kitxmlcodeinlinelatexdvpO\left(\left|E\right|\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp.

VII-D-2-d-i. Correction

On cherche à prouver que l'algorithme de Dijkstra se termine avec

kitxmlcodelatexdvpv.d=\delta\left(s,v\right).finkitxmlcodelatexdvp

On remarque tout d'abord que, lorsqu'un nœud kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp est extrait de la file kitxmlcodeinlinelatexdvpQfinkitxmlcodeinlinelatexdvp, son champ kitxmlcodeinlinelatexdvpdfinkitxmlcodeinlinelatexdvp n'est plus modifié. On montre donc que la propriété ci-dessus est respectée quand on extrait un nœud de la file. L'invariant de l'algorithme général est toujours

kitxmlcodelatexdvpv.d\geq\delta\left(s,v\right).finkitxmlcodelatexdvp

On procède par l'absurde en supposant qu'il existe un nœud kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp tel que

kitxmlcodelatexdvpu.d>\delta\left(s,u\right)finkitxmlcodelatexdvp

lors de son extraction et qu'il s'agisse du premier nœud satisfaisant cette propriété. On considère alors kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp, le premier nœud d'un plus court chemin de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp se trouvant dans la file avant l'extraction de kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp. kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp en est le prédécesseur. kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp étant le premier nœud violant l'invariant, on doit avoir

kitxmlcodelatexdvpx.d=\delta\left(s,x\right).finkitxmlcodelatexdvp

Par la propriété de sous-structure optimale, le sous-chemin de kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp est un plus court chemin, kitxmlcodeinlinelatexdvpy.dfinkitxmlcodeinlinelatexdvp a été assigné, lors de l'extraction de kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp, à

kitxmlcodelatexdvp \begin{eqnarray} y.d & = & x.d+w\left(x,y\right)\\ & = & \delta\left(s,x\right)+w\left(x,y\right)\\ & = & \delta\left(s,y\right)\\ & \leq & \delta\left(s,u\right)\\ & \leq & u.d. \end{eqnarray} finkitxmlcodelatexdvp

Or, on doit avoir, puisqu'on s'apprête à extraire kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp de la file,

kitxmlcodelatexdvpy.d\geq u.d.finkitxmlcodelatexdvp

On doit donc avoir

kitxmlcodelatexdvpy.d=\mathbf{u.d}=\delta\left(s,y\right)=\boldsymbol{\delta\left(s,u\right)},finkitxmlcodelatexdvp

ce qui contredit l'hypothèse.

VII-D-3. Problème de recherche pour toutes les paires

D'un graphe dirigé kitxmlcodeinlinelatexdvpGfinkitxmlcodeinlinelatexdvp et de sa fonction de poids kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp, on cherche à produire une matrice kitxmlcodeinlinelatexdvpDfinkitxmlcodeinlinelatexdvp de taille kitxmlcodeinlinelatexdvpn\times nfinkitxmlcodeinlinelatexdvp, où

kitxmlcodelatexdvpd_{ij}=\delta\left(i,j\right).finkitxmlcodelatexdvp
VII-D-3-a. Réutilisation des algorithmes de Bellman-Ford ou Dijkstra

Dans le cas général, on peut appliquer l'algorithme de Bellman-Ford sur chaque sommet pour obtenir une complexité de kitxmlcodeinlinelatexdvpO\left(\text{\left|V\right|}^{2}\left|E\right|\right)finkitxmlcodeinlinelatexdvp (si le graphe est dense, kitxmlcodeinlinelatexdvp\left|E\right|=\Theta\left(\left|V\right|^{2}\right)finkitxmlcodeinlinelatexdvp et on a la complexité kitxmlcodeinlinelatexdvpO\left(\left|V\right|^{4}\right)finkitxmlcodeinlinelatexdvp.

Si on n'a pas de poids négatif, on peut utiliser l'algorithme de Dijkstra et améliorer la complexité en kitxmlcodeinlinelatexdvpO\left(\left|V\right|\left|E\right|\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp (ou, pour un graphe dense, kitxmlcodeinlinelatexdvpO\left(\left|V\right|^{3}\log\left|V\right|\right)finkitxmlcodeinlinelatexdvp).

VII-D-3-b. Algorithme de Floyd-Marshall

En appliquant les principes de la programmation dynamique, on peut réduire la complexité à kitxmlcodeinlinelatexdvpO\left(\left|V\right|^{3}\right)finkitxmlcodeinlinelatexdvp par l'algorithme de Floyd-Marshall.

Pour un chemin kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp, un sommet intermédiaire sera un sommet qui n'est ni origine ni extrémité de ce chemin. On notera kitxmlcodeinlinelatexdvpd_{ij}^{k}finkitxmlcodeinlinelatexdvp le poids d'un plus court chemin en kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpjfinkitxmlcodeinlinelatexdvp n'utilisant qu'un sous-ensemble des kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp premiers nœuds comme sommets intermédiaires.

L'algorithme reviendra à implémenter le fait que, si kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp n'est pas un sommet intermédiaire de kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp, alors tous les sommets intermédiaires de kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp sont dans kitxmlcodeinlinelatexdvp\left[1;k-1\right]finkitxmlcodeinlinelatexdvp, sinon, tous les sommets intermédiaires des sous-chemins entre kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp et entre kitxmlcodeinlinelatexdvpkfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpjfinkitxmlcodeinlinelatexdvp appartiennent à kitxmlcodeinlinelatexdvp\left[1;k-1\right]finkitxmlcodeinlinelatexdvp. De manière récursive,

kitxmlcodelatexdvp d_{ij}^{k}=\begin{cases} w\left(i,j\right) & \text{si }k=0\\ \min\left\{ d_{ij}^{k-1},d_{ik}^{k-1}+d_{kj}^{k-1}\right\} & \text{si }k>0 \end{cases}. finkitxmlcodelatexdvp

Ci-dessous, une implémentation ascendante basée sur la matrice d'adjacence pondérée (kitxmlcodeinlinelatexdvp0finkitxmlcodeinlinelatexdvp si l'arête n'est pas dans le graphe, son poids sinon).

Algorithme de Floyd-Warshall
Sélectionnez
D[0] = W
for k = 1 to n
	let D[k] = (d[k][i][j]) be a new n * n matrix
	for i = 1 to n
		for j = 1 to n
			d[k][i][j] = min{d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]}
return D[n]

VII-E. Arbre couvrant

Un arbre couvrant pour un graphe connexe non dirigé kitxmlcodeinlinelatexdvpG=\left(V,E\right)finkitxmlcodeinlinelatexdvp est un arbre (graphe acyclique) kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp tel que

  • l'ensemble des nœuds de kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp est kitxmlcodeinlinelatexdvpVfinkitxmlcodeinlinelatexdvp ;
  • l'ensemble des arcs de kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp est un sous-ensemble de kitxmlcodeinlinelatexdvpEfinkitxmlcodeinlinelatexdvp.

Il sera dit de poids minimal pour un graphe pondéré par la fonction kitxmlcodeinlinelatexdvpwfinkitxmlcodeinlinelatexdvp si, de plus, on a la valeur minimale de

kitxmlcodelatexdvp\sum\limits _{e\in E}w\left(e\right).finkitxmlcodelatexdvp

VII-E-2. Approche générique

Un arbre couvant minimal est un sous-ensemble d'arêtes du graphe initial ; ainsi, on part avec un ensemble kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp vide auquel on ajoute des arêtes en respectant l'invariant qu'il existe un arbre couvrant minimal qui contienne ces arêtes. À cette fin, on définit la notion d'arête sûre : une arête kitxmlcodeinlinelatexdvp\left(u,v\right)finkitxmlcodeinlinelatexdvp sera sûre pour kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp si et seulement s'il existe un arbre couvrant minimal qui contient les arêtes de kitxmlcodeinlinelatexdvpA\cup\left\{ \left(u,v\right)\right\}finkitxmlcodeinlinelatexdvp.

On se retrouve donc avec l'algorithme générique suivant, il faudra encore caractériser plus avant les arêtes sûres.

Arbre couvrant minimal et approche générique
Sélectionnez
A = empty set
while A is not a spanning tree
	find an edge (u, v) that is safe for A
	A = union of A and {(u, v)}
return A

VII-E-3. Caractérisation des arêtes sûres

Avec kitxmlcodeinlinelatexdvpS\subsetneq Afinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpA\subseteq Efinkitxmlcodeinlinelatexdvp, on définit la coupure kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp comme une partition des sommets en deux ensembles disjoints kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpV\setminus Sfinkitxmlcodeinlinelatexdvp, l'arête traverse d'une coupure kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp comme une arête dont une extrémité est dans kitxmlcodeinlinelatexdvpSfinkitxmlcodeinlinelatexdvp et l'autre dans kitxmlcodeinlinelatexdvpV\setminus Sfinkitxmlcodeinlinelatexdvp. Une coupure respecte kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp si et seulement s'il n'y a pas d'arête dans kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp qui traverse la coupure.

VII-E-3-a. Propriété des choix gloutons optimaux

Soit kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp, un sous-ensemble d'un arbre couvrant minimal ; kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp, une coupure qui respecte kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp ; kitxmlcodeinlinelatexdvp\left(u,v\right)finkitxmlcodeinlinelatexdvp, une arête de poids minimal qui traverse la coupure kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp ; ainsi, kitxmlcodeinlinelatexdvp\left(u,v\right)finkitxmlcodeinlinelatexdvp est une coupure sûre pour kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp.

On considère kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp, un arbre couvrant minimal qui inclut kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp. On suppose que kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp ne contient pas kitxmlcodeinlinelatexdvp\left\{ \left(u,v\right)\right\}finkitxmlcodeinlinelatexdvp et on montre qu'il est possible de construire un arbre kitxmlcodeinlinelatexdvpT'finkitxmlcodeinlinelatexdvp qui inclut kitxmlcodeinlinelatexdvpA\cup\left\{ \left(u,v\right)\right\}finkitxmlcodeinlinelatexdvp.

Puisque kitxmlcodeinlinelatexdvpTfinkitxmlcodeinlinelatexdvp est un arbre, le chemin kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp de kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpvfinkitxmlcodeinlinelatexdvp est unique, il traverse la coupure kitxmlcodeinlinelatexdvp\left(S,V\setminus S\right)finkitxmlcodeinlinelatexdvp. Soit kitxmlcodeinlinelatexdvp\left(x,y\right)finkitxmlcodeinlinelatexdvp, une arête de kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp qui traverse cette coupure. Puisque kitxmlcodeinlinelatexdvp\left(u,v\right)finkitxmlcodeinlinelatexdvp est une arête de poids minimum qui traverse la coupure,

kitxmlcodelatexdvpw\left(u,v\right)\leq w\left(x,y\right).finkitxmlcodelatexdvp

Puisque la coupure respecte kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp, l'arête kitxmlcodeinlinelatexdvp\left(x,y\right)finkitxmlcodeinlinelatexdvp ne fait pas partie de kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp.

On définit alors kitxmlcodeinlinelatexdvpT'finkitxmlcodeinlinelatexdvp comme

kitxmlcodelatexdvpT'=\left(T\setminus\left\{ \left(x,y\right)\right\} \right)\cup\left\{ \left(u,v\right)\right\} .finkitxmlcodelatexdvp

kitxmlcodeinlinelatexdvpT'finkitxmlcodeinlinelatexdvp est un arbre couvrant et

kitxmlcodelatexdvpw\left(T'\right)=w\left(T\right)-w\left(x,y\right)+w\left(u,v\right)\leq w\left(T\right)\text{, puisque }w\left(u,v\right)\leq w\left(x,y\right).finkitxmlcodelatexdvp

kitxmlcodeinlinelatexdvpT'finkitxmlcodeinlinelatexdvp est donc bien un arbre couvrant minimal tel que kitxmlcodeinlinelatexdvpA\cup\left\{ \left(u,v\right)\right\} \subseteq T'finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\left(u,v\right)finkitxmlcodeinlinelatexdvp est bien une arête sûre pour kitxmlcodeinlinelatexdvpAfinkitxmlcodeinlinelatexdvp.

VII-E-4. Algorithme de Kruskal

On construit une forêt, en ajoutant progressivement des arêtes à un graphe dépourvu d'arcs initialement. On maintient en permanence une partition du graphe en cours de construction en ses composantes connexes. Pour relier des composantes connexes, on choisit à chaque fois l'arête de poids minimal qui les connecte. On s'arrête dès qu'il ne reste plus qu'une composante connexe.

Cet algorithme est correct : puisqu'on connecte à chaque fois deux composantes connexes disjointes, on forme un arbre ; à la fin, on forme un arbre de recouvrement. Puisqu'on sélectionne une arête de poids minimal à chaque étape, la propriété des choix gloutons optimaux garantit que le résultat sera bien un arbre de recouvrement minimal.

On peut choisir les composantes connexes à fusionner de manière totalement arbitraire.

Algorithme de Kruskal
Sélectionnez
A = empty set
P = empty set
for each vertex v 2 G:V
	P = union of P and {{v}}
for each (u, v) in G.E taken into nondecreasing order of weight
	P1 = subset in P containing u
	P2 = subset in P containing v
	if P1 != P2
		A = union of A and {(u, v)}
		P = P1 merged with P2
return A

VIII. Conclusion

Au bout de ce cheminement relativement ardu, vous voilà armés pour partir dans vos développements en connaissance de cause : vous aurez le bagage théorique pour comprendre pourquoi votre algorithme est lent, pour prouver à quiconque que cette partie du programme ne peut être que fausse et que l'erreur doit venir des paramètres donnés. Ces algorithmes sont aussi utiles en eux-mêmes : qui n'a jamais rêvé de programmer son propre jeu ? Parmi les algorithmes que l'on rencontre le plus souvent, on retrouve bien évidemment le problème de plus court chemin à origine unique, sous un nom plus onirique : la recherche de chemin (ou path finding). On utilisera cependant plus généralement un algorithme plus rapide, mais qui ne donne pas toujours la solution optimale : A*, une extension de l'algorithme de Dijkstra.

IX. Références et remerciements

Ce cours se base essentiellement sur le cours oral de structures de données et algorithmes de Pierre Geurts (INFO0902), donné à l'ULg pendant l'année académique 2011-2012. Les livres Introduction to Algorithms (troisième édition) et Structures de données avancées avec la STL, première édition, de Philippe Gabrini ont été utilisés comme compléments occasionnels.

Merci à Kevin Vanaertenryck pour ses remarques sur le contenu et à Claude Leloup pour sa relecture orthographique !

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Copyright © 2012 Thibaut Cuvelier. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.