Skip to content

Séquence 6

L'objectif de la séquence est de travailler sur la construction et l'utilisation d'algorithmes gloutons. On poura lire le chapitre 16 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

On considère la straté de rendu de monnaie consistant à rendre la plus forte valeur possible en premier. Cet algorithme est optimal pour

  1. Le système de pièces {1,2,5,10} (système européen)
  2. Le système de pèces {1,3,4,10}

réponses (éléments)

  1. Vrai mais est complèxe à démontrer
  2. Faux par exemple le rendu sur 9 avec la stratégie gloutonne donne \(9=4+3+1+1\) soit un rendu de \(4\) pièces alors que l'on peur rendre \(3\) pièces avec \(9=3+3+3\)

Question 2

On considère le problème de coloriage de graphe non orienté ayant \(n\) noeud, c'est à dire colorer chacun des noeuds du graphe de manière à ce que tous noeuds voisins soient de couleur différente et en utilisant un minimum de couleurs. (les couleurs sont numérotées)

  1. Prendre les sommets dans un ordre quelconque et attribuer à chaque sommet la plus petite couleur non utilisée par ses voisins déjà coloriés. Cet algorithme est-il glouton ? La stratégie fournit-elle une solution optimale ?
  2. Prendre les sommets par degré décroissant et attribuer à chaque sommet la plus petite couleur non utilisée par ses voisins déjà coloriés. Cet algorithme est-il glouton ? La stratégie fournit-elle une solution optimale ?
  3. Commencer avec un nombre de couleurs égal à \(k=0\), tant que l'on ne trouve pas de coloriage incrémenter \(k\) énumérer les coloriages à \(k\) couleurs (un coloriage est un tableau de taille \(n\) dont la valeur de chaque case est la couleur du noeud). Cet algorithme est-il glouton ? La stratégie fournit-elle une solution optimale ?

réponses (éléments)

  1. Cet algorithme est glouton, il ne remet pas en cause les choix précédents. La stratégie n'est pas optimale, en effet si on prend une ligne de 4 noeuds, et que l'on choisit la même couleur pour les extrémités on aura besoin de 3 couleurs pour colorer le graphe alors que 2 suffisent.
  2. Cet algorithme est glouton, il ne remet pas en cause les choix précédents. La stratégie n'est pas optimale. En effet si on prend un anneau de 6 noeuds (tous les noeuds ont le même degré 2) et que l'on choisit la même couleur pour deux noeuds opposés sur l'anneau, on se ramène au cas précédent. On aura besoin de 3 couleurs pour colorer le graphe alors que 2 suffisent.
  3. Cet algorithme d'énumération n'est pas glouton, il ne construit pas de solution partielle qui ne sera pas remise en cause. Par contre il construit une solution optimale.

Question 3

Dans un jeu vidéo, on a \(n\) cibles disposées sur une ligne, aux positions \(x_1\leq x_2\leq \cdots \leq x_n\). Le joueur doit placer des bombes pour atteindre toutes les cibles. Une bombe a une portée de \(0.5\) autour de l'emplacement où elle est posée.

Différentes stratégies gloutonnes sont envisagées:

  1. On détermine la place de la bombe faisant le plus de dégats (touchant le plus de cibles) et on recommence en ignorant les cibles déjà atteinte.
  2. On place une bombe à \(x_1 + 0.5\) on élimine les cibles touchées et on recommence avec les cibles restantes.

Les stratégies ci-dessus produisent-elles des solutions optimales ?

réponses (éléments)

  1. Non La stratégie est gloutonne mais pas optimale. En effet si on a les 6 cibles en position \(0\), \(0.8\), \(1\), \(1.2\), \(1.3\), \(2.2\), l'algorithme va choisir un premier intervalle couvrant les 4 cibles du milieu et sera contraint de choisir 2 intervalles pour couvrir les extrémités, soit 3 intervalles alors que 2 suffisent.
  2. Oui La stratégie est optimale, la preuve s'effectue comme dans le cours.

Question 4

Le preuve d'un algorithme glouton produisant une solution optimale repose sur un invariant d'itération.

Lors de l'implémentation peut-on transformer cet invariant en un assert permettant de vérifier la correction de l'algorithme en cours d'exécution ?

réponses (éléments)

Non (dans le cas général) l'invariant il existe une solution optimale dont les éléments choisis en sont une partie entraine que pour le vérifier il faudrait avoir une solution optimale, ce qui n'est pas le cas car l'algorithme proposé doit la construire.