Arbre de coût minimum à la main

• On applique $m(i,i)=0$ et $m(i,j)=S(i,j)+{\min }_{i\le k<j}\{m(i,k)+m(k+1,j)\}$ par tailles croissantes ($a$ désigne l'argument, première valeur de $k$ réalisant le minimum).

• $t=1$ : $m(0,1)=2$, $m(1,2)=1$, $m(2,3)=3$, $m(3,4)=4$.
• $t=2$ : $m(0,2)=3+\min (0+1,2+0)=4$ ($a=0$) ; $m(1,3)=4+\min (0+3,1+0)=5$ ($a=2$) ; $m(2,4)=7+\min (0+4,3+0)=10$ ($a=3$).
• $t=3$ : $m(0,3)=6+\min (0+5,2+3,4+0)=10$ ($a=2$) ; $m(1,4)=8+\min (0+10,1+4,5+0)=13$ ($a=2$).
• $t=4$ : $m(0,4)=10+\min (0+13,2+10,4+4,10+0)=18$ ($a=2$).

Le programme range les coûts au-dessus de la diagonale et les arguments en dessous ($M[j][i]=a(i,j)$) :

M[4] = [2, 2, 3, 3, 0]
M[3] = [2, 2, 2, 0, 4]
M[2] = [0, 1, 0, 3, 10]
M[1] = [0, 0, 1, 5, 13]
M[0] = [0, 2, 4, 10, 18]

• Racine $a(0,4)=2$ ; à gauche, l'arbre sur $[0:2]$ a pour racine $a(0,2)=0$, avec $1$ à sa droite ; à droite, l'arbre sur $[3:4]$ est la feuille $3$.

Son coût : $1\times 3+2\times (2+4)+3\times 1=18$.

nom : F
valeurs : 2 1 3 4
colorier : 2
zone : 0..1 à gauche
zone : 3..3 à droite
legende : racine a(0,4) = 2, de fréquence 3

• L'abr glouton insère $3,2,0,1$ (fréquences décroissantes) : c'est $(3(2(0()(1()()))())())$, de coût $4+2\times 3+3\times 2+4\times 1=20$. L'abr de hauteur minimum $(2(1(0()())())(3()()))$ coûte $3+2\times (1+4)+3\times 2=19$.

coût min : (2 (0 () (1 () ())) (3 () ())) coût 18
glouton  : (3 (2 (0 () (1 () ())) ()) ()) coût 20
haut.min : (2 (1 (0 () ()) ()) (3 () ())) coût 19

Aucune des deux constructions simples n'est optimale.