TD d’algorithmique numéro 3 : programmation dynamique

Natacha Portier et Yves Robert semaine du 11 au 15 octobre 1999

Question 1 ⋆ location de skis ⋆

Un groupe de n touristes veut louer des skis dans un magasin de location. La boutique dispose de m paires (il y en a suffisemment). Idéalement chacun devrait avoir une paire de ski de même taille que lui. En pratique on cherche un algorithme pour minimiser la somme des valeurs absolues des différences (c’est la distance 1).

Question 1.1

Montrer que la fonction qui à la taille d’une personne associe la taille de ses skis doit être une fonction croissante.

En déduire le cas n=m et la complexité dans ce cas.

Question 1.2

On suppose les skieurs et les skis classés par taille croissante. Soit A[i, j] le minimum de la fonction à minimiser si on considère les i premiers touristes et les j premières paires de ski, avec j ≥ i + 1.

Donner une relation de récurrence pour A, en déduire un algorithme et sa complexité en m et n.

Question 1.3

Montrer que lorsque n^{2} = o(m), et si on suppose les skis déjà classés par ordre croissant, on peut avoir une meilleure complexité en restreignant l’ensemble des skis à considérer.

Question 2 ⋆ triangulation de polygones ⋆

On considère des polygones convexes du plan. Une triangulation d’un polygone est un ensemble de cordes qui ne se coupent pas à l’intérieur du polygone et qui le divisent en triangles.

Question 2.1

Montrer que toute triangulation est maximale (toute nouvelle corde intersecterait une corde existante) et qu’une triangulation d’un polygone à n côtés a (n − 3) cordes et (n − 2) triangles.

Question 2.2

Le problème est celui de la triangulation optimale de polygones. On part d’un polygone convexe P = ⟨v_{0}, ..., v_{n−1}⟩ et d’une fonction de pondération w définie sur les triangles formés par les côtés et les cordes de P, par exemple le périmètre. Le problème est de trouver une triangulation qui minimise la somme des poids des triangles de la triangulation.

On pose v_{0} = v_{n}. On définit t[i, j] pour 1 ≤ i < j ≤ n comme la pondération d’une triangulation optimale du polygone ⟨v_{i−1}, ..., v_{j}⟩, avec t[i, i] = 0.

Définir t récursivement, en déduire l’algorithme et sa complexité.

Remarque : Si la fonction de poids est quelconque, combien faut-il de données pour la connaitre sur tout triangle du polygone? Comparez avec la complexité obtenue.

Question 2.3

Appliquer l’algorithme si le poids d’un triangle est égal à son aire.

Question 3 ⋆ jeu de construction ⋆

On veut construire une tour la plus haute possible à partir de briques de base. On a n types de briques, et un nombre illimité de briques de chaque type. Chaque brique de type i est un parallélépipède de taille (x_{i}, y_{i}, z_{i}) et peut être orientée dans tous les sens, deux dimensions formant la base et la troisième dimension formant la hauteur.

Dans la construction de la tour une brique ne peut être placée au dessus d’une autre que si les deux dimensions de la base de la brique du dessus sont strictement inférieures aux dimensions de la base de la brique du dessous.

Proposer un algorithme efficace pour construire une tour de hauteur maximale.