Supposons que l'on ait déterminé une certaine liste de villes dans lesquelles nous devons nous rendre et que l'on cherche un itinéraire minimisant la distance totale parcourue.
On s'autorisera à visiter les villes dans n'importe quel ordre, mais aucune ne doit être négligée, et il faudra à la fin revenir à la ville de départ.
Voici une situation concrète. Nous partons de Carhaix et devons nous rendre à Brest, à Rennes, à Nantes et à Vannes avant de retourner à Carhaix.
Le tableau des distances routières kilométriques entre ces différentes villes est le suivant :
| Carhaix | Brest | Rennes | Nantes | Vannes | |
| Carhaix | 80 | 154 | 227 | 111 | |
| Brest | 80 | 239 | 298 | 112 | |
| Rennes | 154 | 239 | 106 | 95 | |
| Nantes | 227 | 298 | 106 | 114 | |
| Vannes | 111 | 112 | 95 | 114 |
Ces données sont issues de https://www.geoportail.gouv.fr, arrondies à 1 unité la plus proche.
Le problème se ramène à trouver un ordre de visite des quatre villes Brest, Rennes, Nantes et Vannes pour lequel la somme des distances données par ce tableau pour chaque étape est aussi petite que possible.
Une manière simple d'aborder ce problème consiste à énumérer tous les ordres possibles, calculer pour chacun la distance correspondante, pour sélectionner ensuite la plus petite.
On a ici vingt-quatre itinéraires possibles, dont douze sont détaillés dans le tableau ci-dessous, où le départ et l'arrivée à Carhaix sont sous-entendus.
Cependant, cette technique ne passe pas à l'échelle. En se fixant une liste plus longue de villes à visiter, le nombre de circuits différents à analyser devient vite beaucoup trop important, et ce même pour les capacités de calcul d'un ordinateur.
Nous avons ainsi 24 circuits pour 4 villes (hors ville de depart), presque 2 millions pour 10 villes, plus de 3 milliards pour 13 villes, et plus d'un milliards de milliards pour 20 villes (la valeur exacte est la moitié de la factorielle du nombre de villes).
| Circuit | Kilomètrage |
| Carrhaix - Brest - Rennes - Nantes - Vannes - Carhaix | 80 + 239 + 106 + 114 + 111 = 650 |
| Carrhaix - Brest - Rennes - Vannes - Nantes - Carhaix | 80 + 239 + 95 + 114 + 227 = 755 |
| Carrhaix - Brest - Nantes - Rennes - Vannes - Carhaix | 80 + 298 + 106 + 95 + 111 = 690 |
| Carrhaix - Brest - Nantes - Vannes - Rennes - Carhaix | 80 + 298 + 114 + 95 + 154 = 741 |
| Carrhaix - Brest - Vannes - Rennes - Nantes - Carhaix | 80 + 112 + 95 + 106 + 227 = 620 |
| Carrhaix - Brest - Vannes - Nantes - Rennes - Carhaix | 80 + 112 + 114 + 106 + 154 = 566 |
| Carrhaix - Rennes - Brest - Nantes - Vannes - Carhaix | 154 + 239 + 298 + 114 + 111 = 916 |
| Carrhaix - Rennes - Brest - Vannes - Nantes - Carhaix | 154 + 239 + 112 + 114 + 227 = 846 |
| Carrhaix - Rennes - Nantes - Brest - Vannes - Carhaix | 154 + 106 + 298 + 112 + 111 = 781 |
| Carrhaix - Rennes - Nantes - Vannes - Brest - Carhaix | 154 + 106 + 114 + 112 + 80 = 566 |
| Carrhaix - Rennes - Vannes - Brest - Nantes - Carhaix | 154 + 95 + 112 + 298 + 227 = 886 |
| Carrhaix - Rennes - Vannes - Nantes - Brest - Carhaix | 154 + 95 + 114 + 298 + 80 = 741 |
| Carrhaix - Nantes - Brest - Rennes - Vannes - Carhaix | 227 + 298 + 239 + 95 + 111 = 970 |
| Carrhaix - Nantes - Brest - Vannes - Rennes - Carhaix | 227 + 298 + 112 + 95 + 154 = 886 |
| Carrhaix - Nantes - Rennes - Brest - Vannes - Carhaix | 227 + 106 + 239 + 112 + 111 = 795 |
| Carrhaix - Nantes - Rennes - Vannes - Brest - Carhaix | 227 + 106 + 95 + 112 + 80 = 620 |
| Carrhaix - Nantes - Vannes - Brest - Rennes - Carhaix | 227 + 114 + 112 + 239 + 154 = 846 |
| Carrhaix - Nantes - Vannes - Rennes - Brest - Carhaix | 227 + 114 + 95 + 239 + 80 = 755 |
| Carrhaix - Vannes - Brest - Rennes - Nantes - Carhaix | 111 + 112 + 239 + 106 + 227 = 795 |
| Carrhaix - Vannes - Brest - Nantes - Rennes - Carhaix | 111 + 112 + 298 + 106 + 154 = 781 |
| Carrhaix - Vannes - Rennes - Brest - Nantes - Carhaix | 111 + 95 + 239 + 298 + 227 = 970 |
| Carrhaix - Vannes - Rennes - Nantes - Brest - Carhaix | 111 + 95 + 106 + 298 + 80 = 690 |
| Carrhaix - Vannes - Nantes - Brest - Rennes - Carhaix | 111 + 114 + 298 + 239 + 154 = 916 |
| Carrhaix - Vannes - Nantes - Rennes - Brest - Carhaix | 111 + 114 + 106 + 239 + 80 = 650 |
Face à de tels problèmes d'optimisation impossibles à explorer dans un temps raisonnable, il peut être utile de connaitre des algorithmes donnant rapidement une réponse qui, sans être nécessairement optimale, resterait bonne. La méthode gloutonne présentée dans cette séquence donne une approche simple pour concevoir de tels algorithmes souvent approximatifs mais rapides.
Les différents algorithmes s'appliquant à un tableau de longueur n peuvent impliquer des nombres d'opérations très différents. proportionnels par exemple à n. (parcours d'un tableau) ou au carré de n (tri par sélection). Pour mesurer l'importance de cette différence, voici un petit tableau de taille n donnant un nombre d'opérations proche du milliard, c'est-à-dire un nombre d'opération qu'il est envisageable de faire exécuter à un programme.
Nombre op.\tn maximal
log(n) 10300 000 000
√ n 1018
n 1 000 000 000
n2 31 600
n3 1000
2n 30
n! 12
On observe qu'un algorithme avec un nombre d'opérations proportionnel à une petite puissance ne pourra être appliqué à un tableau grand voire très grand. Si le nombre d'opérations est en revanche exponentiel ou pire alors l'algorithme ne pourra être appliqué\tqu'à de tout petits tableaux.
","title":"Ordres de grandeur de la complexité des algorithmes"},{"edit":" "}],[{"text":"Les algorithmes gloutons sont utilises pour répondre à des problèmes d'optimisation, c'est-à-dire des problèmes algorithmiques dans lesquels l'objectif est de trouver une solution \"la meilleure possible\" selon un certain critère, parmi un ensemble de solutions également valides mais potentiellement moins avantageuses.
Le contexte général d'un tel problème d'optimisation est donc le suivant :
• on considère un problème possédant un très grand nombre de solutions,
• on dispose d'une fonction mathématique évaluant la qualité de chaque solution,
• on cherche une solution qui soit bonne, voire la meilleure.
Les algorithmes gloutons s'appliquent lorsque de plus :
• la recherche d'une solution peut se ramener à une succession de choix, qui produisent et précisent petit à petit une solution partielle,
• on dispose d'une fonction mathématique évaluant la qualité de chaque solution partielle (dont on attend en général qu'elle soit cohérente avec la fonction d'évaluation des solutions complètes).
L'approche gloutonne consiste alors à construire une solution complète par une succession de choix en prenant systématiquement l'option donnant la meilleure solution partielle.
","title":"Algorithmes gloutons"},{"edit":" "}],[{"text":"Certains problèmes algorithmiques sont difficiles, au point que l'on peut parfois aller jusqu'à, démontrer que leur résolution demande un nombre d'opérations exponentiel.
Par exemple, pour déterminer s'il est possible de gagner à coup sur à une partie du jeu de dames à partir d'une certaine configuration sur un plateau de coté n peut requérir un nombre d'opérations proportionnel à l'exponentielle de n. (cela vaut également pour le go et les échecs).
Une famille do problèmes célèbre dans le domaine est celle des problèmes NP-cormplets, à laquelle appartient le problème du voyageur.
Ces problèmes répondent à une question de la forme \"Existe-t-il une solution telle quo...\t? \"
et sont caractérisées par deux conditions :
• Il est facile de vérifier la validité ou l'invalidité d'une prétendue solution (un itinéraire étant donné, ii est: facile de vérifier qu'il passe par toutes les villes et de calculer sa distance totale).
• L'ensemble des solutions potentielles est vaste et nous ne savons pas l'explorer efficacement à la recherche d'une solution valide.
Par exemple pour notre problème d'itinéraire, il faut se poser la question : Existe-t-il un itinéraire passant par toutes
les villes en moins de 750kilomètres?
Personne ne sait, résoudre ces problèmes à coup sur en un temps qui soit meilleur qu'exponentiel. En pratique on ne peut donc les résoudre parfaitement que sur des instances de taille modeste. Une majorité des algorithmiciens tendent même à supposer qu'il soit effectivement impossible de résoudre ces problème en un temps raisonnable. Cependant, personne n'a encore réussi. à démontrer cette conjecture et un prix d'un million de dollars est d'ores et déjà promis à quiconque trancherait définitivement Ia. question.
.Ainsi, un problème NP-complet ne peut probablement pas être résolu parfaitement en un temps raisonnable pour des instances de grande taille. On se tourne alors le plus souvent vers des algorithmes donnant des solutions approchées.
Appliquons l'approche gloutonne à notre problème du voyageur. Le problème considéré est une visite de l'ensemble des villes, depuis une ville de départ déterminée et avec retour à cette ville. Une solution est donc n'importe quelle séquence passant par toutes les villes intermédiaires demandées, qu'on peut ramener à une succession de choix :
\"quelle sera ma prochaine étape ?\"
Une solution partielle est donc n'importe quel début de séquence.
La qualité d'une solution est inversement proportionnelle à la distance totale parcourue et on peut appliquer ce critère autant aux solutions partielles qu'aux solutions complètes.
Ces éléments mis en place, il ne reste plus qu'a appliquer la méthode gloutonne :
- partant de la ville de départ, aller à la ville la plus proche, puis à la ville la plus proche de cette dernière parmi les villes non encore visitées, et ainsi de suite.
| Carhaix | Brest | Rennes | Nantes | Vannes | |
| Carhaix | 80 | 154 | 227 | 111 | |
| Brest | 80 | 239 | 298 | 112 | |
| Rennes | 154 | 239 | 106 | 95 | |
| Nantes | 227 | 298 | 106 | 114 | |
| Vannes | 111 | 112 | 95 | 114 |
Compléter le texte ci-dessous pour appliquer l'algorithme glouton à notre voyage.
Partant de .............., nous irons donc en premier lieu à ......... , distante de ........ kilomètres.
Ensuite à ................ en ........ kilomètres,
puis à .............. en ........ kilomètres,
et enfin à .......... en ....... kilomètres,
avec ultime retour à ................ en ......... kilomètres.
Notre voyage fera donc ......... kilomètres.
L'itinéraire ainsi obtenu est plus long que le circuit minimal de ......... kilomètres vu en introduction, mais reste loin des assez nombreuses mauvaises solution qui demandaient plus de mille kilomètres. Et surtout, nous n'avons analyse qu'un unique itinéraire !
Le programme suivant propose une réalisation en Python de l'algorithme du voyageur glouton. Les n villes à visiter sont numérotées de 0 à n-1 et les distances entre villes sont stockées dans un tableau dist à deux dimensions tel que dist[i][j] donne la distance de la ville numéro i à la ville numéro j.
#tableau des villes
tabvilles = [\"Carhaix\",\"Brest\",\"Rennes\",\"Nantes\",\"Vannes\"]
#tableau des distances entre les villes
tabdist = [[ 0 , 80 , 154 , 227 , 111 ],
[ 80 , 0 , 239 , 298 , 112 ],
[ 154 , 239 , 0 , 106 , 95 ],
[ 227 , 298 , 106 , 0 , 114 ],
[ 111 , 112 , 95 , 114 , 0 ] ]
#ville de départ Carhaix
depart = 0
def plus_proche(ville, dist , visitees) :
\"\"\"Renvoie le numéro de la ville non encore visitée la plus proche
de la ville courante, en supposant qu'il en existe au moins une.\"\"\"
pp = None
for i in range(len(visitees)):
if visitees[i] : continue
if pp == None or dist[ville][i] < dist[ville][pp] :
pp = i
return pp
def voyageur(villes, dist, depart):
\"\"\"Affsche les etapes du parcours glouton depuis
la ville de depart.\"\"\"
n = len(villes)
visitees = [False] * n
courante = depart
for _ in range(n-1):
visitees[courante] = True
suivante = plus_proche(courante, dist , visitees)
print (\"on va de\", villes[courante] , \\
\"a\", villes[suivante] , \\
\"en\", dist[courante][suivante] , \"km\")
courante = suivante
print(\"on revient de\", villes[courante] , \\
\"a\", villes[depart] , \\
\"en\", dist[courante][depart] , \"km\")
voyageur(tabvilles, tabdist, depart)
La fonction principale voyageur prend en paramètres la liste des villes, la table des distances et le numéro de la ville de départ. Elle utilise un tableau visitees de booléens indiqnant pour chaque ville (donnée par son numéro) si elle a été visitée ou non, ainsi qu'une variable courante mémorisant le numéro de la ville actuelle.
La fonction est ensulte constituée d'une boucle qui, n-1 fois, marque comme visité la ville courante puis sélectionne la suivante.
La fonction voyageur délègue le choix de la ville suivante à une fonction auxiliaire plus_proche, qui prend en paramètres la table des distances, le numéro de la ville courante et le tableau des villes déjà visitées pour sélectionner la ville la plus proche de la ville courante parmi les villes non encore visitées.
Cette fonction est constituée d'une boucle examinant les villes tour à, tour en écartant les villes déjà visitées et en mémorisant dans une variable pp le numéro de la ville non visitée la plus proche vue jusque là. Cette variable est initialisée avec la valeur spéciale None.
Il faut noter que la fonction plus_proche dépend d'une pré-condition : elle ne peut fonctionner correctement que s'il existe au moins une ville non visitée, et renvoie None sinon.
Aucun test spécifique n'est fait car il est certain que l'utilisation de plus_proche par voyageur respectera toujours cette condition. En effet, chacun des n-1 tours de boucle marque exactement une des n villes comme visité et il en restera donc toujours au moins une qui ne soit pas encore marquée.
Ecrire et tester le code.
Mettre le résultat ici.
La solution donnée par i'algorithme glouton n'est pas nécessairement optimale. Peut-on néanmoins s'attendre à un certain niveau de qualité?
Si oui, ce niveau de qualité attendu est-il garanti, c'est-à-dire respecte même dans le pire des scénarios?
Ou bien est-il seulement hautement probable, c'est-à-dire généralement respecté mais avec des exceptions?
Les réponses à ces questions dépendent fortement du problème considéré.
Pour notre problème du voyageur, ii a été démontré que lorsque Ie nombre de villes devient grand, le rapport entre la. solution gloutonne et la solution optimale est dans le pire des cas proportionnel au logarithme du nombre de villes.
Dans certains cas la stratégie gloutonne donne toujours une solution optimale.
Considérons le problème d'un commerçant devant rendre de la monnaie à l'un de ses clients. Il souhaite le faire en utilisant le moins de pièces et de billets possibles.
On suppose que l'on manipule les coupures et pièces habituelles des euros (oublions les centimes) et que le commerçant dispose d'une réserve suffisamment importante de chaque espèce.
Si la somme qui doit être rendue est 9, les différentes combinaisons possibles sont les suivantes, qui utilisent entre 3 et 9 pièces.
| Combinaison | Pieces |
| 9 x 1€ | 9 |
| 7x1€ + 1x2€ | 8 |
| 5x1€ + 2x2€ | 7 |
| 3x1€+ 3x2€ | 6 |
| 1x1€ + 4x2€ | 5 |
| 4x1€ + 1x5€ | 5 |
| 2x1€ + 1x2€ + 1x5€ | 4 |
| 2x2€ + 1x5€ | 2 |
Une seule combinaison, que votre boulanger connait bien, permet d'atteindre la somme de 9 euros avec seulement trois éléments : 2 pieces de deux euros plus 1 billet de cinq euros.
Pour aborder le problème de rendu de monnaie avec une stratégie gloutonne, on va donc sélectionner les pièces et billets à rendre un à un, et faire décroitre progressivement la somme restant à rendre.
Chaque choix doit être celui qui parait être le meilleur au vu de la situation présente, c'est-à-dire de la somme restant à rendre. Pour limiter le nombre de devises rendues, on choisit de faire décroitre cette somme aussi vite que possible, c'est-à-dire de sélectionner à chaque fois la plus grande valeur disponible qui ne soit pas strictement supérieure à la somme à rendre.
Ainsi, dans notre exemple précédent, pour atteindre la somme de 9 on sélectionne d'abord un billet de 5 euros. Il reste alors 4 euros à rendre et on choisit une pièce de 2 euros.
Enfin, les 2 euros restant après cette étape sont atteints avec une unique pièce. On obtient alors la combinaison 2x2€+1x5€ dont on a vu qu'elle était optimale.
Le programme ci-dessous définit une fonction Python calculant le nombre de pièces ou billets qui doivent être utilises pour une somme à rendre donnée, en utilisant la stratégie gloutonne. Jusqu'à ce que la somme totale ait été rendue, cette fonction considère tour à tour les différentes coupures de la plus grosse à la plus petite, identifiées par un indice i dans le tableau euros.
euros = [1, 2, 5, 10, 20, 50, 100, 200]
def monnaie(s):
\"\"\"combien de pieces faut-il pour
obtenir la somme\"\"\"
i = len(euros) - 1
p = 0
while s > 0:
if s >= euros[i] :
s -= euros[i]
p += 1
else:
i -= 1
return p
print(\"nb pièce(s)\",monnaie(9))
Tant que la somme à rendre est supérieure à la coupure courante, on choisit de l'utiliser. Des que la somme à rendre devient inférieure à la valeur de la coupure en euros, on poursuit avec la coupure immédiatement inférieure.
On remarque que, la somme à rendre ne faisant que décroitre, une coupure écartée à cette étape ne sera effectivement plus jamais utile.
D'autres expériences permettent d'observer que cet algorithme glouton fournit toujours une réponse optimale. C'est quelque chose qui peut même être démontre.
Mettre les résultats ici.
. Les euros forment ce qu'on appelle un systèrne canonique, c'est-à-dire un système pour lequel l'algorithme glouton donne un rendu optimal.
Pour démontrer cela„ on peut. commencer par analyser quelques combinaisons de pièces pouvant on non apparaitre dans un rendu optimal.
•\t.Les pieces de 1 euro et les billets de 5, 10, 50 et 100 euros ne peuvent chactm etre utilises qu'une seule fois dans un rendu optimal. En eFfet, un rendu qui utiliserait deux pieces de 1 euro pent etre ameliore en remplaca.nt ces deux pieces par line, unique piece de 2 cures. De mettle pour 5/10, 10/20, 50/100 et 100/200.
•\tLes pieces de 2 cures et, les billets de 20 euros ne peuvent chacun etre utilises que deux fois dans un rendu optimal. En effet, un rendu qui utiliserait trois pieces de 2 cures pent etre ameliore en remplaca.nt ces trois pieces par line piece de 1 ewe et 1.111 billet de 5 euros. Dc meme pour 20/10/50.
•\tUn rendu optimal ne pent. contenir a la fois deux pieces de 2 cures et. lute piece de 1 euros (ou deux billets de 20 et. un de 10). En effet, un rendu avec c.:ette combinaison pent etre ameliore en utilisant è. la. place un billet de 5 cures (ou 50:).
On en deduit que, da.ns un rendu optimal, la somme totale des pieces et billet de 100 cures ou mains ne pent depa.sser 199 cures (avec la combinaison 2 x 2+1 x 5+2.x 20+1 x 50+1 x.1.00). Si la somme é. rendre est, superieure a 200 cures, le rendu optimal contient done necessairement tin billet de 200 cures, que l'algorithme glouton a. alors raison de choisir. On pent. poursuivre le raisonnement avec les coupures de 50 euros 01.1 moins (maximum 99) pour valider le choix d'un billet de 1.00, et ainsi dc suite pour valider l'integralite du systeme,.
Rendu de monnaie glouton dans d'autres systemes monetaires
Avec les euros, l'algorithme de rendu de monnaie glouton donne toujours la reponse optimale. Cependant ii n'en est pas toujours de meme dans tout systeme monetaire.
Considerons comme premier contre-exemple un systeme dans lequel les coupures out les valetas 1, 6 et 10. On souhaite rendre la somme 12. L'algorithme glouton selectionne d'abord la coupure 10, puis deux fois la coupure 1 pour un total de trois coupures. Ii etait cependant possible de faire mieux avec deux fois 6. Dans cc cas, l'algorithme glouton a donne une solution de rendu de monnaie correcte, mais pas optimale.
On peut construire un deuxieme contre-exemple plus grave avec le systerne dont les coupures out les valeurs 2 et 3, en tentant de rendre la somme 4. L'algorithme glouton selectionne alors en premier la coupure 3, apres quoi ii ne reste plus que 1 a rendre, cc que l'on ne sait pas faire avec les coupures disponibles. Et pourtant, une solution pour rendre 4 existait, il suffisait de selectionner deux fois 2! Dans cc cas, l'algorithme glouton echoue atrouver une solution de rendu alors qu'il en existait une.
On ne connait pas de critère simple caractérisant les systèmes canoniques. On salt en revanche qu'il suffit de tester l'algorithme pour chaque valeur inférieure à la somme des deux plus grandes pièces d'un système donné pour savoir si ce dernier est canonique.
Ainsi, la démonstration de canonicité des euros pourrait être remplacée par une vérification de l'optimalité de tous les rendus gloutons pour les sommes allant de 1 à 299 euros, vérification que l'on peut faire manuellement ou confiée à un programme.
Le processus est cependant susceptible d'être assez couteux, puisqu'il nécessite de faire une recherche exacte du rendu optimal pour toutes ces valeurs.
Problème du sac à dos.
Arsène L. à devant lui un ensemble d'objets de valeurs et de poids variés. II dispose d'un sac à dos dans lequel il ne peut prendre qu'une partie des objets, en essayant de maximiser la valeur totale emportée.
Cependant, il ne pourra emporter le sac que si le poids total ne dépasse pas 10 kilogrammes. Dans chacune des situations suivantes, indiquer les différentes combinaisons qui peuvent être formées et les valeurs correspondantes.
| Objet | Poids (kg) | Prix (€) | Objet | Poids (kg) | Prix (€) | |
| A | 8 | 4800 | A | 6 | 4800 | |
| B | 5 | 4000 | B | 5 | 3500 | |
| C | 4 | 3000 | C | 4 | 3000 | |
| D | 1 | 500 | D | 1 | 500 |
Algorithmes gloutons pour le problème du sac à dos. Arsene L. ne voulant pas arriyer en retard à son rendez-vous avec la comtesse C. Il va devoir choisir très rapidement les objets a emporter.
Appliquer chacune des trois stratégies gloutonnes suivantes aux situations de l'exercice précédent.
1. Choisir les objets par ordre de valeur décroissante parmi ceux qui ne dépassent pas la capacité restante.
2. Choisir les objets par ordre de poids croissant.
3. Choisir les objets par ordre de rapport valeur/poids décroissant parmi ceux qui ne depassent pas la capacité restante.
","title":"Exercice"},{"edit":" "}],[{"text":"Problème du sac à dos :
Pour chacune des stratégies gloutonnes de l'exercice précédent, trouver des situations dans lesquelles la valeur emportée est aussi éloignée que possible de la valeur optimale (Cas le plus défavorable).\tSolution page 466 0
Bin packing. Arsene L. à une nouvelle strategie. Ii enyerra aujourd'hui plusieurs complices avec l'objectif de tout emporter sans se soucier de la valeur de chaque objet, mais toujours dans la limite de 10 kilogrammes chacun. II faut cette fois essayer de repartir les objets parmi les personnes presentes.
1. Supposons qu'Arsene ait envoye trois personnes, et qu'il y a parmi les objets a emporter : un objet de lkg, deux objets de 2kg, deux objets de 3kg, deux objets de 4kg, un objet de 5kg et un objet de 6kg. Trouver une maniere de repartir les objets.
2. Combien de personnes faut-il pour recuperer un objet de 3kg, un objet de 5kg et deux objets de 6kg ?
4. kg €
A 7 9100
Exercice 162 Bin packing : strategic gloutonne. Une strategie gloutonne consiste a considerer les objets dans l'ordre, et pour chacun decider d'une personne a qui le confier. Pour cela, les personnes ont elles-memes un ordre, et on confie l'objet a la premiere ayant encore la capacite de le prendre. Si personne ne peut prendre l'objet on dira que la strategie a echoue.
Appliquer cette strategic a la situation de l'exercice 161 avec les deux ordres suivants pour les objets.
1.\t[6,\t3,\t4,\t2,\t4,\t3,\t1,\t5, 2]
2.\t[6,\t3,\t4,\t2,\t3,\t4, \t1,\t5, 2]
Exercice 163 Bin packing : programmation. On veut ecrire un programme qui, etant dorm& un tableau tab donnant les poids de chaque objet et un nombre n de conteneurs de capacite c, chercher a repartir l'ensemble des objets dans les conteneurs. Ecrire un programme qui indique s'il a reussi a repartir tous les objets en utilisant la premiere strategie proposee a
Exercice 164 Supposons avoir une liste d'activites, chacune associee a un creneau horaire defini par une heure de debut et une heure de fin. Deux activites sont compatibles si leurs creneaux horaires ne se recouvrent pas. On souhaite selectionner un nombre maximal d'activites toutes compatibles entre elles.
1. On se donne des activites avec les creneaux suivants : 8h-13h, 12h-17h, 9h-11h, 14h-16h, 11h-12h. Combien de ces activites peuvent-elles etre conciliees sur une seule journee ?
2. On propose une strategie gloutonne pour selectionner des activites en commencant par le debut de la journee : choisir l'activite dont l'heure de fin arrive le plus tot (parmi les activites dont l'heure de debut est bien posterieure aux creneaux des activites déjà choisies). Appliquer cette strategie a la situation precedente.
Remarque : cette strategie gloutonne donne toujours un nombre d'activites
optimal.\t
Exercice 165 On reprend le probleme de l'exercice precedent et on suppose avoir n activites numerotees de 0 a n - 1, et deux tableaux debut et fin de taille n tels que debut [i] et fin [i] contiennent respectivement l'heure de debut et l'heure de fin de l'activite numero i.
1. Ecrire une fonction prochaine (debut , fin, h) qui selectionne, parmi les activites dont l'heure de debut n'est pas anterieure a h, une s'arretant le plus tot. On demandera A la fonction de renvoyer None
1,1'17- 9 911,1711 ,TZ11-19911 0(11,11,9n1-11A9
2. En deduire une fonction selection(debut , fin) qui, en supposant que toutes les heures sont positives, selectionne autant d'activites que possible en suivant la strategie gloutonne. On demandera a la fonction d'afficher les numeros des activites selectionnees.