Aller au contenu

DS 1 (MPSI tronc commun 2021-2022) — Poteaux télégraphiques, longueur minimale du fil

Devoir surveillé · MPSI (tronc commun) · 2021-2022 · partie III du DS 1

Cours : Programmation dynamique

Autres parties : I–II. Planter les poteaux

III. Minimiser la longueur du fil

L'objectif est maintenant de calculer un placement optimal des poteaux en terme de longueur totale du fil (le nombre de poteaux pouvant être maintenant arbitraire). Un tableau optL peut être calculé de proche en proche tel que optL[i] désigne la longueur minimale de fil à utiliser si l'on souhaitait relier le point \(P_{0}\) au point \(P_{i}\).

Question 9

Soit \(L_{i, j}\) la longueur du segment d'extrémités \(P_{i}\) et \(P_{j}\).

Montrer que le tableau optL vérifie : \(\operatorname{optL}[0]=0\), et pour \(1 \leqslant i \leqslant n\),

\[ \operatorname{optL}[i]=\min \left\{L_{i, j}+\operatorname{optL}[j], \text { où } 0 \leqslant j<i \text { et il est possible de tirer un fil de } P_{j} \text { à } P_{i}\right\} . \]

La case \(\operatorname{optL}[n]\) contient alors la longueur minimale de fil pour relier le bord gauche au bord droit.

Question 10

Écrire une fonction longueurMinimale\((n, \ell, \Delta)\) qui renvoie la longueur minimale de fil pour relier le bord gauche au bord droit, en respectant la législation.

Question 11

Modifier votre procédure longueurMinimale\((n, \ell, \Delta)\) pour qu'elle remplisse également un tableau precOptL de taille \(n+1\), où precOptL[i] contient l'indice du poteau précédant le poteau placé en \(P_{i}\) dans une solution de longueur minimale reliant \(P_{0}\) à \(P_{i}\). (Par convention, precOptL[0] = -1.)

Question 12

Écrire une procédure qui produit un placement des poteaux minimisant la longueur du fil de \(P_{0}\) à \(P_{n}\) à partir du tableau precOptL. La solution sera stockée dans un tableau global poteaux de la façon suivante :

  • la case poteaux[0] contiendra le nombre de poteaux utilisés ;
  • la case poteaux[t], pour \(t \geqslant 1\), contiendra l'indice \(i\) indiquant que le \(t\)-ème poteau, s'il existe, est planté en \(P_{i}\).

Quelle est la complexité de votre procédure en fonction de \(n\) ?