Algorithmes diviser pour régner

Un algorithme diviser pour régner (divide and conquer algorithm) est un paradigme algorithmique qui décompose un problème en sous-problèmes plus petits, résout récursivement chaque sous-problème (régner), puis combine le résultat de chaque sous-problème pour former la solution globale. L'idée algorithmique de récursivité est fondamentale pour les algorithmes diviser pour régner car elle résout des problèmes complexes en divisant les données d'entrée en des instances plus petites du même problème, appelées sous-problèmes. De tels appels récursifs se terminent lorsque les entrées deviennent si petites ou si simples que d'autres procédures non récursives peuvent fournir les réponses.

Un sous-problème (subproblem) est une instance plus petite d'un problème qui peut être résolue indépendamment, et chaque sous-problème peut être résolu indépendamment des autres sous-problèmes en réappliquant le même algorithme récursif. Pour concevoir des sous-problèmes récursifs, les concepteurs d'algorithmes se concentrent souvent sur l'identification d'une auto-similarité structurelle dans les données d'entrée. Ce processus se répète jusqu'à ce que les données d'entrée soient suffisamment petites pour être résolues directement. Une fois tous les sous-problèmes résolus, l'algorithme récursif réassemble chacune de ces solutions indépendantes pour calculer le résultat du problème original.

Précédemment, nous avons introduit la recherche binaire (binary search) pour trouver une cible dans une liste triée, par analogie avec la recherche d'un terme dans un dictionnaire trié alphabétiquement. Au lieu de commencer par le début du dictionnaire et de vérifier chaque terme, comme dans une recherche séquentielle (sequential search), nous pourrions plutôt commencer par le milieu et regarder à gauche ou à droite en fonction de l'endroit où nous nous attendrions à trouver le terme dans le dictionnaire. Mais la recherche binaire peut également être comprise comme un exemple d'algorithme diviser pour régner (Figure 3.16).

1. Le problème de trouver une cible dans la liste triée entière est décomposé (divisé) en le sous-problème de trouver une cible dans la moitié de la liste après avoir comparé l'élément (element) du milieu à la cible. La moitié de la liste peut être écartée sur la base de cette comparaison, laissant la recherche binaire trouver la cible dans la moitié restante.
2. La recherche binaire est répétée sur la moitié restante de la liste triée (régner). Ce processus se poursuit récursivement jusqu'à ce que la cible soit trouvée dans la liste triée (ou signalée comme n'étant pas du tout dans la liste).
3. Pour résoudre le problème original de trouver une cible dans la liste triée entière, le résultat du sous-problème doit éclairer la solution globale. L'appel original à la recherche binaire rapporte le même résultat que son sous-problème.

Figure 3.16 La recherche binaire est un algorithme diviser pour régner qui effectue de manière répétée un seul appel récursif sur la moitié des éléments restants. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

La recherche binaire effectue un seul appel récursif sur la moitié restante de la liste dans le cadre de l'étape de conquête, mais d'autres algorithmes diviser pour régner effectuent plusieurs appels récursifs pour résoudre leurs problèmes. Nous verrons également des algorithmes qui effectuent beaucoup de travail à l'étape finale de combinaison des résultats, au-delà du simple rapport du même résultat qu'un sous-problème.

Étant donné une liste d'éléments dans un ordre inconnu, un algorithme de tri doit renvoyer une nouvelle liste contenant les mêmes éléments réorganisés dans un ordre logique, tel que du plus petit au plus grand. Un algorithme diviser pour régner canonique pour le tri par comparaison est appelé tri fusion (merge sort). Le problème du tri par comparaison (comparison sorting) est basé sur l'opération de comparaison. L'opération de comparaison (comparison operation) est comme une balance traditionnelle qui indique si un élément est plus lourd, plus léger ou du même poids qu'un autre élément, mais ne fournit aucune information sur le poids ou la valeur exacte de l'élément. Bien que cela puisse sembler une restriction sérieuse, le tri par comparaison est en fait un problème très riche en informatique — c'est peut-être le problème le plus profondément étudié en informatique. Choisir la comparaison comme opération fondamentale est également pratique pour les données complexes (complex data), où il pourrait être difficile d'attribuer un classement numérique exact (Figure 3.17).

1. Le problème de trier la liste est décomposé (divisé) en deux sous-problèmes : le sous-problème de trier la moitié gauche et le sous-problème de trier la moitié droite.
2. Le tri fusion est répété pour trier chaque moitié (régner). Ce processus se poursuit récursivement jusqu'à ce que les sous-listes ne contiennent qu'un seul élément. Pour trier une liste d'un seul élément, l'algorithme n'a rien à faire, puisque les éléments de la liste sont déjà arrangés dans un ordre logique.
3. Pour résoudre le problème original de trier la liste entière, combinez les sous-listes triées adjacentes en les fusionnant tout en maintenant l'ordre trié. La fusion de chaque paire de sous-listes triées adjacentes se répète pour former des sous-listes triées de plus en plus grandes jusqu'à ce que la liste entière soit entièrement triée.

Figure 3.17 Le tri fusion est un algorithme diviser pour régner qui effectue de manière répétée deux appels récursifs sur les deux moitiés de la sous-liste. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Algorithmes par force brute

Résoudre un problème combinatoire (combinatorial problem) implique d'identifier la meilleure solution candidate parmi un espace de nombreuses solutions potentielles. Chaque solution à un problème combinatoire est représentée comme un type de données complexe. De nombreuses applications qui impliquent la simulation et la comparaison de différentes options peuvent être posées comme des problèmes combinatoires.

• La planification d'itinéraire dans la cartographie en ligne demande : « Parmi tous les itinéraires possibles du point A au point B, quel est l'itinéraire le plus court ? » (Problème des plus courts chemins)
• La planification du haut débit municipal demande : « Parmi toutes les manières possibles de connecter chaque adresse réelle à Internet, quel réseau de connexions est le moins cher à construire ? » (Problème des arbres couvrants minimaux)
• Le problème d'ordonnancement d'intervalles (interval scheduling problem) est un problème combinatoire impliquant une liste de tâches planifiées avec l'objectif de trouver le plus grand ensemble de tâches non chevauchantes qui peuvent être accomplies.

Plutôt que de rechercher un seul élément, les problèmes combinatoires se concentrent sur la recherche de solutions candidates qui pourraient être représentées comme une liste de directions de navigation, de connexions réseau ou de plannings de tâches. Et contrairement au tri, où la sortie devrait être une liste triée, les problèmes combinatoires tentent souvent de quantifier ou de comparer la qualité relative des solutions afin de déterminer la meilleure solution candidate parmi un espace de nombreuses solutions potentielles. Même si notre plan d'itinéraire n'est pas le « meilleur » ou le plus court, il peut toujours être une solution valide au problème.

Un algorithme par force brute (brute-force algorithm) résout les problèmes combinatoires en énumérant systématiquement toutes les solutions potentielles afin d'identifier la meilleure solution candidate. Par exemple, un algorithme par force brute pour générer des numéros de carte de crédit valides pourrait commencer par considérer un numéro de carte de crédit composé de tous les zéros, puis de tous les zéros sauf un un à la dernière position, et ainsi de suite, pour explorer progressivement toutes les valeurs possibles pour chaque position de chiffre.

Des algorithmes par force brute existent pour chaque problème combinatoire, mais ils ne sont généralement pas utilisés en raison de problèmes de temps d'exécution (runtime). Pour énumérer systématiquement toutes les solutions potentielles, un algorithme par force brute doit générer chaque combinaison possible des données d'entrée. Par exemple, si un numéro de carte de crédit a seize chiffres et que chaque chiffre peut avoir n'importe quelle valeur entre zéro et neuf, alors il y a 10¹⁶ numéros de carte de crédit potentiels à énumérer. L'explosion combinatoire (combinatorial explosion) est le nombre exponentiel de solutions à un problème combinatoire qui rend les algorithmes par force brute inutilisables en pratique. Malgré les améliorations continues de la vitesse d'exécution des programmes par les ordinateurs, les algorithmes par force brute à temps exponentiel sont impraticables, sauf pour des données d'entrée de problème très petites.

Algorithmes gloutons

Un algorithme glouton (greedy algorithm) résout les problèmes combinatoires en appliquant de manière répétée une règle simple pour sélectionner le prochain élément à inclure dans la solution. Contrairement aux algorithmes par force brute qui résolvent les problèmes combinatoires en générant toutes les solutions potentielles, les algorithmes gloutons se concentrent plutôt sur la génération d'une seule solution. Ces algorithmes sont gloutons parce qu'ils sélectionnent le prochain élément à inclure en fonction du bénéfice immédiat.

Par exemple, un algorithme glouton d'ordonnancement d'intervalles pourrait choisir de travailler sur la tâche qui prend le moins de temps à accomplir ; en d'autres termes, la manière la moins chère de marquer une tâche comme terminée (Figure 3.18). Si les tâches sont planifiées à l'avance et que nous ne pouvons travailler que sur une seule tâche à la fois, choisir la tâche qui prend le moins de temps à accomplir pourrait nous empêcher de terminer plusieurs autres tâches qui se chevauchent dans le temps. Cet algorithme glouton ne calcule pas la bonne sortie — il trouve une solution mais pas la solution optimale.

Figure 3.18 L'ordonnancement glouton d'intervalles ne fonctionnera pas si la règle simple sélectionne de manière répétée l'intervalle le plus court. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

La majorité des algorithmes gloutons ne calculent pas toujours la meilleure solution. Mais il existe aussi certains scénarios dans lesquels des algorithmes gloutons astucieusement conçus garantissent la découverte de solutions optimales. Les problèmes qu'ils résolvent sont formulés de manière à garantir que l'algorithme glouton ne commet jamais d'erreur lorsqu'il applique de manière répétée la règle simple pour sélectionner l'élément suivant.

Considérons le problème de planification du haut débit municipal ou, plus formellement, le problème de l'arbre couvrant minimal, qui consiste à trouver le moyen le moins coûteux de connecter tous les sommets d'un graphe connexe les uns aux autres. Si nous voulons minimiser la somme des poids des arêtes sélectionnées, une idée est de sélectionner de manière répétée l'arête suivante avec le poids le plus faible tant qu'elle étend la portée du réseau. Ou, dans le contexte du problème de planification du haut débit municipal, nous voulons nous assurer que la prochaine connexion la moins chère que nous choisissons de construire atteigne quelqu'un qui a besoin d'accéder à Internet (Figure 3.19).

Figure 3.19 La planification du haut débit municipal peut être représentée comme un problème de graphe d'arbres couvrants minimaux où le poids de chaque arête représente le coût de construction d'une connexion entre deux sommets ou lieux. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Les informaticiens ont conçu des algorithmes qui appliquent de manière répétée cette règle simple pour trouver un arbre couvrant minimal optimal :

• algorithme de Kruskal (Kruskal’s algorithm), un algorithme glouton qui trie la liste des arêtes du graphe par poids.
• algorithme de Prim (Prim’s algorithm), un algorithme glouton qui maintient une file de priorité de sommets dans le graphe ordonnée par le poids des arêtes de connexion.

Pour la plupart des problèmes, les algorithmes gloutons ne produiront pas la meilleure solution. Au lieu de cela, les concepteurs d'algorithmes se tournent généralement vers un autre paradigme algorithmique appelé programmation dynamique (dynamic programming). Néanmoins, les algorithmes gloutons constituent un point de départ utile pour comprendre les problèmes et concevoir des algorithmes de base pour générer des solutions potentielles.

Algorithmes de réduction

Les concepteurs d'algorithmes passent une grande partie de leur temps à modéliser des problèmes en sélectionnant et en adaptant des structures de données et des algorithmes pertinents pour représenter le problème et une solution dans un programme informatique. Ce processus de modélisation (modeling) implique souvent de modifier un patron de conception d'algorithme afin qu'il puisse être appliqué au problème. Mais il existe également une approche différente de la conception d'algorithmes qui résout les problèmes en modifiant les données d'entrée et les données de sortie pour les adapter à un problème préexistant. Plutôt que de résoudre le problème directement, un algorithme de réduction (reduction algorithm) résout les problèmes en les transformant en d'autres problèmes (Figure 3.20).

1. Prétraitement : Transformer les données d'entrée de manière à ce qu'elles soient acceptables pour un algorithme destiné à l'autre problème.
2. Appliquer l'algorithme destiné à l'autre problème sur les données prétraitées.
3. Post-traitement : Transformer la sortie de l'algorithme destiné à l'autre problème de manière à ce qu'elle corresponde à la sortie attendue pour le problème original.

Figure 3.20 Un algorithme de réduction prétraite les données d'entrée, les transmet à un autre algorithme, puis post-traite la sortie de l'algorithme pour résoudre le problème original. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Considérons une version légèrement différente du problème de planification du haut débit municipal, où au lieu de ne considérer que les connexions (arêtes), nous étendons le problème pour envisager la possibilité d'installer des nœuds de haut débit directement à chaque adresse sans dépendre de connexions voisines potentiellement coûteuses. C'est-à-dire que tous les sommets équipés de nœuds de haut débit sont interconnectés les uns aux autres via un autre réseau haut débit. Si nous devions exécuter directement un algorithme de résolution du problème de l'arbre couvrant minimal sur ce graphe, notre résultat ne considérerait jamais l'installation directe de nœuds de haut débit, car les algorithmes de l'arbre couvrant minimal ne prennent pas en compte les poids des sommets (Figure 3.21).

Figure 3.21 Le problème de trouver un arbre couvrant minimal dans un graphe avec des poids de sommets peut être réduit au problème de trouver un arbre couvrant minimal dans un graphe sans poids de sommets. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Nous disons que ce problème plus complexe de planification du haut débit municipal se réduit au problème de l'arbre couvrant minimal car nous pouvons concevoir un algorithme de réduction composé de procédures de prétraitement et de post-traitement.

• Prétraitement : Introduire un sommet supplémentaire qui ne représente pas un emplacement réel mais se connecte à chaque adresse de la ville. Le poids de l'arête de chaque connexion est le coût d'installation du nœud de haut débit directement à cet emplacement.
• Post-traitement : Après avoir calculé un arbre couvrant minimal pour le graphe prétraité, supprimer le sommet supplémentaire que nous avons ajouté pendant l'étape de traitement. Toutes les arêtes connectées au sommet supplémentaire représentent une installation directe de nœud de haut débit, tandis que les autres arêtes entre les emplacements réels sont simplement les mêmes connexions réseau que nous avons vues précédemment.

Les algorithmes de réduction permettent aux concepteurs d'algorithmes de résoudre des problèmes sans avoir à modifier les algorithmes existants ou les patrons de conception d'algorithmes. Les algorithmes de réduction permettent aux concepteurs d'algorithmes de s'appuyer sur des algorithmes canoniques optimisés plutôt que de concevoir une solution en composant des patrons de conception d'algorithmes, ce qui peut entraîner des bogues de performance ou d'exactitude. Les algorithmes de réduction permettent également aux informaticiens de faire des affirmations sur la difficulté relative d'un problème. Si nous savons qu'un problème A se réduit à un autre problème B, B est aussi difficile à résoudre que A.