Upload
etienne-gautier
View
110
Download
4
Embed Size (px)
Citation preview
Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1123 novembre 200623 novembre 2006
Cours d’AlgorithmiqueCours d’Algorithmique
Programmation dynamique :Programmation dynamique :
Problème du sac à dos.Problème du sac à dos.
Négociant en sardines au port de Marseille.Négociant en sardines au port de Marseille.
Problème de la plus longue sous-chaîne commune.Problème de la plus longue sous-chaîne commune.
Problème du plus court chemin.Problème du plus court chemin.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 22
• Trier et chercher, recherche textuelleTrier et chercher, recherche textuelle• Listes et arbresListes et arbres• Le back-trackLe back-track• Arbres équilibrésArbres équilibrés• Récursivité et induction sur la structureRécursivité et induction sur la structure• Divide and conquerDivide and conquer• Minimax, alpha-betaMinimax, alpha-beta• DérécursionDérécursion• Divers problèmes particuliers.Divers problèmes particuliers.• Logique de HoareLogique de Hoare• Programmation dynamiqueProgrammation dynamique• Complexité et calculabilitéComplexité et calculabilité
Les grandes lignes du coursLes grandes lignes du cours
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 33
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
En français : Programmation dynamique !En français : Programmation dynamique !
Abréviation classique : DPAbréviation classique : DP
Notion introduite par Richard Bellman en 1957.Notion introduite par Richard Bellman en 1957.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 44
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
En français : Programmation dynamique !En français : Programmation dynamique !
Abréviation classique : DPAbréviation classique : DP
Notion introduite par Richard Bellman en 1957.Notion introduite par Richard Bellman en 1957.
Principe :Principe :
Nous explicitons le TEMPSNous explicitons le TEMPS
qui sera linéaire, bi-dimensionnel, . . .qui sera linéaire, bi-dimensionnel, . . .
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 55
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Introduction à la problématique.Introduction à la problématique.
• Considérons à nouveau la fonction Considérons à nouveau la fonction Fibonacci :Fibonacci :
fib ( n ) = fib ( n ) =
n si n = 0 ou n = 1,n si n = 0 ou n = 1,
fib ( n-2 ) + fib ( n-1 ) sinon.fib ( n-2 ) + fib ( n-1 ) sinon.{{
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 66
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Introduction à la problématique.Introduction à la problématique.
• Considérons à nouveau la fonction Fibonacci :Considérons à nouveau la fonction Fibonacci :
• Le programme récursif est exponentiel en temps !Le programme récursif est exponentiel en temps !
C’est dû auxC’est dû auxrépétitionsrépétitionsde calculs !de calculs !
fib ( n ) = fib ( n ) =
n si n = 0 ou n = 1,n si n = 0 ou n = 1,
fib ( n-2 ) + fib ( n-1 ) sinon.fib ( n-2 ) + fib ( n-1 ) sinon.{{
0 1
22
1
33
44
0 1
22
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 77
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 88
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{Nous utilisons au temps « t » ce que nous avonsNous utilisons au temps « t » ce que nous avons
pu calculer aux temps « t – 1 » et « t – 2 ».pu calculer aux temps « t – 1 » et « t – 2 ».
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 99
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 1100
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1010
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 11 1100
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1111
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 11 11 2200
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1212
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 11 11 22 3300
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1313
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 11 11 22 33 5500
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1414
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 11 11 22 33 55 8800
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1515
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Principe de la programmation dynamique :Principe de la programmation dynamique :
– Dites à quel moment vous ferez quel calcul ?Dites à quel moment vous ferez quel calcul ?
• Respectons le temps :Respectons le temps :
• Nous avons une complexité en temps linéaire ! ! !Nous avons une complexité en temps linéaire ! ! !
fib ( fib ( tt ) = ) =
tt si si tt = 0 ou = 0 ou tt = 1, = 1,
fib ( fib ( t-2t-2 ) + fib ( ) + fib ( t-1t-1 ) sinon. ) sinon.{{tt
00 11 22 33 44 55 66
fibfib 11 11 22 33 55 8800
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1616
L AL AF O N C T I O NF O N C T I O N
D ED ET E M P ST E M P S
L E S L E S D E P E N D A N C E D E P E N D A N C E
SS
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1717
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Quelle fonction de temps ?Quelle fonction de temps ?
– C’est quoi ?C’est quoi ?
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1818
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Quelle fonction de temps ?Quelle fonction de temps ?
– C’est quoi ?C’est quoi ?
– Une fonction qui dit, en termes de l’état du Une fonction qui dit, en termes de l’état du problème, à quel moment il va être résolu !problème, à quel moment il va être résolu !
– Exemples : Exemples : fib ( t ) au temps « t »,fib ( t ) au temps « t », prog( x , y ) au temps « 2 *x + y -prog( x , y ) au temps « 2 *x + y -
5 ».5 ».
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 1919
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Quelle fonction de temps ?Quelle fonction de temps ?
– C’est quoi ?C’est quoi ?
– Une fonction qui dit, en termes de l’état du Une fonction qui dit, en termes de l’état du problème, à quel moment il va être résolu !problème, à quel moment il va être résolu !
– Exemples : Exemples : fib ( t ) au temps « t »,fib ( t ) au temps « t », prog( x , y ) au temps « 2 *x + y -5 ».prog( x , y ) au temps « 2 *x + y -5 ».
• N’importe laquelle pour peu queN’importe laquelle pour peu que
– nous ne répétions pas les calculsnous ne répétions pas les calculs
Ce n’est pas interdit, mais fortement déconseillé !Ce n’est pas interdit, mais fortement déconseillé !
– et que la fonction soit compatible avec les et que la fonction soit compatible avec les dépendances. dépendances.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2020
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Dépendances entre problèmes :Dépendances entre problèmes :
– On parle aussi de « flot de données ou de On parle aussi de « flot de données ou de contrôle ».contrôle ».
– Le calcul « B » dépend du calcul « A » s’il faut Le calcul « B » dépend du calcul « A » s’il faut queque
« A » soit calculé avant « B » !« A » soit calculé avant « B » !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2121
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Dépendances entre problèmes :Dépendances entre problèmes :
– On parle aussi de « flot de données ou de On parle aussi de « flot de données ou de contrôle ».contrôle ».
– Le calcul « B » dépend du calcul « A » s’il faut Le calcul « B » dépend du calcul « A » s’il faut queque
« A » soit calculé avant « B » !« A » soit calculé avant « B » !
– Soit, parce que « A » a besoin de données produites Soit, parce que « A » a besoin de données produites par « B » --- flot de données !par « B » --- flot de données !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2222
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Dépendances entre problèmes :Dépendances entre problèmes :
– On parle aussi de « flot de données ou de On parle aussi de « flot de données ou de contrôle ».contrôle ».
– Le calcul « B » dépend du calcul « A » s’il faut Le calcul « B » dépend du calcul « A » s’il faut queque
« A » soit calculé avant « B » !« A » soit calculé avant « B » !
– Soit, parce que « A » a besoin de données produites Soit, parce que « A » a besoin de données produites par « B » --- flot de données !par « B » --- flot de données !
– Soit, parce qu’il faut respecter un ordre (par Soit, parce qu’il faut respecter un ordre (par exempleexemple
imprimer « A » avant « B »).imprimer « A » avant « B »).
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2323
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Dépendances entre problèmes :Dépendances entre problèmes :
– On parle aussi de « flot de données ou de On parle aussi de « flot de données ou de contrôle ».contrôle ».
– Le calcul « B » dépend du calcul « A » s’il faut Le calcul « B » dépend du calcul « A » s’il faut queque
« A » soit calculé avant « B » !« A » soit calculé avant « B » !
– Soit, parce que « A » a besoin de données produites Soit, parce que « A » a besoin de données produites par « B » --- flot de données !par « B » --- flot de données !
– Soit, parce qu’il faut respecter un ordre (par Soit, parce qu’il faut respecter un ordre (par exempleexemple
imprimer « A » avant « B »).imprimer « A » avant « B »).
– Soit, parce que « A » conditionne « B » ( si A alors B ) Soit, parce que « A » conditionne « B » ( si A alors B ) --- flot de contrôle ! --- flot de contrôle !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2424
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Dépendances entre problèmes :Dépendances entre problèmes :
– On parle aussi de « flot de données ou de On parle aussi de « flot de données ou de contrôle».contrôle».
– Le calcul « B » dépend du calcul « A » s’il faut Le calcul « B » dépend du calcul « A » s’il faut queque
« A » soit calculé avant « B » !« A » soit calculé avant « B » !
– Soit, parce que « A » a besoin de données produites Soit, parce que « A » a besoin de données produites par « B » --- flot de données !par « B » --- flot de données !
– Soit, parce qu’il faut respecter un ordre (par Soit, parce qu’il faut respecter un ordre (par exempleexemple
imprimer « A » avant « B »).imprimer « A » avant « B »).
– Soit, parce que « A » conditionne « B » ( si A alors B ) Soit, parce que « A » conditionne « B » ( si A alors B ) --- flot de contrôle ! --- flot de contrôle !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2525
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• En fait, les dépendances comportent une notion En fait, les dépendances comportent une notion de temporalité sous la forme de :de temporalité sous la forme de :
AVANT --- APRESAVANT --- APRES D’ABORD --- ENSUITED’ABORD --- ENSUITE
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2626
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• En fait, les dépendances comportent une notion En fait, les dépendances comportent une notion de temporalité sous la forme de :de temporalité sous la forme de :
AVANT --- APRESAVANT --- APRES D’ABORD --- ENSUITED’ABORD --- ENSUITE
• La fonction de temps « f » dit de manière plus La fonction de temps « f » dit de manière plus précise :précise :
QUANDQUAND
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2727
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• En fait, les dépendances comportent une notion En fait, les dépendances comportent une notion de temporalité sous la forme de :de temporalité sous la forme de :
AVANT --- APRESAVANT --- APRES D’ABORD --- ENSUITED’ABORD --- ENSUITE
• La fonction de temps « f » dit de manière plus La fonction de temps « f » dit de manière plus précise :précise :
QUANDQUAND
• La contrainte sur « f » dit que :La contrainte sur « f » dit que :
– dès que « A » doit être avant « B » pour des dès que « A » doit être avant « B » pour des raisons de dépendances, alorsraisons de dépendances, alors
f ( A ) < f ( B )f ( A ) < f ( B )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2828
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• En fait, les dépendances comportent une notion En fait, les dépendances comportent une notion de temporalité sous la forme de :de temporalité sous la forme de :
AVANT --- APRESAVANT --- APRES D’ABORD --- ENSUITED’ABORD --- ENSUITE
• La fonction de temps « f » dit de manière plus La fonction de temps « f » dit de manière plus précise :précise :
QUANDQUAND
• La contrainte sur « f » dit que :La contrainte sur « f » dit que :
– dès que « A » doit être avant « B » pour des dès que « A » doit être avant « B » pour des raisons de dépendances, alorsraisons de dépendances, alors
f ( A ) < f ( B )f ( A ) < f ( B )« f » est alors dite « compatible avec les dépendances ».« f » est alors dite « compatible avec les dépendances ».
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 2929
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• L’arbre de dépendances de Fibonacci :L’arbre de dépendances de Fibonacci :
0
1
22
1
33
44
0
1
22
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3030
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• L’arbre de dépendances de Fibonacci :L’arbre de dépendances de Fibonacci :
• Sa projection sur un axe de temps :Sa projection sur un axe de temps :
0
1
22
1
33
44
0
1
22
tt
00
11
22
33
44
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3131
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• L’arbre de dépendances de Fibonacci :L’arbre de dépendances de Fibonacci :
• Sa projection sur un axe de temps :Sa projection sur un axe de temps :
0
1
22
1
33
44
0
1
22
tt
00
11
22
33
44
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3232
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• L’arbre de dépendances de Fibonacci :L’arbre de dépendances de Fibonacci :
• Sa projection sur un axe de temps :Sa projection sur un axe de temps :
0
1
22
1
33
44
0
1
22
tt
00
11
22
33
44Compatibilité !Compatibilité !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3333
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
• Parfois, la programmation dynamique estParfois, la programmation dynamique est
• la transformation d’un problème de back-track la transformation d’un problème de back-track ou divide-and-conquerou divide-and-conquer
• avec un comportement temporel anarchiqueavec un comportement temporel anarchique
• en un problème qui réalise les calculs une et une en un problème qui réalise les calculs une et une seule fois, et lorsqu’il le faut !seule fois, et lorsqu’il le faut !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3434
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
Il y a une théorie derrière !Il y a une théorie derrière !
• Cadre général : les modèles de décision multi-Cadre général : les modèles de décision multi-étages.étages.
• Si certaines propriétés sont vérifiées, on peut Si certaines propriétés sont vérifiées, on peut transformer tout problème de ce modèle en un transformer tout problème de ce modèle en un programme DP.programme DP.
• Trop long et compliqué dans le contexte du cours.Trop long et compliqué dans le contexte du cours.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3535
U n e x e m p l e c o m p l U n e x e m p l e c o m p l e t :e t :
S A C A D O S ! ! !S A C A D O S ! ! !
Dynamic ProgrammingDynamic Programming----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3636
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Problème du « sac à dos » !Problème du « sac à dos » !
• Ingrédients :Ingrédients :
– 1 sac à dos de capacité « C » (par exemple en kilos),1 sac à dos de capacité « C » (par exemple en kilos),
– n objets de O , … , O n objets de O , … , O
• de poids strictement positifs respectifs pde poids strictement positifs respectifs p
• et de bénéfices strictement positifs respectifs et de bénéfices strictement positifs respectifs b .b .
nn11
ii
ii
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3737
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Problème du « sac à dos » !Problème du « sac à dos » !
• Ingrédients :Ingrédients :
– 1 sac à dos de capacité « C » (par exemple en kilos),1 sac à dos de capacité « C » (par exemple en kilos),
– n objets de O , … , O n objets de O , … , O
• de poids strictement positifs respectifs pde poids strictement positifs respectifs p
• et de bénéfices strictement positifs respectifs et de bénéfices strictement positifs respectifs b .b .
• Recette :Recette :
– Trouvez, sans dépasser la capacité, l’ensemble Trouvez, sans dépasser la capacité, l’ensemble d’objets qui maximise le bénéfice.d’objets qui maximise le bénéfice.
nn11
ii
ii
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3838
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Trouvez l’ensemble « I » inclus dans { 1 , … , n } tel Trouvez l’ensemble « I » inclus dans { 1 , … , n } tel que :que :
• P ( I ) = P ( I ) = p p CCi i IIii
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 3939
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Trouvez l’ensemble « I » inclus dans { 1 , … , n } Trouvez l’ensemble « I » inclus dans { 1 , … , n } tel que :tel que :
• P ( I ) = P ( I ) = p p CC
• B ( I ) = B ( I ) = b b max ( B ( J ) )max ( B ( J ) )
i i IIii
J { 1 , … , n }J { 1 , … , n }et P ( J ) et P ( J ) CC
vviii i II
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4040
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Trouvez l’ensemble « I » inclus dans { 1 , … , n } tel Trouvez l’ensemble « I » inclus dans { 1 , … , n } tel que :que :
• P ( I ) = P ( I ) = p p CC
• B ( I ) = B ( I ) = b b max ( B ( J ) )max ( B ( J ) )
• A priori, il faut se comparer à un grand nombre A priori, il faut se comparer à un grand nombre d’autres ensembles candidats à être optimal.d’autres ensembles candidats à être optimal.
i i IIii
J { 1 , … , n }J { 1 , … , n }et P ( J ) et P ( J ) CC
vviii i II
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4141
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Correct, mais …Correct, mais …
{int max_benefice = 0 ;
pour k allant de 1 à n faire
pour chaque ensemble I, de taille k et sous-ensemble
de { 1 , ... , n } faire
si ( P ( I ) <= C )
max_benefice = max ( B ( I ) , max_benefice ) ;
}
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4242
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Correct, mais …Correct, mais …
{int max_benefice = 0 ;
pour k allant de 1 à n faire
pour chaque ensemble I, de taille k et sous-ensemble
de { 1 , ... , n } faire
si ( P ( I ) <= C )
max_benefice = max ( B ( I ) , max_benefice ) ;
}
Toutes les tailles possiblesToutes les tailles possiblespour les sous-ensembles.pour les sous-ensembles.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4343
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Correct, mais …Correct, mais …
{int max_benefice = 0 ;
pour k allant de 1 à n faire
pour chaque ensemble I, de taille k et sous-ensemble
de { 1 , ... , n } faire
si ( P ( I ) <= C )
max_benefice = max ( B ( I ) , max_benefice ) ;
}
Toutes les tailles possiblesToutes les tailles possiblespour les sous-ensembles.pour les sous-ensembles.
Tous les sous-ensemblesTous les sous-ensemblesde cette taille …de cette taille …
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4444
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Correct, mais …Correct, mais …
{int max_benefice = 0 ;
pour k allant de 1 à n faire
pour chaque ensemble I, de taille k et sous-ensemble
de { 1 , ... , n } faire
si ( P ( I ) <= C )
max_benefice = max ( B ( I ) , max_benefice ) ;
}
Toutes les tailles possiblesToutes les tailles possiblespour les sous-ensembles.pour les sous-ensembles.
Tous les sous-ensemblesTous les sous-ensemblesde cette taille …de cette taille …
Retenez le bénéfice s’il est meilleur et queRetenez le bénéfice s’il est meilleur et quela contrainte sur la capacité est respectée.la contrainte sur la capacité est respectée.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4545
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Correct, mais …Correct, mais …
{int max_benefice = 0 ;
pour k allant de 1 à n faire
pour chaque ensemble I, de taille k et sous-ensemble
de { 1 , ... , n } faire
si ( P ( I ) <= C )
max_benefice = max ( B ( I ) , max_benefice ) ;
}
Toutes les tailles possiblesToutes les tailles possiblespour les sous-ensembles.pour les sous-ensembles.
Tous les sous-ensemblesTous les sous-ensemblesde cette taille …de cette taille …
Retenez le bénéfice s’il est meilleur et queRetenez le bénéfice s’il est meilleur et quela contrainte sur la capacité est respectée.la contrainte sur la capacité est respectée.
Seule ombre au tableau :Seule ombre au tableau :
le nombre des ensembles considérés est en le nombre des ensembles considérés est en 2^n ). 2^n ).
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4646
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ?Solution Divide and Conquer ? ? ?
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4747
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! ! !Mais oui ! ! !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4848
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 4949
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
– Soit « i » l’indice de l’objet que nous allons Soit « i » l’indice de l’objet que nous allons considérer,considérer,
– soit « R » la capacité résiduelle,soit « R » la capacité résiduelle,
– soit « B » le bénéfice des objets pris jusque-là.soit « B » le bénéfice des objets pris jusque-là.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5050
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
– Soit « i » l’indice de l’objet que nous allons Soit « i » l’indice de l’objet que nous allons considérer,considérer,
– soit « R » la capacité résiduelle,soit « R » la capacité résiduelle,
– soit « B » le bénéfice des objets pris jusque-là.soit « B » le bénéfice des objets pris jusque-là.I = 1 , R = C , B = 0I = 1 , R = C , B = 0Etat initial.Etat initial.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5151
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
– Soit « i » l’indice de l’objet que nous allons Soit « i » l’indice de l’objet que nous allons considérer,considérer,
– soit « R » la capacité résiduelle,soit « R » la capacité résiduelle,
– soit « B » le bénéfice des objets pris jusque-là.soit « B » le bénéfice des objets pris jusque-là.I = 1 , R = C , B = 0I = 1 , R = C , B = 0Etat initial.Etat initial.
O est pris !O est pris !11
I = 2 , R = C - p , B = bI = 2 , R = C - p , B = b1111
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5252
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
– Soit « i » l’indice de l’objet que nous allons Soit « i » l’indice de l’objet que nous allons considérer,considérer,
– soit « R » la capacité résiduelle,soit « R » la capacité résiduelle,
– soit « B » le bénéfice des objets pris jusque-là.soit « B » le bénéfice des objets pris jusque-là.I = 1 , R = C , B = 0I = 1 , R = C , B = 0Etat initial.Etat initial.
O est pris !O est pris !11
I = 2 , R = C - p , B = bI = 2 , R = C - p , B = b1111
O n’est pas pris !O n’est pas pris !11
I = 2 , R = C , B = 0I = 2 , R = C , B = 0
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5353
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
– Soit « i » l’indice de l’objet que nous allons Soit « i » l’indice de l’objet que nous allons considérer,considérer,
– soit « R » la capacité résiduelle,soit « R » la capacité résiduelle,
– soit « B » le bénéfice des objets pris jusque-là.soit « B » le bénéfice des objets pris jusque-là.I = 1 , R = C , B = 0I = 1 , R = C , B = 0Etat initial.Etat initial.
O est pris !O est pris !11
I = 2 , R = C - p , B = bI = 2 , R = C - p , B = b1111
O n’est pas pris !O n’est pas pris !11
I = 2 , R = C , B = 0I = 2 , R = C , B = 0
Optimum local : B_avecOptimum local : B_avec Optimum local : B_sansOptimum local : B_sans
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5454
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Solution Divide and Conquer ? ? ? Solution Divide and Conquer ? ? ? Mais oui ! Mais oui ! ! !! !
• Considérez les ensembles qui contiennent Considérez les ensembles qui contiennent l’objet O et ceux qui ne le contiennent pas ! l’objet O et ceux qui ne le contiennent pas !
– Soit « i » l’indice de l’objet que nous allons Soit « i » l’indice de l’objet que nous allons considérer,considérer,
– soit « R » la capacité résiduelle,soit « R » la capacité résiduelle,
– soit « B » le bénéfice des objets pris jusque-là.soit « B » le bénéfice des objets pris jusque-là.I = 1 , R = C , B = 0I = 1 , R = C , B = 0Etat initial.Etat initial.
O est pris !O est pris !11
I = 2 , R = C - p , B = bI = 2 , R = C - p , B = b1111
O n’est pas pris !O n’est pas pris !11
I = 2 , R = C , B = 0I = 2 , R = C , B = 0
Optimum local : B_avecOptimum local : B_avec Optimum local : B_sansOptimum local : B_sans
MAXMAX
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5555
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
int D&C_sac ( int objet , int residuelle , int benefice )
{if ( objet > n )
return( benefice ) ;
else
{int memoire ;
memoire = D&C_sac ( objet + 1 , residuelle , benefice ) ;
if ( p[ objet ] > residuelle )
return( memoire ) ;
else
return( max( D&C_sac( objet + 1 ,
residuelle – p[ objet ] ,
benefice + b[ objet ] ) ,
memoire ) ) ; } }
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5656
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
int D&C_sac ( int objet , int residuelle , int benefice )
{if ( objet > n )
return( benefice ) ;
else
{int memoire ;
memoire = D&C_sac ( objet + 1 , residuelle , benefice ) ;
if ( p[ objet ] > residuelle )
return( memoire ) ;
else
return( max( D&C_sac( objet + 1 ,
residuelle – p[ objet ] ,
benefice + b[ objet ] ) ,
memoire ) ) ; } }
Cas final !Cas final !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5757
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
int D&C_sac ( int objet , int residuelle , int benefice )
{if ( objet > n )
return( benefice ) ;
else
{int memoire ;
memoire = D&C_sac ( objet + 1 , residuelle , benefice ) ;
if ( p[ objet ] > residuelle )
return( memoire ) ;
else
return( max( D&C_sac( objet + 1 ,
residuelle – p[ objet ] ,
benefice + b[ objet ] ) ,
memoire ) ) ; } }
Cas final !Cas final !
Nous explorons toujours le casNous explorons toujours le casoù l’objet ne sera pas pris !où l’objet ne sera pas pris !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5858
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
int D&C_sac ( int objet , int residuelle , int benefice )
{if ( objet > n )
return( benefice ) ;
else
{int memoire ;
memoire = D&C_sac ( objet + 1 , residuelle , benefice ) ;
if ( p[ objet ] > residuelle )
return( memoire ) ;
else
return( max( D&C_sac( objet + 1 ,
residuelle – p[ objet ] ,
benefice + b[ objet ] ) ,
memoire ) ) ; } }
Cas final !Cas final !
Nous explorons toujours le casNous explorons toujours le casoù l’objet ne sera pas pris !où l’objet ne sera pas pris !
Il se peut que cela suffise !Il se peut que cela suffise !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 5959
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
int D&C_sac ( int objet , int residuelle , int benefice )
{if ( objet > n )
return( benefice ) ;
else
{int memoire ;
memoire = D&C_sac ( objet + 1 , residuelle , benefice ) ;
if ( p[ objet ] > residuelle )
return( memoire ) ;
else
return( max( D&C_sac( objet + 1 ,
residuelle – p[ objet ] ,
benefice + b[ objet ] ) ,
memoire ) ) ; } }
Cas final !Cas final !
Nous explorons toujours le casNous explorons toujours le casoù l’objet ne sera pas pris !où l’objet ne sera pas pris !
Le cas le plus courantLe cas le plus courantest celui qui exploreest celui qui exploreles deux alternatives !les deux alternatives !
Il se peut que cela suffise !Il se peut que cela suffise !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6060
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
int D&C_sac ( int objet , int residuelle , int benefice )
{if ( objet > n )
return( benefice ) ;
else
{int memoire ;
memoire = D&C_sac ( objet + 1 , residuelle , benefice ) ;
if ( p[ objet ] > residuelle )
return( memoire ) ;
else
return( max( D&C_sac( objet + 1 ,
residuelle – p[ objet ] ,
benefice + b[ objet ] ) ,
memoire ) ) ; } }
Cas final !Cas final !
Nous explorons toujours le casNous explorons toujours le casoù l’objet ne sera pas pris !où l’objet ne sera pas pris !
Le cas le plus courantLe cas le plus courantest celui qui exploreest celui qui exploreles deux alternatives !les deux alternatives !
La capacité résiduelleLa capacité résiduellediminue !diminue !
Le bénéfice augmente !Le bénéfice augmente !
Il se peut que cela suffise !Il se peut que cela suffise !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6161
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Malheureusement, nous répétons des calculs !Malheureusement, nous répétons des calculs !
• Considérons p[ 1 ] = 1 , p[ 2 ] = 2 , p[ 3 ] = 3 Considérons p[ 1 ] = 1 , p[ 2 ] = 2 , p[ 3 ] = 3 et et
b[ 1 ] = 2 , b[ 2 ] = 4 , b[ 3 ] = b[ 1 ] = 2 , b[ 2 ] = 4 , b[ 3 ] = 6 . 6 .
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6262
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Malheureusement, nous répétons des calculs !Malheureusement, nous répétons des calculs !
• Considérons p[ 1 ] = Considérons p[ 1 ] = 11 , p[ 2 ] = , p[ 2 ] = 22 , p[ 3 ] = 3 , p[ 3 ] = 3 et et
b[ 1 ] = b[ 1 ] = 22 , b[ 2 ] = , b[ 2 ] = 44 , b[ 3 ] = , b[ 3 ] = 6 . 6 .
• Si nous sélectionnons 1 et 2 mais pas 3 , Si nous sélectionnons 1 et 2 mais pas 3 , l’appel suivant seral’appel suivant sera
D&C_sac ( 4 , C – 3 , 6 ).D&C_sac ( 4 , C – 3 , 6 ).
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6363
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Malheureusement, nous répétons des calculs !Malheureusement, nous répétons des calculs !
• Considérons p[ 1 ] = 1 , p[ 2 ] = 2 , p[ 3 ] = Considérons p[ 1 ] = 1 , p[ 2 ] = 2 , p[ 3 ] = 33 etet
b[ 1 ] = 2 , b[ 2 ] = 4 , b[ 3 ] = b[ 1 ] = 2 , b[ 2 ] = 4 , b[ 3 ] = 66 . .
• Si nous sélectionnons 1 et 2 mais pas 3 , Si nous sélectionnons 1 et 2 mais pas 3 , l’appel suivant seral’appel suivant sera
D&C_sac ( 4 , C – 3 , 6 ).D&C_sac ( 4 , C – 3 , 6 ).
• Si nous ne sélectionnons ni 1 , ni 2 , mais 3 , Si nous ne sélectionnons ni 1 , ni 2 , mais 3 , l’appel suivant seral’appel suivant sera
D&C_sac ( 4 , C – 3 , 6 ).D&C_sac ( 4 , C – 3 , 6 ).
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6464
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O . tt
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6565
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O .
• Nous avons donc déjà considéré O , … , O .Nous avons donc déjà considéré O , … , O .
tt
11 t-1t-1
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6666
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O .
• Nous avons donc déjà considéré O , … , O .Nous avons donc déjà considéré O , … , O .
• Avec une capacité résiduelle « R », la meilleure solution Avec une capacité résiduelle « R », la meilleure solution sur les « t » premiers objets est obtenue par :sur les « t » premiers objets est obtenue par :
Opt ( t , R ) = Opt ( t , R ) =
tt
11 t-1t-1
{{
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6767
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O .
• Nous avons donc déjà considéré O , … , O .Nous avons donc déjà considéré O , … , O .
• Avec une capacité résiduelle « R », la meilleure solution Avec une capacité résiduelle « R », la meilleure solution sur les « t » premiers objets est obtenue par :sur les « t » premiers objets est obtenue par :
Opt ( t – 1 , R ) si p > R !Opt ( t – 1 , R ) si p > R !Opt ( t , R ) = Opt ( t , R ) =
tt
11 t-1t-1
{{ tt
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6868
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O .
• Nous avons donc déjà considéré O , … , O .Nous avons donc déjà considéré O , … , O .
• Avec une capacité résiduelle « R », la meilleure solution Avec une capacité résiduelle « R », la meilleure solution sur les « t » premiers objets est obtenue par :sur les « t » premiers objets est obtenue par :
Opt ( t – 1 , R ) si p > R !Opt ( t – 1 , R ) si p > R !Opt ( t , R ) = Opt ( t , R ) = max ( Opt ( t – 1 , R ) , b + Opt ( t - 1 , R – max ( Opt ( t – 1 , R ) , b + Opt ( t - 1 , R –
p ) )p ) )
tt
11 t-1t-1
{{ tt
tt tt
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 6969
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O .
• Nous avons donc déjà considéré O , … , O .Nous avons donc déjà considéré O , … , O .
• Avec une capacité résiduelle « R », la meilleure solution Avec une capacité résiduelle « R », la meilleure solution sur les « t » premiers objets est obtenue par :sur les « t » premiers objets est obtenue par :
Opt ( t – 1 , R ) si p > R !Opt ( t – 1 , R ) si p > R !Opt ( t , R ) = Opt ( t , R ) = max ( max ( Opt ( t – 1 , R )Opt ( t – 1 , R ) , , b + Opt ( t - 1 , R – b + Opt ( t - 1 , R –
p )p ) ) )
tt
11 t-1t-1
{{ tt
tt tt
O n’est pas pris !O n’est pas pris !ttO est pris !O est pris !tt
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7070
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
• Organisons notre emploi du temps !Organisons notre emploi du temps !
– Au temps « t », nous nous occupons de O . Au temps « t », nous nous occupons de O .
• Nous avons donc déjà considéré O , … , O .Nous avons donc déjà considéré O , … , O .
• Avec une capacité résiduelle « R », la meilleure solution Avec une capacité résiduelle « R », la meilleure solution sur les « t » premiers objets est obtenue par :sur les « t » premiers objets est obtenue par :
Opt ( Opt ( t – 1t – 1 , R ) si p > R ! , R ) si p > R !Opt ( Opt ( tt , R ) = , R ) = max ( Opt ( max ( Opt ( t – 1t – 1 , R ) , b + Opt ( , R ) , b + Opt ( t - 1t - 1 , R – , R –
p ) )p ) )
tt
11 t-1t-1
{{ tt
tt tt
Nous respectons l’écoulement du temps !Nous respectons l’écoulement du temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7171
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
CC
nn
Opt ( t , R )Opt ( t , R )
t-1t-1 tt
Opt ( t-1 , R )Opt ( t-1 , R )
Si l’objet estSi l’objet esttrop lourd !trop lourd !
RR
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7272
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
CC
nn
Opt ( t , R )Opt ( t , R )
t-1t-1 tt
Opt ( t-1 , R )Opt ( t-1 , R )
Si l’objet estSi l’objet esttrop lourd !trop lourd !
RR
La fonction de tempsLa fonction de tempsest compatible avecest compatible avecles dépendances ! ! !les dépendances ! ! !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7373
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
CC
Opt ( t , R )Opt ( t , R )
RR
Opt ( t-1 , R )Opt ( t-1 , R )
Si l’objet n’estSi l’objet n’estpas trop lourd !pas trop lourd !
Opt ( t-1 , R – p[ t ] )Opt ( t-1 , R – p[ t ] )
R – p[ t ]R – p[ t ]
nnt-1t-1 tt
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7474
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
CC
Opt ( t , R )Opt ( t , R )
RR
Opt ( t-1 , R )Opt ( t-1 , R )
Si l’objet n’estSi l’objet n’estpas trop lourd !pas trop lourd !
Opt ( t-1 , R – p[ t ] )Opt ( t-1 , R – p[ t ] )
R – p[ t ]R – p[ t ]
nnt-1t-1 tt
La fonction de tempsLa fonction de tempsest compatible avecest compatible avecles dépendances ! ! !les dépendances ! ! !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7575
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
CC
Opt ( t , R )Opt ( t , R )
RR
Opt ( t-1 , R )Opt ( t-1 , R )
Si l’objet n’estSi l’objet n’estpas trop lourd !pas trop lourd !
Opt ( t-1 , R – p[ t ] )Opt ( t-1 , R – p[ t ] )
R – p[ t ]R – p[ t ]
nnt-1t-1 tt
La fonction de tempsLa fonction de tempsest compatible avecest compatible avecles dépendances ! ! !les dépendances ! ! !
00
00
00
……
……
Sans objets, il n’ySans objets, il n’ya aucun bénéfice.a aucun bénéfice.
00
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7676
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
{for ( R = 0 ; R <= C ; R++ )
Opt[ 0 , R ] = 0 ;
for ( t = 1 ; t <= n ; t++ )
for ( R = 0 ; R <= C ; R++ )
if ( p[ t ] > R )
Opt[ t , R ] = Opt[ t-1 , R ] ;
else
Opt[ t , R ] = max( b[ t ] + Opt[ t-1 , R–p[ t ] ,
Opt[ t-1 , R ] ) ;
}
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7777
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
{for ( R = 0 ; R <= C ; R++ )
Opt[ 0 , R ] = 0 ;
for ( t = 1 ; t <= n ; t++ )
for ( R = 0 ; R <= C ; R++ )
if ( p[ t ] > R )
Opt[ t , R ] = Opt[ t-1 , R ] ;
else
Opt[ t , R ] = max( b[ t ] + Opt[ t-1 , R–p[ t ] ,
Opt[ t-1 , R ] ) ;
}
Initialisation de laInitialisation de lapremière colonne à 0.première colonne à 0.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7878
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
{for ( R = 0 ; R <= C ; R++ )
Opt[ 0 , R ] = 0 ;
for ( t = 1 ; t <= n ; t++ )
for ( R = 0 ; R <= C ; R++ )
if ( p[ t ] > R )
Opt[ t , R ] = Opt[ t-1 , R ] ;
else
Opt[ t , R ] = max( b[ t ] + Opt[ t-1 , R–p[ t ] ,
Opt[ t-1 , R ] ) ;
}
Initialisation de laInitialisation de lapremière colonne à 0.première colonne à 0.
Colonne après colonne,Colonne après colonne,depuis la gauche vers la droitedepuis la gauche vers la droite
et de bas en haut …et de bas en haut …
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 7979
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
{for ( R = 0 ; R <= C ; R++ )
Opt[ 0 , R ] = 0 ;
for ( t = 1 ; t <= n ; t++ )
for ( R = 0 ; R <= C ; R++ )
for ( R = C ; R >= 0 ; R-- )
if ( p[ t ] > R )
Opt[ t , R ] = Opt[ t-1 , R ] ;
else
Opt[ t , R ] = max( b[ t ] + Opt[ t-1 , R–p[ t ] ,
Opt[ t-1 , R ] ) ;
}
Initialisation de laInitialisation de lapremière colonne à 0.première colonne à 0.
Colonne après colonne,Colonne après colonne,depuis la gauche vers la droitedepuis la gauche vers la droite
et de bas en haut …et de bas en haut …et de haut en bas, pourquoi pas ?et de haut en bas, pourquoi pas ?
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8080
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
{for ( R = 0 ; R <= C ; R++ )
Opt[ 0 , R ] = 0 ;
for ( t = 1 ; t <= n ; t++ )
for ( R = 0 ; R <= C ; R++ )
if ( p[ t ] > R )
Opt[ t , R ] = Opt[ t-1 , R ] ;
else
Opt[ t , R ] = max( b[ t ] + Opt[ t-1 , R–p[ t ] ,
Opt[ t-1 , R ] ) ;
}
Initialisation de laInitialisation de lapremière colonne à 0.première colonne à 0.
Colonne après colonne,Colonne après colonne,depuis la gauche vers la droitedepuis la gauche vers la droite
et de bas en haut …et de bas en haut …
… … ce qu’il faut !ce qu’il faut !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8181
Sac à dos --- KnapsackSac à dos --- Knapsack----------------------------------------------------------------------------------------------------------------------------------
{for ( R = 0 ; R <= C ; R++ )
Opt[ 0 , R ] = 0 ;
for ( t = 1 ; t <= n ; t++ )
for ( R = 0 ; R <= C ; R++ )
if ( p[ t ] > R )
Opt[ t , R ] = Opt[ t-1 , R ] ;
else
Opt[ t , R ] = max( b[ t ] + Opt[ t-1 , R–p[ t ] ,
Opt[ t-1 , R ] ) ;
}
Initialisation de laInitialisation de lapremière colonne à 0.première colonne à 0.
Colonne après colonne,Colonne après colonne,depuis la gauche vers la droitedepuis la gauche vers la droite
et de bas en haut …et de bas en haut …
… … ce qu’il faut !ce qu’il faut !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8282
U n e x e m p l e c o m p l U n e x e m p l e c o m p l e t :e t :
N E G O C I A N TN E G O C I A N TA UA U
P O R TP O R TD ED E
M A R S E I L L E ! ! !M A R S E I L L E ! ! !
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8383
• L’énoncé :L’énoncé :
– Vous êtes acheteur au port de Marseille,Vous êtes acheteur au port de Marseille,
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8484
• L’énoncé :L’énoncé :
– Vous êtes acheteur au port de Marseille,Vous êtes acheteur au port de Marseille,
– « n » bateaux vont arriver et vous connaissez « n » bateaux vont arriver et vous connaissez cette valeur,cette valeur,
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8585
• L’énoncé :L’énoncé :
– Vous êtes acheteur au port de Marseille,Vous êtes acheteur au port de Marseille,
– « n » bateaux vont arriver et vous connaissez « n » bateaux vont arriver et vous connaissez cette valeur,cette valeur,
– la qualité de la marchandise des différents la qualité de la marchandise des différents bateaux « Q( i ) » varie de 0 à 1000, de manière bateaux « Q( i ) » varie de 0 à 1000, de manière aléatoire uniforme, et vous savez la juger, aléatoire uniforme, et vous savez la juger,
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8686
• L’énoncé :L’énoncé :
– Vous êtes acheteur au port de Marseille,Vous êtes acheteur au port de Marseille,
– « n » bateaux vont arriver et vous connaissez « n » bateaux vont arriver et vous connaissez cette valeur,cette valeur,
– la qualité de la marchandise des différents la qualité de la marchandise des différents bateaux « Q( i ) » varie de 0 à 1000, de manière bateaux « Q( i ) » varie de 0 à 1000, de manière aléatoire uniforme, et vous savez la juger, aléatoire uniforme, et vous savez la juger,
– vous achetez une et une seule cargaison !vous achetez une et une seule cargaison !
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8787
• L’énoncé :L’énoncé :
– Vous êtes acheteur au port de Marseille,Vous êtes acheteur au port de Marseille,
– « n » bateaux vont arriver et vous connaissez « n » bateaux vont arriver et vous connaissez cette valeur,cette valeur,
– la qualité de la marchandise des différents la qualité de la marchandise des différents bateaux « Q( i ) » varie de 1 à 1000, de manière bateaux « Q( i ) » varie de 1 à 1000, de manière aléatoire uniforme, et vous savez la juger, aléatoire uniforme, et vous savez la juger,
– vous achetez une et une seule cargaison !vous achetez une et une seule cargaison !
• Laquelle ? Laquelle ?
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8888
• A l’arrivée du premier bateau :A l’arrivée du premier bateau :
– Vous achetez ?Vous achetez ?
– Vous attendez mieux ?Vous attendez mieux ?
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 8989
• A l’arrivée du premier bateau :A l’arrivée du premier bateau :
– Vous achetez ?Vous achetez ?
– Vous attendez mieux ?Vous attendez mieux ?
OUIOUIAchat du premier ? Achat du premier ? NONNON
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9090
• A l’arrivée du premier bateau :A l’arrivée du premier bateau :
– Vous achetez ?Vous achetez ?
– Vous attendez mieux ?Vous attendez mieux ?
OUIOUIAchat du premier ? OUIAchat du premier ? OUI NON – Achat du secondNON – Achat du second NONNON
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9191
• A l’arrivée du premier bateau :A l’arrivée du premier bateau :
– Vous achetez ?Vous achetez ?
– Vous attendez mieux ?Vous attendez mieux ?
OUIOUIAchat du premier ? OUIAchat du premier ? OUI NON – Achat du secondNON – Achat du second NONNON
• En fait, qu’attendez-vous ?En fait, qu’attendez-vous ?
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9292
• A l’arrivée du premier bateau :A l’arrivée du premier bateau :
– Vous achetez ?Vous achetez ?
– Vous attendez mieux ?Vous attendez mieux ?
OUIOUIAchat du premier ? OUIAchat du premier ? OUI NON – Achat du secondNON – Achat du second NONNON
• En fait, nous achetons si la qualité duEn fait, nous achetons si la qualité du bateau courant est meilleure que labateau courant est meilleure que la qualité moyenne espérée des bateauxqualité moyenne espérée des bateaux qui vont venir !qui vont venir !
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9393
• A l’arrivée du bateau « i » :A l’arrivée du bateau « i » :
– Nous achetons si Q( i ) est supérieure à E ( i+1 )Nous achetons si Q( i ) est supérieure à E ( i+1 )
– où E ( i+1 ) est la qualité moyenne des bateaux où E ( i+1 ) est la qualité moyenne des bateaux i+1 à ni+1 à n
– et nous en déduisons E( i ) !et nous en déduisons E( i ) !
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9494
• A l’arrivée du bateau « i » :A l’arrivée du bateau « i » :
– Nous achetons si Q( i ) est supérieure à E ( i+1 )Nous achetons si Q( i ) est supérieure à E ( i+1 )
– où E ( i+1 ) est la qualité moyenne des bateaux où E ( i+1 ) est la qualité moyenne des bateaux i+1 à ni+1 à n
– et nous en déduisons E( i ) !et nous en déduisons E( i ) !
• Donc,Donc,
– avec une probabilité de ( 1000 – E( i+1 ) ) / 1000avec une probabilité de ( 1000 – E( i+1 ) ) / 1000
– nous achetons le bateau « i » dont la qualité moyenne nous achetons le bateau « i » dont la qualité moyenne vaut ( 1000 + E( i+1 ) ) / 2 .vaut ( 1000 + E( i+1 ) ) / 2 .
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9595
• A l’arrivée du bateau « i » :A l’arrivée du bateau « i » :
– Nous achetons si Q( i ) est supérieure à E ( i+1 )Nous achetons si Q( i ) est supérieure à E ( i+1 )
– où E ( i+1 ) est la qualité moyenne des bateaux où E ( i+1 ) est la qualité moyenne des bateaux i+1 à ni+1 à n
– et nous en déduisons E( i ) !et nous en déduisons E( i ) !
• Donc,Donc,
– avec une probabilité de avec une probabilité de ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000
– nous achetons le bateau « i » dont la qualité moyenne nous achetons le bateau « i » dont la qualité moyenne vaut vaut ( 1000 + E( i+1 ) ) / 2( 1000 + E( i+1 ) ) / 2 . .
– E ( i ) = E ( i ) = ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000 * * ( 1000 + E( i+ 1 ) ) / 2( 1000 + E( i+ 1 ) ) / 2 + …+ …
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9696
• A l’arrivée du bateau « i » :A l’arrivée du bateau « i » :
– Nous achetons si Q( i ) est supérieure à E ( i+1 )Nous achetons si Q( i ) est supérieure à E ( i+1 )
– où E ( i+1 ) est la qualité moyenne des bateaux où E ( i+1 ) est la qualité moyenne des bateaux i+1 à ni+1 à n
– et nous en déduisons E( i ) !et nous en déduisons E( i ) !
• Donc,Donc,
– avec une probabilité de avec une probabilité de ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000
– nous achetons le bateau « i » dont la qualité moyenne nous achetons le bateau « i » dont la qualité moyenne vaut vaut ( 1000 + E( i+1 ) ) / 2( 1000 + E( i+1 ) ) / 2 . .
– E ( i ) = E ( i ) = ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000 * * ( 1000 + E( i+ 1 ) ) / 2( 1000 + E( i+ 1 ) ) / 2 + ( 1 - + ( 1 - ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000 ) * ) * E( i+1 )E( i+1 )
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9797
• A l’arrivée du bateau « i » :A l’arrivée du bateau « i » :
– Nous achetons si Q( i ) est supérieure à E ( i+1 )Nous achetons si Q( i ) est supérieure à E ( i+1 )
– où E ( i+1 ) est la qualité moyenne des bateaux i+1 où E ( i+1 ) est la qualité moyenne des bateaux i+1 à nà n
– et nous en déduisons E( i ) !et nous en déduisons E( i ) !
• Donc,Donc,
– avec une probabilité de avec une probabilité de ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000
– nous achetons le bateau « i » dont la qualité moyenne vaut nous achetons le bateau « i » dont la qualité moyenne vaut ( 1000 + E( i+1 ) ) / 2( 1000 + E( i+1 ) ) / 2 . .
– E ( i ) = E ( i ) = ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000 * * ( 1000 + E( i+ 1 ) ) / 2( 1000 + E( i+ 1 ) ) / 2 + ( 1 - + ( 1 - ( 1000 – E( i+1 ) ) / 1000( 1000 – E( i+1 ) ) / 1000 ) * ) * E( i+1 )E( i+1 )
= ( 1000^2 + E^2( i+1 ) ) / 2000= ( 1000^2 + E^2( i+1 ) ) / 2000
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9898
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 9999
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
• E( n-1 ) = ½ * 750 + ½ * 500 = 625E( n-1 ) = ½ * 750 + ½ * 500 = 625
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 100100
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
• E( n-1 ) = ½ * 750 + ½ * 500 = 625E( n-1 ) = ½ * 750 + ½ * 500 = 625
• E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2 + 625 / 1000 * 625 / 2+ 625 / 1000 * 625 / 2 = 695= 695
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 101101
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
• E( n-1 ) = ½ * 750 + ½ * 500 = 625E( n-1 ) = ½ * 750 + ½ * 500 = 625
• E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2 + 625 / 1000 * 625 / 2+ 625 / 1000 * 625 / 2 = 695= 695 n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-
1 n1 n
879 871 861 850 836 820 775 741 695 625 879 871 861 850 836 820 775 741 695 625 500 500
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
E( x )E( x )
xx
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 102102
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
• E( n-1 ) = ½ * 750 + ½ * 500 = 625E( n-1 ) = ½ * 750 + ½ * 500 = 625
• E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2 + 625 / 1000 * 625 / 2+ 625 / 1000 * 625 / 2 = 695= 695 n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-
1 n1 n
879 871 861 850 836 820 775 741 695 625 879 871 861 850 836 820 775 741 695 625 500 500
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
E( x )E( x )
xx
L’axe de temps !L’axe de temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 103103
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
• E( n-1 ) = ½ * 750 + ½ * 500 = 625E( n-1 ) = ½ * 750 + ½ * 500 = 625
• E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2 + 625 / 1000 * 625 / 2+ 625 / 1000 * 625 / 2 = 695= 695 n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-
1 n1 n
879 871 861 850 836 820 775 741 695 625 879 871 861 850 836 820 775 741 695 625 500 500
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
E( x )E( x )
xx
Pour tout bateau i , i < n : Nous achetons si Q( i ) >= E( i+1 ) !Pour tout bateau i , i < n : Nous achetons si Q( i ) >= E( i+1 ) !
L’axe de temps !L’axe de temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 104104
• Ce qui nous donne :Ce qui nous donne :
• E( n ) = 500E( n ) = 500
• E( n-1 ) = ½ * 750 + ½ * 500 = 625E( n-1 ) = ½ * 750 + ½ * 500 = 625
• E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2E( n-2 ) = ( 1000 – 625 ) / 1000 * ( 1000 + 625 ) / 2 + 625 / 1000 * 625 / 2+ 625 / 1000 * 625 / 2 = 695= 695 n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-n-10 n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-
1 n1 n
879 871 861 850 836 820 775 741 695 625 879 871 861 850 836 820 775 741 695 625 500 500
Marine marchandeMarine marchande----------------------------------------------------------------------------------------------------------------------------------
E( x )E( x )
xx
Pour tout bateau i , i < n : Nous achetons si Q( i ) >= E( i+1 ) !Pour tout bateau i , i < n : Nous achetons si Q( i ) >= E( i+1 ) !
L’axe de temps !L’axe de temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 105105
U n e x e m p l e c o m p l U n e x e m p l e c o m p l e t :e t :
L A P L U S L O N G U EL A P L U S L O N G U ES O U S – C H A I N ES O U S – C H A I N EC O M M U N E ! ! !C O M M U N E ! ! !
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 106106
En français : Plus longue sous-chaîne commune !En français : Plus longue sous-chaîne commune !
• On obtient une sous-chaîne en supprimant On obtient une sous-chaîne en supprimant des caractères d’une chaîne.des caractères d’une chaîne.
A B C D E F GA B C D E F G
B A C D D B E FB A C D D B E F
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 107107
En français : Plus longue sous-chaîne commune !En français : Plus longue sous-chaîne commune !
• On obtient une sous-chaîne en supprimant On obtient une sous-chaîne en supprimant des caractères d’une chaîne.des caractères d’une chaîne.
A B C D E F GA B C D E F G
B A C D D B E FB A C D D B E F
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
Une sous-chaîne : A BUne sous-chaîne : A B
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 108108
En français : Plus longue sous-chaîne commune !En français : Plus longue sous-chaîne commune !
• On obtient une sous-chaîne en supprimant On obtient une sous-chaîne en supprimant des caractères d’une chaîne.des caractères d’une chaîne.
A B C D E F GA B C D E F G
B A C D D B E FB A C D D B E F
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
Une sous-chaîne : A BUne sous-chaîne : A B
Une autre sous-chaîne : B D EUne autre sous-chaîne : B D E
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 109109
En français : Plus longue sous-chaîne commune !En français : Plus longue sous-chaîne commune !
• On obtient une sous-chaîne en supprimant On obtient une sous-chaîne en supprimant des caractères d’une chaîne.des caractères d’une chaîne.
A B C D E F GA B C D E F G
B A C D D B E FB A C D D B E F
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
Une sous-chaîne : A BUne sous-chaîne : A B
Une autre sous-chaîne : B D EUne autre sous-chaîne : B D E
La sous-chaîne la plus longue : A C D E FLa sous-chaîne la plus longue : A C D E F
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 110110
• LCSS ( u , v ) = LCSS ( u , v ) =
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
Nous allons définir LCSS de uNous allons définir LCSS de uet de v à partir de solutionset de v à partir de solutionsobtenues pour des chaînesobtenues pour des chaînesplus courtes !plus courtes !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 111111
, si u = , si u = ou v = ou v =
• LCSS ( u , v ) = LCSS ( u , v ) =
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 112112
, si u = , si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . a . LCSS ( u’ , v’ ) , si u = a . u’ etu’ et
v = a . v’ v = a . v’ , ,
• LCSS ( u , v ) = LCSS ( u , v ) =
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 113113
, si u = , si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . a . LCSS ( u’ , v’ ) , si u = a . u’ etu’ et
v = a . v’ v = a . v’ , ,
• LCSS ( u , v ) = LCSS ( u , v ) =
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
a . u’a . u’
a . v’a . v’
LCSSLCSS
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 114114
, si u = , si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . u’ eta . LCSS ( u’ , v’ ) , si u = a . u’ et v = a . v’ , v = a . v’ , • LCSS ( u , v ) = LCSS ( u , v ) =
maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )
si u = a . u’ , v = b . v’ et a <> b.si u = a . u’ , v = b . v’ et a <> b.
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 115115
, si u = , si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . u’ eta . LCSS ( u’ , v’ ) , si u = a . u’ et v = a . v’ , v = a . v’ , • LCSS ( u , v ) = LCSS ( u , v ) =
maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )
si u = a . u’ , v = b . v’ et a <> b.si u = a . u’ , v = b . v’ et a <> b.
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
a . u’a . u’
b . v’b . v’
LCSSLCSS
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 116116
, si u = , si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . u’ eta . LCSS ( u’ , v’ ) , si u = a . u’ et v = a . v’ , v = a . v’ , • LCSS ( u , v ) = LCSS ( u , v ) =
maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )
si u = a . u’ , v = b . v’ et a <> b.si u = a . u’ , v = b . v’ et a <> b.
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Soient a et b des lettres et u et v des séquences de lettres.Soient a et b des lettres et u et v des séquences de lettres.
a . u’a . u’
b . v’b . v’
LCSSLCSS
a . u’a . u’
b . v’b . v’ LCSSLCSS
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 117117
, si u = , si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . u’ eta . LCSS ( u’ , v’ ) , si u = a . u’ et v = a . v’ , v = a . v’ , • LCSS ( u , v ) = LCSS ( u , v ) =
maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )
si u = a . u’ , v = b . v’ et a <> b.si u = a . u’ , v = b . v’ et a <> b.
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Le programme récursif s’arrête, CAR :Le programme récursif s’arrête, CAR :
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 118118
, , si u = si u = ou v = ou v =
a . LCSS ( u’ , v’ ) , si u = a . u’ eta . LCSS ( u’ , v’ ) , si u = a . u’ et v = a . v’ , v = a . v’ , • LCSS ( u , v ) = LCSS ( u , v ) =
maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v ) )
si u = a . u’ , v = b . v’ et a <> b.si u = a . u’ , v = b . v’ et a <> b.
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Le programme récursif s’arrête, CAR :Le programme récursif s’arrête, CAR :
C’est fini dès que u ou v est réduite à la chaîne vide !C’est fini dès que u ou v est réduite à la chaîne vide !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 119119
, , si u = si u = ou v = ou v =
a . LCSS ( a . LCSS ( u’ , v’u’ , v’ ) , si u = a . u’ et ) , si u = a . u’ et v = a . v’ , v = a . v’ , • LCSS ( LCSS ( u , vu , v ) = ) =
maxstr ( LCSS ( maxstr ( LCSS ( u , v’u , v’ ) , LCSS ( ) , LCSS ( u’ , vu’ , v ) ) ) )
si u = a . u’ , v = b . v’ et a <> b.si u = a . u’ , v = b . v’ et a <> b.
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
{{Le programme récursif s’arrête, CAR :Le programme récursif s’arrête, CAR :
C’est fini dès que u ou v est réduite à la chaîne vide !C’est fini dès que u ou v est réduite à la chaîne vide !
A chaque appel récursif, l’une au moins des chaînes raccourcit !A chaque appel récursif, l’une au moins des chaînes raccourcit !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 120120
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 121121
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 122122
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )ww
a.wa.wLCSS ( a . u’ , a . v’ )LCSS ( a . u’ , a . v’ )
==a . LCSS ( u’ , v’ )a . LCSS ( u’ , v’ )
ww
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 123123
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
LCSS ( a . u’ , b . v’ )LCSS ( a . u’ , b . v’ )==
maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v) )maxstr ( LCSS ( u , v’ ) , LCSS ( u’ , v) )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 124124
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )La case jaune dépendLa case jaune dépend
de ses trois voisines dude ses trois voisines dusudsud, de l’, de l’ouestouest et du et du sud-ouestsud-ouest,,
suivant les cas de figure !suivant les cas de figure !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 125125
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 126126
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 127127
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
Projection !Projection !PremierPremier
axe de temps !axe de temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 128128
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Deuxième axe de temps !Deuxième axe de temps !
Les calculs sontLes calculs sontindépendants, carindépendants, carils sont portés parils sont portés parle premier axe ! ! !le premier axe ! ! !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 129129
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
L’ordre des calculs !L’ordre des calculs !
1.1. 3.3.
2.2.
4.4.
5.5.
6.6.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 130130
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
L’ordre des calculs !L’ordre des calculs !
1.1. 3.3.
2.2.
4.4.
5.5.
6.6.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 131131
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
L’ordre des calculs !L’ordre des calculs !
1.1. 3.3.
2.2.
4.4.
5.5.
6.6.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 132132
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 133133
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 134134
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 135135
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !Projection !Projection !
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 136136
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !Projection !Projection !
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 137137
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !Projection !Projection !
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 138138
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !Projection !Projection !
DeuxièmeDeuxième
PremierPremier
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 139139
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !Projection !Projection !
DeuxièmeDeuxième
PremierPremier
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 140140
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
LCSS est donc calculé pour les suffixes de u et v .LCSS est donc calculé pour les suffixes de u et v .
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
LCSS( ? , LCSS( ? , ) )
LCSS( LCSS( , ? ) , ? )
PremierPremieraxe de temps !axe de temps !
Projection !Projection !
Deuxième axe de temps !Deuxième axe de temps !Projection !Projection !
DeuxièmeDeuxième
PremierPremier
..
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 141141
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
PremierPremieraxe de temps !axe de temps !
Deuxième axe de temps !Deuxième axe de temps !
Temps multi-dimensionnel, ici bi-dimensionnel.Temps multi-dimensionnel, ici bi-dimensionnel.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 142142
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
Temps multi-dimensionnel, ici bi-dimensionnel.Temps multi-dimensionnel, ici bi-dimensionnel.
suffixe( u )suffixe( u )
suffixe( v )suffixe( v )
vv
uu
PremierPremieraxe de temps !axe de temps !
Deuxième axe de temps !Deuxième axe de temps !
Heure ( u , v )Heure ( u , v )
Heure ( u+1 , v+1 )Heure ( u+1 , v+1 )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 143143
{T[ , ? ] = ;
T[ ? , ] = ;
pour x suffixe de u , suivant de jusqua u
pour y suffixe de v , suivant de jusqua v
si ( tete( x ) == tete( y ) )
T[ x , y ] = tete( x ) . T[ reste( x ) ,
reste( y ) ] ;
sinon
T[ x , y ] = maxstr( T[ x , reste( y ) ] ,
T[ reste( x ) , y ] ) ;
}
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 144144
{T[ , ? ] = ;
T[ ? , ] = ;
pour x suffixe de u , suivant de jusqua u
pour y suffixe de v , suivant de jusqua v
si ( tete( x ) == tete( y ) )
T[ x , y ] = tete( x ) . T[ reste( x ) ,
reste( y ) ] ;
sinon
T[ x , y ] = maxstr( T[ x , reste( y ) ] ,
T[ reste( x ) , y ] ) ;
}
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
L’initialisation !L’initialisation !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 145145
{T[ , ? ] = ;
T[ ? , ] = ;
pour x suffixe de u , suivant de jusqua u
pour y suffixe de v , suivant de jusqua v
si ( tete( x ) == tete( y ) )
T[ x , y ] = tete( x ) . T[ reste( x ) ,
reste( y ) ] ;
sinon
T[ x , y ] = maxstr( T[ x , reste( y ) ] ,
T[ reste( x ) , y ] ) ;
}
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
L’initialisation !L’initialisation !
Colonne par colonne,Colonne par colonne,depuis le bas …depuis le bas …
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 146146
{T[ , ? ] = ;
T[ ? , ] = ;
pour x suffixe de u , suivant de jusqua u
pour y suffixe de v , suivant de jusqua v
si ( tete( x ) == tete( y ) )
T[ x , y ] = tete( x ) . T[ reste( x ) ,
reste( y ) ] ;
sinon
T[ x , y ] = maxstr( T[ x , reste( y ) ] ,
T[ reste( x ) , y ] ) ;
}
Longest Common Sub-StringLongest Common Sub-String----------------------------------------------------------------------------------------------------------------------------------
L’initialisation !L’initialisation !
… … ce qu’il faut !ce qu’il faut !
Colonne par colonne,Colonne par colonne,depuis le bas …depuis le bas …
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 147147
U n e x e m p l e c o m p l U n e x e m p l e c o m p l e t :e t :
L E C H E M I N L EL E C H E M I N L EP L U S C O U R T ! ! !P L U S C O U R T ! ! !
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 148148
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Il s’agit d’aller d’une ville de départ vers une ville Il s’agit d’aller d’une ville de départ vers une ville d’arrivée, par le plus court chemin, dansd’arrivée, par le plus court chemin, dans
– un réseau de villes avec routes en sens unique,un réseau de villes avec routes en sens unique,
– à distances connuesà distances connues
– et sans cycles (retour au point de départ).et sans cycles (retour au point de départ).
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 149149
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Il s’agit d’aller d’une ville de départ vers une ville Il s’agit d’aller d’une ville de départ vers une ville d’arrivée, par le plus court chemin, dansd’arrivée, par le plus court chemin, dans
– un réseau de villes avec routes en sens unique,un réseau de villes avec routes en sens unique,
– à distances connuesà distances connues
– et sans cycles (retour au point de départ).et sans cycles (retour au point de départ).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 150150
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Il s’agit d’aller d’une ville de départ vers une ville Il s’agit d’aller d’une ville de départ vers une ville d’arrivée, par le plus court chemin, dansd’arrivée, par le plus court chemin, dans
– un réseau de villes avec routes en sens unique,un réseau de villes avec routes en sens unique,
– à distances connuesà distances connues
– et sans cycles (retour au point de départ).et sans cycles (retour au point de départ).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111LesLespluspluscourtscourtschemins !chemins !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 151151
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 152152
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 153153
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111f( F ) = 0f( F ) = 0
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 154154
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F )
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 155155
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F )f( E ) = 37 + f( F )f( E ) = 37 + f( F )
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 156156
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F )f( E ) = 37 + f( F )f( E ) = 37 + f( F )f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) }
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 157157
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F )f( E ) = 37 + f( F )f( E ) = 37 + f( F )f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 158158
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Notations :Notations :
– Désignons par V( x ) l’ensemble des voisines d’une ville Désignons par V( x ) l’ensemble des voisines d’une ville x ,x ,
– Soit d( x , y ) la distance entre deux villes voisines,Soit d( x , y ) la distance entre deux villes voisines,
– Soit f( x ) le plus court chemin pour aller de x à F .Soit f( x ) le plus court chemin pour aller de x à F .
• f ( x ) = min d ( x , y ) + f ( y ) et f( F ) f ( x ) = min d ( x , y ) + f ( y ) et f( F ) = 0= 0
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F )f( E ) = 37 + f( F )f( E ) = 37 + f( F )f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }
y y V( x ) V( x )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 159159
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F )f( E ) = 37 + f( F )f( E ) = 37 + f( F )f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 160160
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 + f( F )f( D ) = 11 + f( F ) = 11 + 0 = 11 = 11 + 0 = 11f( E ) = 37 + f( F )f( E ) = 37 + f( F )f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 161161
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 + f( F )f( E ) = 37 + f( F ) = 37 + 0 = 37 = 37 + 0 = 37f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 162162
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = min{ 9 + f( D ) , 15 + f( E ) }f( B ) = min{ 9 + f( D ) , 15 + f( E ) } = min{ 9 + 11 , 15 + 37} = 20 = min{ 9 + 11 , 15 + 37} = 20f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 163163
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = min{ 37 + f( D ) , 12 + f( E ) }f( C ) = min{ 37 + f( D ) , 12 + f( E ) } = min{ 37 + 11 , 12 + 37} = 48 = min{ 37 + 11 , 12 + 37} = 48f( A ) = min{ 41 + f( B ) , 13 + f( C ) }f( A ) = min{ 41 + f( B ) , 13 + f( C ) }
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 164164
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = min{ 41 + f( B ) , 13 + f( C ) } f( A ) = min{ 41 + f( B ) , 13 + f( C ) } = min{ 41 + 20 , 13 + 48} = 61= min{ 41 + 20 , 13 + 48} = 61
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 165165
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = 61f( A ) = 61
f( A ) = 61f( A ) = 61 = 41 + f( B )= 41 + f( B )
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 166166
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = 61f( A ) = 61
f( A ) = 61f( A ) = 61 = 41 + f( B )= 41 + f( B ) = 41 + 9 + f( D )= 41 + 9 + f( D )
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 167167
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = 61f( A ) = 61
f( A ) = 61f( A ) = 61 = 41 + f( B )= 41 + f( B ) = 41 + 9 + f( D )= 41 + 9 + f( D ) = 41 + 9 + 11= 41 + 9 + 11
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 168168
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = 61f( A ) = 61
f( A ) = 61f( A ) = 61 = 41 + f( B )= 41 + f( B ) = 41 + 9 + f( D )= 41 + 9 + f( D ) = 41 + 9 + 11= 41 + 9 + 11
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
f( A ) = 61f( A ) = 61 = 13 + f( C )= 13 + f( C )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 169169
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = 61f( A ) = 61
f( A ) = 61f( A ) = 61 = 41 + f( B )= 41 + f( B ) = 41 + 9 + f( D )= 41 + 9 + f( D ) = 41 + 9 + 11= 41 + 9 + 11
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
f( A ) = 61f( A ) = 61 = 13 + f( C )= 13 + f( C ) = 13 + 37 + f( D )= 13 + 37 + f( D )
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 170170
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Nous résolvons ces contraintes par substitution :Nous résolvons ces contraintes par substitution :
f( F ) = 0f( F ) = 0f( D ) = 11 f( D ) = 11 f( E ) = 37 f( E ) = 37 f( B ) = 20f( B ) = 20f( C ) = 48f( C ) = 48f( A ) = 61f( A ) = 61
f( A ) = 61f( A ) = 61 = 41 + f( B )= 41 + f( B ) = 41 + 9 + f( D )= 41 + 9 + f( D ) = 41 + 9 + 11= 41 + 9 + 11
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
f( A ) = 61f( A ) = 61 = 13 + f( C )= 13 + f( C ) = 13 + 37 + f( D )= 13 + 37 + f( D ) = 13 + 37 + 11= 13 + 37 + 11
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 171171
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Principe de la résolution par programmation Principe de la résolution par programmation dynamique :dynamique :
– Nous allons supposer que les plus courts chemins sont Nous allons supposer que les plus courts chemins sont connus pour un sous-ensemble des villes. Ce seront des connus pour un sous-ensemble des villes. Ce seront des « voisines » de la ville d’arrivée.« voisines » de la ville d’arrivée.
– Pour les autres villes, nous ne connaissons qu’un majorant Pour les autres villes, nous ne connaissons qu’un majorant de la longueur du plus court chemin !de la longueur du plus court chemin !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 172172
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
• Principe de la résolution par programmation Principe de la résolution par programmation dynamique :dynamique :
– Nous allons supposer que les plus courts chemins sont Nous allons supposer que les plus courts chemins sont connus pour un sous-ensemble des villes. Ce seront des connus pour un sous-ensemble des villes. Ce seront des « voisines » de la ville d’arrivée.« voisines » de la ville d’arrivée.
– Pour les autres villes, nous ne connaissons qu’un majorant Pour les autres villes, nous ne connaissons qu’un majorant de la longueur du plus court chemin !de la longueur du plus court chemin !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 173173
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
Plus courtPlus courtchemin connu !chemin connu !
1111
00
3737
• Principe de la résolution par programmation Principe de la résolution par programmation dynamique :dynamique :
– Nous allons supposer que les plus courts chemins sont Nous allons supposer que les plus courts chemins sont connus pour un sous-ensemble des villes. Ce seront des connus pour un sous-ensemble des villes. Ce seront des « voisines » de la ville d’arrivée.« voisines » de la ville d’arrivée.
– Pour les autres villes, nous ne connaissons qu’un majorant Pour les autres villes, nous ne connaissons qu’un majorant de la longueur du plus court chemin !de la longueur du plus court chemin !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 174174
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Principe de la résolution par programmation Principe de la résolution par programmation dynamique :dynamique :
– Nous allons supposer que les plus courts chemins sont Nous allons supposer que les plus courts chemins sont connus pour un sous-ensemble des villes. Ce seront des connus pour un sous-ensemble des villes. Ce seront des « voisines » de la ville d’arrivée.« voisines » de la ville d’arrivée.
– Pour les autres villes, nous ne connaissons qu’un majorant Pour les autres villes, nous ne connaissons qu’un majorant de la longueur du plus court chemin !de la longueur du plus court chemin !
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
+inf+inf
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 175175
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Parmi les villes non définitives, nous choisissons celle Parmi les villes non définitives, nous choisissons celle qui est à la plus petite distance.qui est à la plus petite distance.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
+inf+inf
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 176176
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Parmi les villes non définitives, nous choisissons celle Parmi les villes non définitives, nous choisissons celle qui est à la plus petite distance.qui est à la plus petite distance.
• Cette distance est en fait exacte, et la ville passe dans Cette distance est en fait exacte, et la ville passe dans le camp de droite ! le camp de droite !
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
+inf+inf
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 177177
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Parmi les villes non définitives, nous choisissons celle Parmi les villes non définitives, nous choisissons celle qui est à la plus petite distance.qui est à la plus petite distance.
• Cette distance est en fait exacte, et la ville passe dans Cette distance est en fait exacte, et la ville passe dans le camp de droite ! le camp de droite !
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
+inf+inf
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 178178
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Parmi les villes non définitives, nous choisissons celle Parmi les villes non définitives, nous choisissons celle qui est à la plus petite distance.qui est à la plus petite distance.
• Cette distance est en fait exacte, et la ville passe dans Cette distance est en fait exacte, et la ville passe dans le camp de droite ! le camp de droite !
• Les villes qui la précèdent, et non définitives, sont Les villes qui la précèdent, et non définitives, sont mises à jour par rapport à leur plus court chemin.mises à jour par rapport à leur plus court chemin.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
+inf+inf
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 179179
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Parmi les villes non définitives, nous choisissons celle Parmi les villes non définitives, nous choisissons celle qui est à la plus petite distance.qui est à la plus petite distance.
• Cette distance est en fait exacte, et la ville passe dans Cette distance est en fait exacte, et la ville passe dans le camp de droite ! le camp de droite !
• Les villes qui la précèdent, et non définitives, sont Les villes qui la précèdent, et non définitives, sont mises à jour par rapport à leur plus court chemin.mises à jour par rapport à leur plus court chemin.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
min( 20 + 41 ,min( 20 + 41 , +inf ) = 61+inf ) = 61
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 180180
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Parmi les villes non définitives, nous choisissons celle Parmi les villes non définitives, nous choisissons celle qui est à la plus petite distance.qui est à la plus petite distance.
• Cette distance est en fait exacte, et la ville passe dans Cette distance est en fait exacte, et la ville passe dans le camp de droite ! le camp de droite !
• Les villes qui la précèdent, et non définitives, sont Les villes qui la précèdent, et non définitives, sont mises à jour par rapport à leur plus court chemin.mises à jour par rapport à leur plus court chemin.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
37373737
1111
1111
00
3737MajorantMajorantdu plusdu pluscourt chemin !court chemin !
2020
4848
6161
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 181181
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet.Exemple complet.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
+inf+inf +inf+inf
+inf+inf +inf+inf
2020 00
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 182182
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (première itération).Exemple complet (première itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
+inf+inf +inf+inf
+inf+inf +inf+inf
2020 00
Sélection !Sélection !
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 183183
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (première itération).Exemple complet (première itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
+inf+inf 1111
+inf+inf 3737
2020 00
Sélection !Sélection !
Mise à jour desMise à jour desprédécesseurs.prédécesseurs.
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 184184
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet.Exemple complet.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
+inf+inf 1111
+inf+inf 3737
2020 00
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 185185
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (deuxième itération).Exemple complet (deuxième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
+inf+inf 1111
+inf+inf 3737
2020 00
Sélection !Sélection !
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 186186
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (deuxième itération).Exemple complet (deuxième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
2020 1111
4848 3737
2020 00
Sélection !Sélection !
Mise à jour desMise à jour desprédécesseurs.prédécesseurs.
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 187187
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet.Exemple complet.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
2020 1111
4848 3737
2020 00
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 188188
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (troisième itération).Exemple complet (troisième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
+inf+inf
2020 1111
4848 3737
2020 00
Sélection !Sélection !
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 189189
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (troisième itération).Exemple complet (troisième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
6161
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Mise à jour desMise à jour desprédécesseurs.prédécesseurs.
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 190190
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet.Exemple complet.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
6161
2020 1111
4040 3737
2020 00
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 191191
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (quatrième itération).Exemple complet (quatrième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
6161
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 192192
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (quatrième itération).Exemple complet (quatrième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
6161
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Mise à jour desMise à jour desprédécesseurs.prédécesseurs.
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 193193
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet.Exemple complet.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
6161
2020 1111
4040 3737
2020 00
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 194194
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (cinquième itération).Exemple complet (cinquième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
6161
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 195195
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (cinquième itération).Exemple complet (cinquième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
5353
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Mise à jour desMise à jour desprédécesseurs.prédécesseurs.
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 196196
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet.Exemple complet.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
MajorantMajorantdu plusdu pluscourt chemin !court chemin !
5353
2020 1111
4040 3737
2020 00
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 197197
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (sixième itération).Exemple complet (sixième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
5353
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 198198
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet (sixième itération).Exemple complet (sixième itération).
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
5353
2020 1111
4040 3737
2020 00
Sélection !Sélection !
Mise à jour desMise à jour desprédécesseurs.prédécesseurs.
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 199199
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Exemple complet, c’est fini.Exemple complet, c’est fini.
AA
BB
CC
DD
EE
FF
4141
1313
99
1212
1515
3737 3737
1111
5353
2020 1111
4040 3737
2020 00
Plus courtPlus courtchemin connu !chemin connu !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 200200
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
pour toutes les villes v : f[ v ] = +inf ;
f[ arrivee ] = 0 ;
V = « l’ensemble de toutes les villes » ;
tantque V <> {}
{choisir dans V la ville x tq f[ x ] soit minimale sur V
/* Si ex aequo, on choisit une ville optimale au hasard */
V = V – { x } ;
pour toute ville v dans V et tq d( v , x ) est finie
f[ v ] = min( f[ v ] , d( v , x ) + f[ x ] ) ;
}
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 201201
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
pour toutes les villes v : f[ v ] = +inf ;
f[ arrivee ] = 0 ;
V = « l’ensemble de toutes les villes » ;
tantque V <> {}
{choisir dans V la ville x tq f[ x ] soit minimale sur V
/* Si ex aequo, on choisit une ville optimale au hasard */
V = V – { x } ;
pour toute ville v dans V et tq d( v , x ) est finie
f[ v ] = min( f[ v ] , d( v , x ) + f[ x ] ) ;
}
Initialisations !Initialisations !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 202202
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
pour toutes les villes v : f[ v ] = +inf ;
f[ arrivee ] = 0 ;
V = « l’ensemble de toutes les villes » ;
tantque V <> {}
{choisir dans V la ville x tq f[ x ] soit minimale sur V
/* Si ex aequo, on choisit une ville optimale au hasard */
V = V – { x } ;
pour toute ville v dans V et tq d( v , x ) est finie
f[ v ] = min( f[ v ] , d( v , x ) + f[ x ] ) ;
}
Il y a un tour de boucle par ville !Il y a un tour de boucle par ville !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 203203
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
pour toutes les villes v : f[ v ] = +inf ;
f[ arrivee ] = 0 ;
V = « l’ensemble de toutes les villes » ;
tantque V <> {}
{choisir dans V la ville x tq f[ x ] soit minimale sur V
/* Si ex aequo, on choisit une ville optimale au hasard */
V = V – { x } ;
pour toute ville v dans V et tq d( v , x ) est finie
f[ v ] = min( f[ v ] , d( v , x ) + f[ x ] ) ;
}
f[ x ] est la longueurf[ x ] est la longueurdu plus courtdu plus court
chemin issu de x !chemin issu de x !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 204204
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
pour toutes les villes v : f[ v ] = +inf ;
f[ arrivee ] = 0 ;
V = « l’ensemble de toutes les villes » ;
tantque V <> {}
{choisir dans V la ville x tq f[ x ] soit minimale sur V
/* Si ex aequo, on choisit une ville optimale au hasard */
V = V – { x } ;
pour toute ville v dans V et tq d( v , x ) est finie
f[ v ] = min( f[ v ] , d( v , x ) + f[ x ] ) ;
}
f[ x ] est la longueurf[ x ] est la longueurdu plus courtdu plus court
chemin issu de x !chemin issu de x !x est retirée de l’ensemble !x est retirée de l’ensemble !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 205205
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
pour toutes les villes v : f[ v ] = +inf ;
f[ arrivee ] = 0 ;
V = « l’ensemble de toutes les villes » ;
tantque V <> {}
{choisir dans V la ville x tq f[ x ] soit minimale sur V
/* Si ex aequo, on choisit une ville optimale au hasard */
V = V – { x } ;
pour toute ville v dans V et tq d( v , x ) est finie
f[ v ] = min( f[ v ] , d( v , x ) + f[ x ] ) ;
}
f[ x ] est la longueurf[ x ] est la longueurdu plus courtdu plus court
chemin issu de x !chemin issu de x !x est retirée de l’ensemble !x est retirée de l’ensemble !
Les villes qui précèdent x sont mises à jour !Les villes qui précèdent x sont mises à jour !
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 206206
Shortest Path ProblemShortest Path Problem----------------------------------------------------------------------------------------------------------------------------------
• Ceci est l’algorithme des plus courts chemins de Ceci est l’algorithme des plus courts chemins de Dijkstra.Dijkstra.
• Sa complexité est de O ( n^2 ) où « n » est le Sa complexité est de O ( n^2 ) où « n » est le nombre de villes.nombre de villes.
• Plus précisément, il est en Plus précisément, il est en ( m ) où « m » est ( m ) où « m » est le nombre d’arcs.le nombre d’arcs.
• L’algorithme est optimal, car le problème ne L’algorithme est optimal, car le problème ne peut pas être résolu avec une complexité plus peut pas être résolu avec une complexité plus petite.petite.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 207207
SynthèseSynthèse----------------------------------------------------------------------------------------------------------------------------------
Programmation dynamique :Programmation dynamique :
Problème du sac à dos.Problème du sac à dos.
Négociant en sardines au port de Marseille.Négociant en sardines au port de Marseille.
Problème de la plus longue sous-chaîne Problème de la plus longue sous-chaîne commune.commune.
Problème du plus court chemin.Problème du plus court chemin.
23 novembre 200623 novembre 2006 Cours d'algorithmique 6 - IntranetCours d'algorithmique 6 - Intranet 208208
m E r C i e Tm E r C i e Tb O n N e J o U r N é b O n N e J o U r N é
E ! ! !E ! ! !
n ‘ O u B l I e Z p A s D en ‘ O u B l I e Z p A s D ep R é P a R e R v O sp R é P a R e R v O s
T D ! ! !T D ! ! !