3.5 Exemples d'algorithmes par problème
Objectifs d'apprentissage
À la fin de cette section, vous serez capable de :
- Découvrir des algorithmes qui résolvent des problèmes de structure de données
- Comprendre les problèmes de graphes et les algorithmes associés
Auparavant, nous avons introduit plusieurs problèmes informatiques, comme la recherche d'une valeur cible dans une liste ou l'implémentation d'un type de données abstrait (listes, ensembles, cartes, files de priorité, graphes). Bien que chaque problème computationnel soit unique, ces types de problèmes partagent souvent des similarités significatives avec d'autres problèmes. Les informaticiens ont identifié de nombreux problèmes canoniques qui représentent ces modèles de problèmes courants. Bien que chacun de ces problèmes canoniques puisse avoir de nombreuses solutions algorithmiques, les informaticiens ont également identifié des algorithmes canoniques pour résoudre ces problèmes. Dans cette section, nous présenterons les problèmes canoniques et passerons en revue les algorithmes canoniques pour chaque problème.
Problèmes de structure de données
Les problèmes de structure de données sont utiles non seulement pour implémenter des structures de données, mais aussi comme patrons de conception d'algorithmes fondamentaux pour organiser les données afin de permettre des solutions efficaces à presque tous les autres problèmes informatiques.
Recherche
La recherche est le problème de la récupération d'un élément cible (target) à partir d'une collection d'éléments. La recherche dans une structure de données linéaire, telle qu'une liste de tableau (array list), peut être effectuée en utilisant soit la recherche séquentielle (sequential search), soit la recherche binaire (binary search).
Algorithme de recherche séquentielle
Un algorithme de recherche séquentielle (sequential search algorithm) est un algorithme de recherche (searching) qui vérifie séquentiellement la collection élément par élément pour trouver la cible. L'exécution de la recherche séquentielle est en O(N) par rapport à N, le nombre d'éléments dans la liste (Figure 3.22).
Algorithme de recherche binaire
Un algorithme de recherche binaire (binary search algorithm) réduit récursivement les emplacements possibles de la cible dans la liste triée. Initialement, l'algorithme n'a aucune information — la cible peut se trouver n'importe où dans toute la plage de la liste triée. En comparant la cible à l'élément du milieu de la plage, nous pouvons exclure la moitié des éléments de la plage. Ce processus peut être répété jusqu'à ce que nous ayons trouvé l'emplacement attendu de la cible dans la liste triée. L'exécution (runtime) de la recherche binaire est en O(log N) par rapport à N, le nombre d'éléments dans la liste triée, tant que l'indexation est une opération à temps constant (constant-time operation) (voir Figure 3.11).
Bien que l'algorithme de recherche séquentielle fonctionne avec n'importe quel type de collection comme les listes, les ensembles, les dictionnaires et les files de priorité, l'algorithme de recherche binaire repose sur une liste triée avec accès aux éléments par index (index). Par conséquent, la recherche binaire est efficace sur les listes de tableau qui offrent un accès à temps constant à l'élément à n'importe quel index et inefficace sur les listes chaînées, qui ne permettent pas un accès à temps constant aux éléments par index. La recherche binaire s'appuie sur la structure de la liste triée pour exclure à plusieurs reprises la moitié des éléments restants.
Les arbres binaires de recherche représentent le concept de recherche binaire dans une structure de données arborescente en organisant les éléments de l'arbre dans un ordre trié de gauche à droite. Idéalement, le nœud racine représente l'élément du milieu dans l'arbre trié et chaque enfant divise approximativement chaque sous-arbre en deux. Mais, dans le pire des cas, un arbre binaire de recherche peut ressembler exactement à une liste chaînée où chaque nœud contient soit zéro enfant, soit un enfant. Bien qu'un tel arbre organise toujours ses éléments dans un ordre trié de gauche à droite, la comparaison de la cible à chaque nœud ne réduit la taille du problème que d'un seul élément plutôt que d'exclure la moitié des éléments restants — l'arbre binaire de recherche dans le pire des cas se dégrade en recherche séquentielle. Les arbres binaires de recherche équilibrés, tels que les arbres AVL (AVL tree), ont abordé ce scénario du pire des cas en maintenant la propriété d'équilibre AVL entre les sous-arbres gauche et droit.
Tri
Le tri est le problème de la réorganisation des éléments dans un ordre logique, généralement du moins valorisé au plus valorisé. Le tri est un problème fondamental non seulement en raison des tâches qu'il résout directement, mais aussi parce qu'il est une base pour de nombreux autres algorithmes tels que l'algorithme de recherche binaire ou l'algorithme de Kruskal (Kruskal’s algorithm) pour le problème de l'arbre couvrant minimal (minimum spanning tree problem).
Le type le plus courant d'algorithme de tri (sorting) résout le problème du tri par comparaison (comparison sorting), ou le tri d'une liste d'éléments où les éléments ne sont pas assignés de valeurs numériques mais plutôt définis en relation avec d'autres éléments. Pour simplifier, les données sont généralement supposées être stockées dans une liste de tableau pour un accès indexé, et l'algorithme de tri peut soit renvoyer une nouvelle liste triée, soit réorganiser les éléments dans la liste de tableau afin qu'ils apparaissent dans l'ordre trié.
Algorithme de tri fusion
Un algorithme de tri fusion (merge sort algorithm) divise récursivement les données en sous-listes jusqu'à ce que les sous-listes ne contiennent qu'un seul élément — que nous savons être triées — puis fusionne les sous-listes triées adjacentes pour finalement renvoyer la liste triée. L'opération de fusion combine deux sous-listes triées pour produire une nouvelle sous-liste triée plus grande contenant tous les éléments dans l'ordre trié. La réorganisation réelle des éléments se produit en appliquant à plusieurs reprises l'opération de fusion sur des paires de sous-listes triées adjacentes, en commençant par les plus petites sous-listes à un seul élément, puis les sous-listes à deux éléments plus grandes, et en atteignant finalement les deux moitiés de la liste entière d'éléments. L'exécution du tri fusion est en O(N log N) par rapport à N, le nombre d'éléments (voir Figure 3.17).
Algorithme de tri rapide
Un algorithme de tri rapide (quicksort algorithm) trie récursivement les données en appliquant le patron de conception d'algorithme d'arbre binaire de recherche pour partitionner les données autour d'éléments pivots. Alors que l'algorithme de tri fusion réorganise les éléments en fusionnant à plusieurs reprises des sous-listes triées après chaque sous-problème récursif, l'algorithme de tri rapide réorganise les éléments en partitionnant les données avant chaque sous-problème récursif. L'opération de partition prend un pivot et réorganise les éléments en trois sections, de gauche à droite : la sous-liste de tous les éléments inférieurs au pivot, l'élément pivot, et la sous-liste de tous les éléments supérieurs (ou égaux) au pivot. Chacune des deux sous-listes résultant de l'opération de partition est un sous-problème récursif de tri rapide ; lorsque les deux sous-listes sont triées, la liste entière sera triée. L'exécution du tri rapide dépend du choix de chaque élément pivot pendant l'exécution de l'algorithme récursif, mais en pratique, pour la plupart des entrées, l'exécution est en O(N log N) par rapport à N, le nombre d'éléments (Figure 3.23).
Algorithme de tri par tas
Un algorithme de tri par tas (heapsort algorithm) ajoute tous les éléments à une structure de données de file de priorité (priority queue) de tas binaire en utilisant l'opération de comparaison (comparison operation) pour déterminer la valeur de priorité, et renvoie la liste triée en retirant à plusieurs reprises les éléments de la file de priorité un par un. L'exécution (runtime) du tri par tas est en O(N log N) par rapport à N, le nombre d'éléments. Le facteur de temps logarithmique est dû au temps nécessaire pour ajouter ou retirer chaque élément du tas binaire (Figure 3.24).
De nombreux algorithmes de tri par comparaison partagent la même borne d'exécution O(N log N) par rapport à N, le nombre d'éléments. Les informaticiens ont montré par une preuve combinatoire que, dans le pire des cas, un algorithme de tri par comparaison ne peut pas faire mieux que O(N log N) comparaisons. Il est impossible de concevoir un algorithme de tri par comparaison avec une exécution en O(N) dans le pire des cas. En fait, une version couramment utilisée du tri par tas (qui est également asymptotiquement plus rapide) consiste à construire d'abord un tas binaire (c'est-à-dire, d'abord organiser les nombres d'entrée dans un tableau, puis appeler à plusieurs reprises une fonction pour transformer le tableau original en un tas binaire ; on peut montrer que le temps d'exécution de cette partie est linéaire en N, ce qui explique pourquoi c'est plus rapide que de construire le tas en ajoutant les nombres un par un), puis à retirer les éléments un par un de la fin du tas.
Mais tous les problèmes de tri ne sont pas des problèmes de tri par comparaison. En fait, une version couramment utilisée du tri par tas (qui est également asymptotiquement plus rapide) consiste à construire d'abord un tas binaire (c'est-à-dire, d'abord organiser les nombres d'entrée dans un tableau, puis appeler à plusieurs reprises une fonction pour transformer le tableau original en un tas binaire. On peut montrer que le temps d'exécution de cette partie est linéaire en N, ce qui explique pourquoi c'est plus rapide que de construire le tas en ajoutant les nombres un par un), puis à retirer les éléments un par un de la fin du tas comme expliqué précédemment.
Un autre type de problème de tri qui n'est pas limité aux comparaisons par paires est connu sous le nom de tri par dénombrement (count sorting), ou le tri d'une liste d'éléments en organisant les éléments en catégories et en réorganisant les catégories dans un ordre logique. Par exemple, le problème du tri d'un jeu de cartes peut être considéré comme un problème de tri par dénombrement si nous mettons les cartes dans des piles numériques, puis réorganisons les piles dans un ordre logique. En modifiant les hypothèses du problème, les algorithmes de tri par dénombrement peuvent s'exécuter en temps O(N) en attribuant d'abord chaque élément à sa catégorie respective, puis en déballant chaque catégorie afin que les éléments apparaissent dans l'ordre trié.
Hachage
Le hachage est le problème de la conception d'algorithmes efficaces qui mappent chaque objet à un entier de sorte que la plupart les objets se voient attribuer des entiers distincts. Bien que les algorithmes de hachage (hashing) soient souvent spécifiques à chaque type de données, il existe des approches générales pour concevoir des algorithmes de hachage. La valeur de hachage d'un type de données simple tel qu'un entier peut simplement être la valeur de l'entier lui-même. La valeur de hachage d'une chaîne de caractères peut être une combinaison mathématique de la valeur numérique de chaque caractère de la chaîne. De même, la valeur de hachage d'une collection telle qu'une liste peut être une combinaison des données numériques sous-jacentes de chaque élément de la collection.
Le hachage a une variété d'applications couvrant les systèmes informatiques, les systèmes de bases de données, la sécurité informatique et les algorithmes de recherche. Par exemple, les algorithmes de hachage sont souvent utilisés pour concevoir des systèmes sécurisés pour protéger les mots de passe stockés même après une violation de sécurité. Dans le contexte des problèmes de structure de données, le hachage offre une approche différente de la recherche binaire. Au lieu de s'appuyer sur des comparaisons par paires pour réduire l'emplacement attendu d'un élément dans une liste triée en temps logarithmique, les algorithmes de recherche par hachage peuvent directement indexer un élément par valeur de hachage en temps constant. Si les arbres binaires de recherche implémentent des ensembles et des cartes en appliquant le concept de recherche binaire, une table de hachage (hash table) implémente des ensembles et des cartes en appliquant le concept de hachage (Figure 3.25). Plutôt que d'organiser les éléments dans l'ordre trié de gauche à droite comme dans un arbre binaire de recherche, les tables de hachage stockent et récupèrent les éléments dans un tableau indexé par la valeur de hachage.
Les algorithmes de recherche par hachage sont souvent préférés aux algorithmes de recherche binaire pour leurs avantages en termes d'exécution, mais ils présentent des inconvénients uniques. Idéalement, différents objets devraient hacher à des valeurs de hachage différentes. Mais l'explosion combinatoire des possibilités pour des chaînes de caractères uniques ou des collections de données complexes signifie qu'une collision (collision), ou une situation dans laquelle plusieurs objets hachent à la même valeur d'index entier, est inévitable puisque les entiers dans un ordinateur ne peuvent généralement représenter qu'une certaine plage fixe de nombres entiers. L'explosion combinatoire n'est pas seulement un problème pour la conception d'algorithmes efficaces, mais aussi pour la conception de structures de données efficaces.
Problèmes de graphes
Alors que les problèmes de structure de données se concentrent principalement sur le stockage et la récupération d'éléments dans une collection, les problèmes de graphes (graph problem) incluent une grande variété de problèmes informatiques impliquant la structure de données de graphe. Contrairement à d'autres structures de données, les graphes incluent non seulement des éléments mais aussi des relations entre les éléments (arêtes). Les problèmes de graphes demandent souvent aux concepteurs d'algorithmes d'explorer le graphe afin de répondre à des questions sur les éléments et les relations entre les éléments.
Parcours
Le parcours est le problème de l'exploration de tous les sommets d'un graphe. Les structures de données de graphes diffèrent des structures de données d'arbres en ce qu'il n'y a pas de nœud racine explicite pour commencer le parcours (traversal) et les arêtes peuvent se reconnecter à d'autres parties du graphe. En général, il n'y a pas de garantie de hiérarchie dans un graphe. Les algorithmes de parcours de graphes tels que la recherche en profondeur et le parcours en largeur commencent à un sommet de départ arbitraire et explorent vers l'extérieur à partir du sommet de départ tout en gardant une trace d'un ensemble de sommets explorés.
Recherche en profondeur
Une recherche en profondeur (depth-first search) est un algorithme de parcours de graphe qui explore récursivement chaque voisin, en continuant aussi loin que possible le long de chaque sous-problème en profondeur (Figure 3.26). Les sommets explorés sont ajoutés à un ensemble global pour garantir que l'algorithme n'explore chaque sommet qu'une seule fois. L'exécution de la recherche en profondeur est en O(|V| + |E|) par rapport à |V|, le nombre de sommets, et |E|, le nombre d'arêtes.
Parcours en largeur
Un parcours en largeur (breadth-first search) explore itérativement chaque voisin, en étendant la recherche niveau par niveau en largeur (Figure 3.27). Les sommets explorés sont également ajoutés à un ensemble global pour garantir que l'algorithme explore chaque sommet une seule fois et dans le bon ordre de niveau. L'exécution (runtime) du parcours en largeur est également en O(|V| + |E|) par rapport à |V|, le nombre de sommets, et |E|, le nombre d'arêtes.
Les algorithmes de parcours de graphes sont les patrons de conception d'algorithmes fondamentaux pour la plupart des algorithmes de traitement de graphes. De nombreux algorithmes nécessitent une certaine exploration, et cette exploration commence généralement à un certain sommet et continue à traiter chaque sommet atteignable au plus une fois. Un sommet atteignable (reachable vertex) peut être atteint si un chemin ou une séquence d'arêtes depuis le sommet de départ existe. Contrairement à la recherche en profondeur, le parcours en largeur a l'avantage d'explorer les sommets plus proches du départ avant d'explorer les sommets plus éloignés du départ, ce qui peut être utile pour résoudre des problèmes tels que les plus courts chemins non pondérés (unweighted shortest path).
Arbres couvrants minimaux
Le problème de l'arbre couvrant minimal consiste à trouver le sous-ensemble de trouver le moyen le moins coûteux de connecter tous les sommets les uns aux autres, où le coût est la somme des poids des arêtes sélectionnées. Les deux algorithmes gloutons (greedy algorithm) canoniques pour trouver un arbre couvrant minimal (minimum spanning tree) dans un graphe sont l'algorithme de Kruskal (Kruskal’s algorithm) et l'algorithme de Prim (Prim’s algorithm). Les deux algorithmes appliquent à plusieurs reprises la règle de sélection de l'arête de poids le plus faible suivante vers une partie non connectée du graphe. La sortie d'un algorithme d'arbre couvrant minimal est un ensemble de |V| - 1 arêtes connectant tous les sommets du graphe avec la somme totale la plus faible des poids des arêtes, où |V| est le nombre de sommets.
Algorithme de Kruskal
L'algorithme de Kruskal commence par considérer chaque sommet comme une "île" indépendante, et le but de l'algorithme est de connecter à plusieurs reprises les îles en sélectionnant les arêtes de coût le plus faible. Une structure de données spécialisée (appelée ensembles disjoints) est généralement utilisée pour suivre les îles indépendantes. L'exécution de l'algorithme de Kruskal est en O(|E| log |E|) par rapport à |E|, le nombre d'arêtes (Figure 3.28).
Algorithme de Prim
L'algorithme de Prim construit un arbre couvrant minimal arête par arête en sélectionnant l'arête de poids le plus faible vers un sommet inexploré. L'exécution de l'algorithme de Prim est en O(|E| log |V| + |V| log |V|) par rapport à |V|, le nombre de sommets, et |E|, le nombre d'arêtes (Figure 3.29).
Plus courts chemins
La sortie d'un algorithme de plus courts chemins est un arbre des plus courts chemins (shortest paths tree), le moyen le moins coûteux de se rendre d'un sommet à tous les autres sommets d'un graphe (Figure 3.30). Le plus court chemin non pondéré (unweighted shortest path) est le problème de trouver les plus courts chemins en termes de nombre d'arêtes. Étant donné un sommet de départ, le parcours en largeur peut calculer l'arbre des plus courts chemins non pondérés du sommet de départ à tous les autres sommets atteignables du graphe en maintenant une structure de données de carte du chemin utilisé pour atteindre chaque sommet.
Plus court chemin pondéré
Un plus court chemin pondéré (weighted shortest path) est le problème de trouver les plus courts chemins en termes de somme des poids des arêtes. Auparavant, nous avons introduit l'algorithme de Prim, un algorithme d'arbre couvrant minimal qui maintient une file de priorité d'arêtes dans le graphe ordonnées par poids et sélectionne à plusieurs reprises l'arête de coût le plus faible suivante vers une partie non connectée du graphe.
Questions de réflexion
Plus courts chemins pondérés pour les directions de navigation
L'une des applications les plus directes du problème des plus courts chemins est de fournir des itinéraires recommandés pour les directions de navigation dans la cartographie du monde réel. De nombreuses applications utilisent la distance comme métrique pour le poids des arêtes, de sorte que le plus court chemin entre deux points représente l'itinéraire réel avec la plus petite distance entre les deux lieux.
Qu'est-ce qu'une métrique de distance ne prend pas en compte lors de la proposition d'un itinéraire recommandé ? Quelles valeurs sont centrées et mises en évidence même en utilisant un algorithme de plus courts chemins pour recommander des itinéraires ?
Algorithme de Dijkstra
L'algorithme de Dijkstra (Dijkstra’s algorithm) maintient une file de priorité de sommets dans le graphe ordonnée par distance depuis le départ et sélectionne à plusieurs reprises le plus court chemin suivant vers une partie non connectée du graphe. L'algorithme de Dijkstra est presque identique à l'algorithme de Prim, sauf qu'il traite les plus courts chemins (séquences d'arêtes) plutôt que des arêtes individuelles. L'algorithme de Dijkstra construit un arbre des plus courts chemins (shortest paths tree) un plus court chemin à la fois en sélectionnant le plus court chemin suivant vers un sommet inexploré. L'exécution de l'algorithme de Dijkstra est en O(|E| log |V| + |V| log |V|) par rapport à |V|, le nombre de sommets, et |E|, le nombre d'arêtes (Figure 3.31).