Toutes les lignes directes, à la main — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 5)

Toutes les lignes directes, à la main

Chemins de valeur optimale · niveau 2

Énoncé

Cinq villes ; le coût direct $d (i, j)$ , pour $i < j$ , est donné par :

$d (i, j)$	$j = 0$	$1$	$2$	$3$	$4$
$i = 0$	–	8	20	35	60
$i = 1$	–	–	10	15	45
$i = 2$	–	–	–	12	40
$i = 3$	–	–	–	–	15

Calculer à la main les tableaux $M$ et $A = ar g M$ , en écrivant chaque minimum.
Donner un trajet de coût minimum de $0$ à $4$ .
Combien d'additions le calcul demande-t-il pour $n$ villes ?

Corrigé

Base $m (0) = 0$ . Puis

$m (1) = m (0) + 8 = 8$ , $a (1) = 0$ ;
$m (2) = min {0 + 20, 8 + 10} = 18$ , $a (2) = 1$ ;
$m (3) = min {0 + 35, 8 + 15, 18 + 12} = 23$ , $a (3) = 1$ ;
$m (4) = min {0 + 60, 8 + 45, 18 + 40, 23 + 15} = 38$ , $a (4) = 3$ .

$M = [0, 8, 18, 23, 38]$ , $A = [- 1, 0, 1, 1, 3]$ .

$a (4) = 3$ , $a (3) = 1$ , $a (1) = 0$ : trajet $0 \to 1 \to 3 \to 4$ , de coût $8 + 15 + 15 = 38$ .


nom : M
valeurs : 0 8 18 23 38
colorier : 4
vert : 0 1 3
griser : 2
fleches : 0->1:8 1->3:15 3->4:15
legende : a(4) = 3, a(3) = 1, a(1) = 0 : trajet 0 → 1 → 3 → 4


M = [0, 8, 18, 23, 38]
A = [-1, 0, 1, 1, 3]
Coût minimum 38 : 0--(8)-->1--(15)-->3--(15)-->4

Le calcul de $m (j)$ fait $j$ additions : au total $1 + 2 + \dots + (n - 1) = n (n - 1) /2$ , soit $Θ (n^{2})$ ; ici $10$ .