Chapitre 7 : exemples d’algorithmes gloutons Partie 4 1 Algorithmique avancée

« Chapitre 7 : exemples d’algorithmes gloutons Partie 4 1 Algorithmique avancée Introduction : les problèmes d’optimisation En informatique, on rencontre souvent des problèmes d’optimisation, c’est-à-dire des problèmes pour lesquels on cherche la meilleure solution possible satisfaisant un certain nombre de contraintes. Par exemple :  la recherche du plus court chemin reliant deux villes en utilisant un réseau routier existant,  le nombre minimum de pièces de monnaie que l’on peut rendre à partir du contenu d’une caisse enregistreuse commerciale,  le nombre maximum de cours que l’on peut organiser dans une même journée dans un établissement ayant un nombre fixé de salles et connaissant la durée et les horaires de chaque cours,  ... En pratique, on cherche à trouver une solution algorithmique pour résoudre des problèmes d’optimisation quand : 1.

le problème possède un très grand nombre de solutions et 2.

on sait évaluer la qualité de chacune des solutions (et donc dire quelle solution est meilleure parmi plusieurs). 2 Le problème du voyageur de commerce Un voyageur de commerce doit se rendre dans plusieurs villes.

Si on connaı̂t la distance séparant chacune des villes, peut-on déterminer l’itinéraire le plus court lui permettant de visiter chaque ville une et une seule fois et qui se termine dans la ville de départ ? Supposons que le voyageur se trouve dans une première ville A et qu’il doit se rendre dans quatre autres villes B,C,D et E et revenir à son point de départ A.

On donne le tableau des distance kilométriques séparant chacune des villes : Villes A B C D E A 55 303 188 183 B 55 306 176 203 C 303 306 142 153 D 188 176 142 E 183 203 153 123 303 A 55 123 188 183 306 203 C 153 142 B 176 D E 123 Pour déterminer la meilleure solution on peut calculer toute les sommes de tous les circuits possibles : Circuit A-B-C-D-E-A ou A-E-D-C-B-A A-B-C-E-D-A ou A-D-B-C-B-A A-B-D-C-E-A ou A-E-C-D-B-A A-B-D-E-C-A ou A-C-E-D-B-A A-B-E-C-D-A ou A-D-C-E-B-A A-B-E-D-C-A ou A-C-D-E-B-A A-C-B-E-D-A ou A-D-E-B-C-A A-C-B-D-E-A ou A-E-D-B-C-A A-C-D-B-E-A ou A-E-B-D-C-A A-C-E-B-D-A ou A-D-B-E-C-A A-D-B-C-E-A ou A-E-C-B-D-A A-E-B-C-D-A ou A-D-C-B-E-A Somme 55 + 306 + 142 + 123 + 183 55 + 306 + 153 + 123 + 188 55 + 176 + 142 + 153 + 183 55 + 176 + 123 + 153 + 303 55 + 203 + 153 + 142 + 188 55 + 203 + 123 + 142 + 303 303 + 306 + 203 + 123 + 188 303 + 306 + 176 + 123 + 183 303 + 142 + 176 + 203 + 183 303 + 153 + 203 + 176 + 188 188 + 176 + 306 + 153 + 183 183 + 203 + 306 + 142 + 188 Total 809 825 709 810 741 826 1123 1091 1007 1023 1006 1022 Puisqu’il y a 5 villes, il y a 12 sommes à calculer : p4  3  2  1q  2 car à partir de la ville A il y a 4 choix possibles (B, C, D ou E), puis à partir de la deuxième ville il ne reste que 3 choix de destination, puis 2 choix, puis 1 choix.

Les circuits obtenus sont en double, donc on divise par deux. On constate alors qu’en appliquant le même raisonnement, pour 6 villes on obtiendrait 60 calculs différents, puis pour 7 villes 180 calculs, ...

pour 10 villes 181 440 sommes à calculer, ...

pour 20 villes plus de 6  1016 calculs.

Le nombre de calculs augmente beaucoup trop vite pour envisager d’implémenter cette méthode (les temps de calculs deviendraient vite infinis). Une autre stratégie existe : la solution dite gloutonne.

Elle consiste à choisir la ville la plus proche à chaque étape (meilleur choix sur le moment) dans l’espoir d’obtenir une solution globalement optimale (la meilleure possible).

Du coup, à chaque étape on va construire le circuit en ajoutant la ville la plus proche de la dernière ajoutée.

Dans l’exemple présenté on obtiendra le circuit A-B-D-E-C-A, soit une distance de 55 176 123 153 303  810.

Cette solution n’est pas la meilleure, mais on a trouvé l’une des moins mauvaises, ce qui peut suffire la plupart du temps et surtout, pour obtenir cette solution, nous n’en avons calculé qu’une seule. Spécialité NSI 1/3 Partie 4 Chapitre 7 : exemples d’algorithmes gloutons Algorithmique avancée Remarque 2.1 (pour aller plus loin) Il n’existe pas d’algorithme rapide permettant de trouver une solution optimale au problème du voyageur de commerce.

Ce problème est NP-complet : il n’existe a priori pas d’algorithme en temps polynomial pour le résoudre ; autrement dit ce problème est classé comme difficile.

Un million de dollar pour celui ou celle qui arrivera à démontrer que les problèmes NP-complets n’ont pas de solution algorithmique en temps polynomial. 3 Un problème d’organisation On dispose du planning d’un festival culturel qui propose des spectacles sur cinq scènes différentes. Un festivalier, qui arrive à 10 : 00, cherche à choisir des spectacles dans ce planning en cherchant à voir le plus grand nombre de spectacles possibles dans sa journée (maximiser une quantité) et en s’imposant de voir chaque spectacle en entier (contraintes). Il peut envisager deux algorithmes gloutons : 1.

Règle de choix de l’algorithme glouton A (basée sur l’idée que moins on attend entre deux spectacles, plus on verra de spectacles) : A chaque étape on choisit le prochain spectacle qui commence.... »