Algorithme diviser pour régner

Diviser pour régner est un outil puissant pour résoudre des problèmes conceptuellement difficiles : il suffit de décomposer le problème en sous-problèmes, de résoudre les cas triviaux et de combiner ces sous-problèmes au problème initial. De même, réduire pour régner consiste simplement à ramener le problème à un seul sous-problème plus simple, comme le casse-tête classique des tours de Hanoï , où déplacer une tour de hauteur h se réduit à déplacer une tour de hauteur h .

Le paradigme « diviser pour régner » facilite souvent la découverte d'algorithmes efficaces. Il a été la clé, par exemple, de la méthode de multiplication rapide de Karatsuba , des algorithmes de tri rapide et de tri fusion, de l' algorithme de Strassen pour la multiplication matricielle et des transformées de Fourier rapides.

Dans tous ces exemples, l'approche D&C a permis d'améliorer le coût asymptotique de la solution. Par exemple, si (a) les cas de base ont une taille constante et bornée, le travail de division du problème et de combinaison des solutions partielles est proportionnel à la taille du problème , et (b) il existe un nombre borné de sous-problèmes de taille ~ à chaque étape, alors le coût de l'algorithme diviser pour régner sera de .

Pour d'autres types d'approches de type « diviser pour régner », les temps d'exécution peuvent également être généralisés. Par exemple, lorsque : a) le travail de division du problème et de combinaison des solutions partielles prend un temps O(n), où n est la taille de l'entrée et c une constante ; b) lorsque n ≥ 0 , l'algorithme prend un temps majoré par n ; et c) il existe n sous-problèmes, chacun de taille n ≈ 0. Alors, les temps d'exécution sont les suivants :

• si le nombre de sous-problèmes , alors le temps d'exécution de l'algorithme diviser pour régner est borné par . 2" $2q>2$2
• si le nombre de sous-problèmes est exactement un, alors le temps d'exécution de l'algorithme diviser pour régner est borné par .

Si, en revanche, le travail de division du problème et de combinaison des solutions partielles prend du temps, et qu'il existe 2 sous-problèmes où chacun a une taille , alors le temps d'exécution de l'algorithme diviser pour régner est borné par .

Les algorithmes de type diviser pour régner sont naturellement adaptés à l'exécution sur des machines multiprocesseurs , en particulier les systèmes à mémoire partagée où la communication des données entre les processeurs n'a pas besoin d'être planifiée à l'avance car des sous-problèmes distincts peuvent être exécutés sur différents processeurs.

Les algorithmes de type « diviser pour régner » exploitent naturellement et efficacement les caches mémoire . En effet, lorsqu'un sous-problème est suffisamment petit, il peut, en principe, être résolu, ainsi que tous ses sous-problèmes, dans le cache , sans accéder à la mémoire principale , plus lente . Un algorithme conçu pour exploiter le cache de cette manière est dit « insensible au cache » , car il ne prend pas en compte la taille du cache comme paramètre explicite . De plus, les algorithmes de type « diviser pour régner » peuvent être conçus pour des algorithmes importants (par exemple, le tri, les FFT et la multiplication matricielle) afin d'être des algorithmes insensibles au cache optimaux : ils utilisent le cache de manière probablement optimale, au sens asymptotique, quelle que soit sa taille. À l'inverse, l'approche traditionnelle d'exploitation du cache consiste à utiliser le blocage , comme dans l'optimisation par imbrication de boucles , où le problème est explicitement divisé en segments de taille appropriée. Cette approche peut également exploiter le cache de manière optimale, mais uniquement si l'algorithme est adapté aux tailles de cache spécifiques d'une machine donnée.

Le même avantage existe en ce qui concerne d'autres systèmes de stockage hiérarchiques, tels que NUMA ou la mémoire virtuelle , ainsi que pour plusieurs niveaux de cache : une fois qu'un sous-problème est suffisamment petit, il peut être résolu au sein d'un niveau donné de la hiérarchie, sans accéder aux niveaux supérieurs (plus lents).

Dans les calculs utilisant l'arithmétique arrondie, par exemple avec des nombres à virgule flottante , un algorithme de type « diviser pour régner » peut donner des résultats plus précis qu'une méthode itérative en apparence équivalente. Par exemple, on peut additionner N nombres soit par une simple boucle qui ajoute chaque donnée à une variable, soit par un algorithme de type « diviser pour régner » appelé sommation par paires, qui divise l'ensemble de données en deux moitiés, calcule récursivement la somme de chaque moitié, puis additionne les deux sommes. Bien que la seconde méthode effectue le même nombre d'additions que la première et présente le surcoût des appels récursifs, elle est généralement plus précise.

Les algorithmes de type « diviser pour régner » sont naturellement implémentés sous forme de procédures récursives . Dans ce cas, les sous-problèmes partiels ayant permis d'aboutir au problème en cours de résolution sont automatiquement stockés dans la pile d'appels de la procédure . Une fonction récursive est une fonction qui s'appelle elle-même au sein de sa définition.

Les algorithmes de type « diviser pour régner » peuvent également être implémentés par un programme non récursif qui stocke les sous-problèmes partiels dans une structure de données explicite, telle qu'une pile , une file ou une file de priorité . Cette approche offre une plus grande liberté dans le choix du sous-problème à résoudre ensuite, une caractéristique importante dans certaines applications, comme la récursivité en largeur et la méthode de séparation et d'évaluation pour l'optimisation de fonctions. Cette approche est également la solution standard dans les langages de programmation qui ne prennent pas en charge les procédures récursives.

Dans les implémentations récursives d'algorithmes de tri par objets (D&C), il est impératif de veiller à allouer suffisamment de mémoire à la pile de récursion ; à défaut, l'exécution risque d'échouer en raison d' un dépassement de capacité de la pile . Les algorithmes D&C performants en termes de temps d'exécution présentent souvent une faible profondeur de récursion. Par exemple, l'algorithme de tri rapide peut être implémenté de manière à ne jamais nécessiter plus de 2 appels récursifs imbriqués pour trier les éléments.

Il peut être difficile de prévenir les débordements de pile lors de l'utilisation de procédures récursives, car de nombreux compilateurs traitent la pile de récursion comme un bloc de mémoire contigu, et certains lui réservent même un espace fixe. De plus, les compilateurs peuvent y stocker plus d'informations que nécessaire, notamment l'adresse de retour, les paramètres inchangés et les variables locales de la procédure. Par conséquent, le risque de débordement de pile peut être réduit en limitant le nombre de paramètres et de variables locales dans la procédure récursive, ou en remplaçant la récursivité par une structure de données de pile explicite.

Dans tout algorithme récursif, il existe une grande liberté dans le choix des cas de base , les petits sous-problèmes qui sont résolus directement afin de terminer la récursion.

Choisir les cas de base les plus simples ou les plus petits possibles est plus élégant et conduit généralement à des programmes plus simples, car il y a moins de cas à considérer et ils sont plus faciles à résoudre. Par exemple, un algorithme de transformée de Fourier rapide peut interrompre la récursion lorsque l'entrée est un seul échantillon, et l'algorithme de tri rapide peut s'arrêter lorsque l'entrée est la liste vide ; dans les deux cas, il n'y a qu'un seul cas de base à considérer, et il ne nécessite aucun traitement.

En revanche, l'efficacité s'améliore souvent si la récursivité est interrompue à des cas de base relativement importants, et que ceux-ci sont résolus de manière non récursive, aboutissant à un algorithme hybride . Cette stratégie évite la surcharge des appels récursifs peu ou pas productifs et peut également permettre l'utilisation d'algorithmes non récursifs spécialisés qui, pour ces cas de base, sont plus efficaces qu'une récursivité explicite. Une procédure générale pour un algorithme récursif hybride simple consiste à court-circuiter le cas de base , également appelé récursivité à distance . Dans ce cas, on vérifie si l'étape suivante aboutira au cas de base avant l'appel de fonction, évitant ainsi un appel inutile. Par exemple, dans un arbre, plutôt que d'effectuer une récursion vers un nœud enfant puis de vérifier s'il est nul, vérifier la valeur nulle avant la récursion permet d'éviter la moitié des appels de fonction dans certains algorithmes sur les arbres binaires. Étant donné qu'un algorithme de division et de regroupement (D&C) réduit finalement chaque instance de problème ou de sous-problème à un grand nombre d'instances de base, ces dernières dominent souvent le coût global de l'algorithme, en particulier lorsque la surcharge liée à la division/regroupement est faible. Notez que ces considérations ne dépendent pas du fait que la récursivité soit implémentée par le compilateur ou par une pile explicite.

Ainsi, par exemple, de nombreuses implémentations de l'algorithme quicksort en bibliothèque basculent vers un simple tri par insertion basé sur une boucle (ou un algorithme similaire) dès que le nombre d'éléments à trier est suffisamment petit. Il est important de noter que si la liste vide était le seul cas de base, le tri d'une liste contenant des éléments impliquerait un nombre maximal d'appels à quicksort qui ne feraient rien d'autre que retourner immédiatement. Augmenter les cas de base à des listes de taille 2 ou moins permet d'éliminer la plupart de ces appels inutiles. Plus généralement, un cas de base supérieur à 2 est généralement utilisé pour réduire le temps passé en surcharge liée aux appels de fonction ou à la manipulation de la pile.

On peut également utiliser de grands ensembles de cas de base qui emploient toujours un algorithme de type « diviser pour régner », mais implémentés pour un ensemble prédéterminé de tailles fixes. Dans ce cas, l'algorithme peut être entièrement déroulé en un code sans récursivité, boucles ni conditions (technique liée à l' évaluation partielle ). Par exemple, cette approche est utilisée dans certaines implémentations efficaces de la FFT, où les cas de base sont des implémentations déroulées d'algorithmes FFT de type « diviser pour régner » pour un ensemble de tailles fixes. Des méthodes de génération de code source peuvent être utilisées pour produire le grand nombre de cas de base distincts nécessaires à la mise en œuvre efficace de cette stratégie.

La version généralisée de cette idée est connue sous le nom de « déroulement » ou « grossissement » de la récursion, et diverses techniques ont été proposées pour automatiser la procédure d'élargissement du cas de base.

Pour certains problèmes, la récursion ramifiée peut aboutir à l'évaluation répétée du même sous-problème. Dans ce cas, il peut être judicieux d'identifier et de sauvegarder les solutions de ces sous-problèmes redondants, une technique communément appelée mémoïsation . Poussée à l'extrême, elle conduit à des algorithmes ascendants de type « diviser pour régner », tels que la programmation dynamique .