Nous étudierons cette semaine une série de problèmes pouvant être résolus en employant des approches de type vorace (aussi appelée gloutonne ou greedy). Informellement, cette classe d’approches consiste à résoudre un problème en construisant une solution progressivement étape par étape, sans jamais revenir en arrière, à l’aide d’un critère local d’optimalité.
Les problèmes suivants sont triés par ordre croissant de difficulté.
“Minimum Scalar Product” — Trouvez une façon de permuter les coordonnées de deux vecteurs pour minimiser leur produit scalaire.
“Birds on a Wire” — Un ensemble d’oiseaux se tiennent sur un câble. Combien d’autres oiseaux peuvent venir les rejoindre sans que deux d’entre eux ne soient trop proches l’un de l’autre?
“Virus Replication” — Étant donnée une séquence d’ADN avant et après une infection, déterminez la plus courte séquence qui a dû y être insérée par un virus.
“Distributing Ballot Boxes” — Déterminez une façon de distribuer des urnes entre des bureaux de vote de sorte à minimiser le nombre maximum de personnes devant voter dans la même urne.
“Messages From Outer Space” — À partir d’une chaîne \(S\), trouvez le plus grand ensemble de mots du dictionnaire qui apparaissent sans chevauchement dans \(S\).
“Watering Grass” — Choisissez le moins d’arroseurs possible qui permettent de couvrir entièrement une bande d’herbe.