Algorithme parallèle - Techniques de conception
La sélection d'une technique de conception appropriée pour un algorithme parallèle est la tâche la plus difficile et la plus importante. La plupart des problèmes de programmation parallèle peuvent avoir plus d'une solution. Dans ce chapitre, nous aborderons les techniques de conception suivantes pour les algorithmes parallèles -
- Diviser et conquérir
- Méthode gourmande
- Programmation dynamique
- Backtracking
- Branche et lié
- Programmation linéaire
Méthode Divide and Conquer
Dans l'approche diviser pour conquérir, le problème est divisé en plusieurs petits sous-problèmes. Ensuite, les sous-problèmes sont résolus de manière récursive et combinés pour obtenir la solution du problème d'origine.
L'approche diviser pour conquérir implique les étapes suivantes à chaque niveau -
Divide - Le problème d'origine est divisé en sous-problèmes.
Conquer - Les sous-problèmes sont résolus de manière récursive.
Combine - Les solutions des sous-problèmes sont combinées ensemble pour obtenir la solution du problème d'origine.
L'approche diviser et conquérir est appliquée dans les algorithmes suivants -
- Recherche binaire
- Tri rapide
- Tri par fusion
- Multiplication entière
- Inversion de matrice
- Multiplication matricielle
Méthode gourmande
Dans un algorithme gourmand d'optimisation de la solution, la meilleure solution est choisie à tout moment. Un algorithme glouton est très facile à appliquer à des problèmes complexes. Il décide quelle étape fournira la solution la plus précise à l'étape suivante.
Cet algorithme est un appelé greedycar lorsque la solution optimale à l'instance plus petite est fournie, l'algorithme ne considère pas le programme total dans son ensemble. Une fois qu'une solution est considérée, l'algorithme glouton ne considère plus jamais la même solution.
Un algorithme gourmand fonctionne de manière récursive en créant un groupe d'objets à partir des plus petits composants possibles. La récursivité est une procédure pour résoudre un problème dans lequel la solution d'un problème spécifique dépend de la solution de la plus petite instance de ce problème.
Programmation dynamique
La programmation dynamique est une technique d'optimisation qui divise le problème en sous-problèmes plus petits et après avoir résolu chaque sous-problème, la programmation dynamique combine toutes les solutions pour obtenir la solution ultime. Contrairement à la méthode de division et de conquête, la programmation dynamique réutilise la solution aux sous-problèmes plusieurs fois.
L'algorithme récursif pour la série Fibonacci est un exemple de programmation dynamique.
Algorithme de retour en arrière
Le backtracking est une technique d'optimisation pour résoudre des problèmes combinatoires. Il est appliqué à la fois aux problèmes programmatiques et réels. Le problème des huit reines, le puzzle Sudoku et le passage dans un labyrinthe sont des exemples populaires où l'algorithme de retour en arrière est utilisé.
En backtracking, on part d'une solution possible, qui satisfait toutes les conditions requises. Ensuite, nous passons au niveau suivant et si ce niveau ne produit pas une solution satisfaisante, nous retournons un niveau en arrière et commençons avec une nouvelle option.
Branche et lié
Un algorithme de branchement et lié est une technique d'optimisation pour obtenir une solution optimale au problème. Il recherche la meilleure solution pour un problème donné dans tout l'espace de la solution. Les limites de la fonction à optimiser sont fusionnées avec la valeur de la dernière meilleure solution. Il permet à l'algorithme de trouver complètement des parties de l'espace de solution.
Le but d'une recherche branchée et liée est de conserver le chemin le moins coûteux vers une cible. Une fois qu'une solution est trouvée, elle peut continuer à améliorer la solution. La recherche de branche et de limite est implémentée dans la recherche limitée en profondeur et la recherche en profondeur d'abord.
Programmation linéaire
La programmation linéaire décrit une large classe de travaux d'optimisation où le critère d'optimisation et les contraintes sont des fonctions linéaires. C'est une technique pour obtenir le meilleur résultat comme le profit maximum, le chemin le plus court ou le coût le plus bas.
Dans cette programmation, nous avons un ensemble de variables et nous devons leur attribuer des valeurs absolues pour satisfaire un ensemble d'équations linéaires et maximiser ou minimiser une fonction objectif linéaire donnée.