Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
178
Soient A i et B j res pec ti ve ment le ième pré fixe d’une séquence A et le jème
pré fixe d’une séquence B. Soit Z 5 z 1 c z k une plus longue sous séquence
com mune de ces deux pré fixes.
2. Mon trer que si a i 5 b j alors z k 5 a i et z 1 c z k21 est une plus longue
sous séquence com mune de A i 2 1 et de B j21 .
3. Mon trer que si a i 2 b j alors Ζ est une plus longue sous séquence com
mune de A i 2 1 et de B j , ou de A i et de B j21 .
Soit f(i, j) la lon gueur maximale d’une sous séquence com mune de A i et B j .
4. Jus ti fier l’équa tion de récur rence sui vante :
f 1 i, j2 5 c
0
f 1 i 2 1, j 2 12 1 1
max 1 f 1 i, j 2 i 2 , f 1 i 2 1, j2 2
si i 5 0 ou j 5 0,
si i, j . 0 et a i 5 b j ,
si i, j . 0 et a i 2 b j .
Afin de ne pas cal cu ler plu sieurs fois une même valeur f(i, j), ces valeurs
seront conser vées un tableau bi dimen sion nel T.
5. Expli quer com ment déduire direc te ment la valeur T(i, j) des valeurs
T(k, l), où : 0 < k < i et 0 < l < j.
6. Décrire un algo rithme de com plexité O(nm) pour cal cu ler toutes les
valeurs f(i, j) , i H 50, c , n6 et j H 50, c , n6 .
7. Appli quer cet algo rithme aux deux séquences A 5 parité et B 5 arrêt.
La lon gueur d’une plus longue sous séquence com mune étant cal cu lée,
une plus longue sous séquence com mune peut être obte nue à par tir de cette
valeur et du tableau T.
8. Don ner le prin cipe d’un algo rithme de com plexité O1 m 1 n 2 pour cal
cu ler une plus longue sous séquence com mune de A et B.
**4.3 D’un pro blème ancien à l’éta ge ment des fusées
Une bête de somme, consom mant 0,5 kg de nour ri ture par kilo mètre par couru et
pou vant tran spor ter une charge de 100 kg au maxi mum, se trouve en un dépôt qui
contient 500 kg de nour ri ture.
1. De quelle dis tance maximale cette bête peut elle s’écarter de son point
de départ en uti li sant com plè te ment la réserve ? (1
er
cas).
2. Quelle quan tité maximale de nour ri ture pourrait elle appor ter à une dis
tance de 100 km de son point ini tial ? (2
e
cas).
ii chE Mins oPTi Maux
*4.4 algo rithme de ForD : cas d’une minimi sa tion
On donne le graphe ci- dessous et l’on demande d’appli quer à la recherche du che min
de valeur mini male, l’algo rithme de Ford, entre A et F.
178
Soient A i et B j res pec ti ve ment le ième pré fixe d’une séquence A et le jème
pré fixe d’une séquence B. Soit Z 5 z 1 c z k une plus longue sous séquence
com mune de ces deux pré fixes.
2. Mon trer que si a i 5 b j alors z k 5 a i et z 1 c z k21 est une plus longue
sous séquence com mune de A i 2 1 et de B j21 .
3. Mon trer que si a i 2 b j alors Ζ est une plus longue sous séquence com
mune de A i 2 1 et de B j , ou de A i et de B j21 .
Soit f(i, j) la lon gueur maximale d’une sous séquence com mune de A i et B j .
4. Jus ti fier l’équa tion de récur rence sui vante :
f 1 i, j2 5 c
0
f 1 i 2 1, j 2 12 1 1
max 1 f 1 i, j 2 i 2 , f 1 i 2 1, j2 2
si i 5 0 ou j 5 0,
si i, j . 0 et a i 5 b j ,
si i, j . 0 et a i 2 b j .
Afin de ne pas cal cu ler plu sieurs fois une même valeur f(i, j), ces valeurs
seront conser vées un tableau bi dimen sion nel T.
5. Expli quer com ment déduire direc te ment la valeur T(i, j) des valeurs
T(k, l), où : 0 < k < i et 0 < l < j.
6. Décrire un algo rithme de com plexité O(nm) pour cal cu ler toutes les
valeurs f(i, j) , i H 50, c , n6 et j H 50, c , n6 .
7. Appli quer cet algo rithme aux deux séquences A 5 parité et B 5 arrêt.
La lon gueur d’une plus longue sous séquence com mune étant cal cu lée,
une plus longue sous séquence com mune peut être obte nue à par tir de cette
valeur et du tableau T.
8. Don ner le prin cipe d’un algo rithme de com plexité O1 m 1 n 2 pour cal
cu ler une plus longue sous séquence com mune de A et B.
**4.3 D’un pro blème ancien à l’éta ge ment des fusées
Une bête de somme, consom mant 0,5 kg de nour ri ture par kilo mètre par couru et
pou vant tran spor ter une charge de 100 kg au maxi mum, se trouve en un dépôt qui
contient 500 kg de nour ri ture.
1. De quelle dis tance maximale cette bête peut elle s’écarter de son point
de départ en uti li sant com plè te ment la réserve ? (1
er
cas).
2. Quelle quan tité maximale de nour ri ture pourrait elle appor ter à une dis
tance de 100 km de son point ini tial ? (2
e
cas).
ii chE Mins oPTi Maux
*4.4 algo rithme de ForD : cas d’une minimi sa tion
On donne le graphe ci- dessous et l’on demande d’appli quer à la recherche du che min
de valeur mini male, l’algo rithme de Ford, entre A et F.