Algorithmes d'Approximation - Chapitre 5 PDF

Université Ferhat Abbas – Setif 1- Faculté des sciences Département d’informatique Algorithmique Avancé et Complexité Dr. Hadi Fairouz Maitre de conférences [email protected]  Chapitre 5 Algorithme...

Université Ferhat Abbas – Setif 1- Faculté des sciences Département d’informatique Algorithmique Avancé et Complexité Dr. Hadi Fairouz Maitre de conférences [email protected]  Chapitre 5 Algorithmes d'Approximation Contenu du chapitre  Définition d’un algorithme d’approximation  La nécessité des algorithmes d'approximation  Les types d'algorithmes d'approximation  Le facteur d'approximation  Applications des algorithmes d'approximation Chapitre 5 Algorithmes d’Approximation Introduction Certains problèmes d'optimisation, tels que ceux classés NP-complets ou NP-difficiles, sont connus pour leur complexité intrinsèque. Dans le cadre de ces problèmes, il est pratiquement impossible de trouver une solution optimale dans un temps polynomial, même pour des instances relativement petites. Ces problèmes se rencontrent dans de nombreux domaines, notamment la planification, l’optimisation des réseaux et la logistique. Leur particularité réside dans le fait qu'il n'existe pas d'algorithmes dont la complexité temporelle soit polynomiale et qui garantissent une solution optimale pour toutes les instances. Face à cette réalité, la question se pose : comment peut-on alors obtenir des solutions suffisamment bonnes, dans des délais raisonnables, pour ces problèmes complexes ? La réponse réside dans l'utilisation d'algorithmes d’approximation. Ces algorithmes, bien qu'ils ne garantissent pas une solution optimale, permettent de produire des solutions proches de l'optimum, tout en restant dans des limites de temps raisonnables grâce à une complexité temporelle polynomiale. Ils offrent ainsi un compromis entre la qualité de la solution et les ressources computationnelles nécessaires, rendant leur utilisation particulièrement pertinente dans des situations où une solution exacte est soit trop coûteuse, soit inutile.  Définition d’un algorithme d’approximation Un algorithme d'approximation est une méthode utilisée pour résoudre un problème d'optimisation lorsque la solution optimale est trop coûteuse à calculer. Ces algorithmes, principalement utilisés pour des problèmes dits NP-complets ou NP-difficiles, cherchent à trouver une solution proche de l'optimal en un temps réduit. Ces types de problèmes sont particulièrement difficiles à résoudre exactement dans un temps raisonnable, surtout lorsque leur taille devient importante. Exemple 1 : Problème de Voyageur de Commerce (TSP) Planifiez un itinéraire pour un vendeur de commerce qui doit visiter plusieurs villes. Le but est de trouver le chemin le plus court possible. Il existe des algorithmes qui peuvent donner une solution rapide, mais pas nécessairement parfaite. L'algorithme pourrait donner un itinéraire qui est près de l'optimal, mais pas forcément le meilleur possible. C'est ça, un algorithme d'approximation. 1 Chapitre 5 Algorithmes d’Approximation Figure 5.1 : Problème de Voyageur de Commerce (TSP)  La nécessité des algorithmes d'approximation Les problèmes d'optimisation peuvent souvent être résolus de manière exacte mais cela prendrait beaucoup trop de temps, même pour des ordinateurs puissants. Par exemple, pour des problèmes complexes comme le voyageur de commerce (TSP), le temps nécessaire pour explorer toutes les solutions possibles augmente très rapidement à mesure que le nombre de villes augmente. Les algorithmes d'approximation permettent donc de résoudre ces problèmes de manière plus rapide en acceptant une solution qui est "assez bonne" plutôt que parfaite. Exemple 2 : Problème du Sac à Dos Imaginons que vous ayez un sac avec une certaine capacité et que vous deviez choisir un ensemble d'objets à y mettre. Chaque objet a une valeur et un poids. L'objectif est de maximiser la valeur totale des objets que vous pouvez mettre dans le sac sans dépasser la capacité du sac. Si vous essayez de trouver la meilleure solution possible, cela pourrait prendre un temps énorme, surtout si vous avez beaucoup d'objets. Par exemple, pour 100 objets, il y aurait des milliards de solutions possibles à tester ! Une solution d'approximation consisterait à choisir les objets en fonction de leur rapport valeur/poids de manière gloutonne. Autrement dit, vous choisiriez d'abord l'objet avec le meilleur rapport valeur/poids, puis le suivant, jusqu'à ce que le sac soit plein. Cette méthode est plus rapide, mais elle ne garantit pas que vous obtiendrez la meilleure solution possible. 2 Chapitre 5 Algorithmes d’Approximation Figure 5.2 : Problème du Sac à Dos  Les types d'algorithmes d'approximation Il existe plusieurs méthodes pour approcher les solutions optimales :  Algorithmes gloutons (greedy) : Ces algorithmes font des choix locaux à chaque étape, en espérant que ces choix conduiront à une solution optimale globale. Par exemple, dans le problème du sac à dos, un algorithme glouton choisit toujours l'objet ayant le meilleur rapport valeur/poids. Algorithme Glouton Trier les éléments selon un critère (par exemple, par valeur décroissante) Initialiser une solution vide Pour chaque élément dans la liste triée : Si l'élément peut être ajouté à la solution sans violer les contraintes : Ajouter l'élément à la solution Retourner la solution 3 Chapitre 5 Algorithmes d’Approximation Dans un algorithme glouton, le critère de tri dépend du problème spécifique que vous cherchez à résoudre. L'idée générale d'un algorithme glouton est de prendre des décisions locales optimales à chaque étape, mais ces décisions sont basées sur un critère qui varie d'un problème à l'autre.  Le critère de tri doit donc être bien défini selon les caractéristiques du problème. L’algorithme glouton ne garantit pas toujours une solution optimale globale, mais il fournit une solution rapide et souvent proche de l’optimum dans de nombreux cas.  Recherche locale (Local Search) : Une autre méthode consiste à commencer avec une solution quelconque et à essayer d'améliorer cette solution étape par étape en effectuant de petites modifications. Par exemple, dans le voyageur de commerce (TSP), vous pouvez commencer par un itinéraire quelconque, puis échanger deux villes pour voir si cela réduit la distance totale. Exemple de pseudo-code pour un algorithme de Recherche locale (Local Search), un algorithme souvent utilisé pour résoudre des problèmes d'optimisation en explorant les voisins d'une solution donnée : Algorithme RechercheLocale Initialiser une solution initiale S Tant que (condition d'arrêt non remplie) : Trouver les voisins de la solution S Sélectionner le meilleur voisin S' parmi les voisins Si (S' est meilleur que S) : Mettre à jour S ← S’ Sinon : Terminer (condition d'arrêt remplie) Retourner la solution S 4 Chapitre 5 Algorithmes d’Approximation Explication: 1. Initialisation : Une solution initiale est générée. Cette solution peut être aléatoire ou issue d'une approche heuristique. 2. Boucle de recherche locale : À chaque itération, l'algorithme explore les voisins de la solution actuelle (voisinage défini par une fonction qui génère des solutions voisines en modifiant légèrement la solution actuelle). 3. Sélection du meilleur voisin : Parmi les voisins générés, l'algorithme choisit celui qui est le meilleur selon une fonction de coût ou d'évaluation (par exemple, minimiser ou maximiser une fonction objective). 4. Mise à jour de la solution : Si un voisin amélioré est trouvé, la solution est mise à jour. Sinon, l'algorithme peut s'arrêter (condition d'arrêt atteinte, par exemple, un nombre maximal d'itérations ou si la solution n'améliore plus). 5. Retour de la solution finale : Une fois l'algorithme arrêté, la solution actuelle est retournée comme étant la meilleure trouvée.  Diviser pour régner : Cette approche divise un grand problème en plusieurs sous-problèmes plus petits, les résout et combine les résultats. Cela permet souvent de trouver une solution approximative assez rapidement. Par exemple, Le problème du voyageur de commerce (TSP) est NP-difficile, mais il existe des méthodes d'approximation pour certaines versions spécifiques du problème, comme le TSP euclidien (où les points sont dans un espace euclidien).  Diviser : Diviser les points en sous-ensembles plus petits à l'aide d'un découpage géographique (par exemple, diviser l'ensemble des points en régions géographiques distinctes).  Régner : Appliquer des heuristiques pour chaque sous-ensemble, par exemple, résoudre le TSP localement dans chaque sous-ensemble de points. 5 Chapitre 5 Algorithmes d’Approximation  Combiner : Réunir les solutions de chaque sous-ensemble en une solution approximative globale, souvent en réorganisant les sous-solutions obtenues pour optimiser le parcours total.  Le facteur d'approximation Le facteur d'approximation permet d'évaluer la qualité des solutions obtenues par des algorithmes approximatifs comparées à la solution optimale d'un problème donné. Puisque dans de nombreux cas, obtenir une solution exacte est difficile ou coûteux, l'objectif est de trouver des solutions proches de l'optimum dans un temps raisonnable. Il existe principalement deux types de facteurs d'approximation : multiplicatif et additif. Ces deux types de facteurs donnent des garanties sur la proximité de la solution approximée par rapport à la solution optimale, mais selon différentes métriques : ratio ou différence absolue.  Approximation multiplicative (ou rationnelle) L'approximation multiplicative compare la solution approximée à la solution optimale à travers un facteur multiplicatif. Ce type de facteur est particulièrement adapté aux problèmes où l'on cherche à maximiser ou minimiser une certaine fonction objective.  Approximation multiplicative :  Pour un problème de maximisation : Solution approchée ≤ α où α ≥ 1 Solution optimale  Pour un problème de minimisation : Solution approchée ≥ α où α ≤ 1 Solution optimale  Approximation additive L'approximation additive mesure la différence absolue entre la solution approximée et la solution optimale. Contrairement à l'approximation multiplicative qui utilise un facteur proportionnel, l'approximation additive garantit que la différence entre la solution approchée et la solution optimale est bornée par une constante donnée. 6 Chapitre 5 Algorithmes d’Approximation Critère d'approximation : L'approximation additive est souvent utilisée dans des situations où la solution optimale et la solution approchée sont exprimées dans des unités similaires (par exemple, une quantité totale ou un coût global) et où on souhaite limiter la différence absolue plutôt que d'exprimer un ratio proportionnel. Formule : Solution approchée − Solution optimale ≤ β  Le facteur d'approximation est une mesure fondamentale pour évaluer la qualité des solutions trouvées par des algorithmes d'approximation. Selon la nature du problème (maximisation ou minimisation), on choisira d'utiliser un facteur multiplicatif (qui donne un ratio entre la solution approximée et la solution optimale) ou un facteur additif (qui donne une borne sur la différence absolue entre les deux solutions). Dans tous les cas, ces facteurs permettent de garantir que la solution obtenue par un algorithme approximatif est proche de l'optimum tout en offrant des garanties théoriques sur la qualité des résultats.  Applications des algorithmes d'approximation Les algorithmes d'approximation sont utilisés dans une grande variété de domaines, notamment :  Planification des ressources (par exemple, planifier les horaires des trains ou des avions).  Réseaux et communication (optimisation des flux de données sur un réseau).  Logistique (planification des itinéraires de livraison, gestion des stocks).  Finance (gestion des portefeuilles d'investissement). 7 Chapitre 5 Algorithmes d’Approximation Conclusion Les algorithmes d'approximation sont des outils puissants pour résoudre des problèmes complexes d'optimisation dans des délais raisonnables. Bien qu'ils ne garantissent pas une solution parfaite, ils offrent une solution proche de l'optimal, ce qui est souvent suffisant dans la pratique. Ils sont particulièrement utiles pour résoudre des problèmes NP-complets et NP-difficiles, où la recherche de la solution exacte serait trop coûteuse en termes de temps et de ressources. Les algorithmes d'approximation permettent de trouver rapidement des solutions suffisamment bonnes pour des problèmes complexes, là où les méthodes exactes sont impraticables. 8