Skip to main content Informatique en prépa - Lycée Malherbe 

4.1- TP - Déplacement du robot

Objectif

se familiariser avec la programmation dynamique pour d’une part obtenir la valeur optimale et d’autre part, la reconstruction d’une solution et même de toutes les solutions.

Un petit robot doit se déplacer sur un damier à lignes et colonnes, en partant de la case en haut à gauche indicée par le couple jusqu’à la case en bas à droite indicée par le couple . Le robot ne peut effectuer des pas que de la gauche vers la droite ou du haut vers le bas. Sur le damier sont disséminés un certain nombre d’objets auxquels sont attribués une utilité représentée par une valeur entière strictement positive et que le robot peut ramasser sur son passage. L’objectif est alors de déterminer un trajet pour lequel la somme des utilités des objets ramassés est maximale.

Exemple qui servira de référence tout au long du TP : image.png

Une donnée du problème est modélisée par une liste de listes u d’entiers de sorte que u[i][j] contient l’utilité de l’objet qui se trouve à l’intersection de la -ième ligne et de la -ième colonne, ou 0 s’il n’y a rien à cet emplacement.

Dans l’exemple précédent, on a :

Le trajet d’un robot sera représenté par une liste de caractères 'D' pour le déplacement vers la droite et 'B' pour le déplacement vers le bas.

Question 1

Compléter ci-dessous la liste de listes u des utilités correspondantes à l’exemple précédent puis exécuter la cellule

Python

Loading editor...

u=[[ 0 ,   ,   ,   ,   ,   ,   ,   ,   ,   ],
   [ 2 ,   ,   ,   ,   ,   ,   ,   ,   ,   ],
   [   ,   ,   ,   ,   ,   ,   ,   ,   ,   ],
   [   ,   ,   ,   ,   ,   ,   ,   ,   ,   ],
   [   ,   ,   ,   ,   ,   ,   ,   ,   , 0 ]]
Question 2

Que représentent les valeurs des instructions suivantes : len(u) et len(u[0]) ?

Question 3

Quelle est la somme des utilités du trajet ci-dessous ?

trajet=['B','D','D','D','D','D','B','D','B','D','B','D','D']

Question 4

Les trajets ci-dessous sont-ils valides ? Pourquoi ? t1=['B','D','D','D','D','D','B','B','D','B','D','D'] t2=['B','D','D','B','D','D','B','D','B','D','B','D','D']

Question 5

À quelles conditions (nécessaires et suffisantes) une liste de caractères quelconques correspond-elle à un trajet valide ?

Question 6

Écrire une fonction occurencesBetD qui prend comme argument une liste de caractères t, qui renvoie sous forme de couple, le nombre de caractères 'B' et le nombre de caractères 'D'. Par exemple, si t=['E','B','D','F','D','D','B'] alors occurencesBetD(t) est le couple (2,3) car il y a 2 'B' et 3 'D'.

Python

Loading editor...

def occurencesBetD(t):
    ''' In : une liste de caractères t
        Out: le nombre de 'B' et de 'D' dans t'''
    pass

Tester votre fonction pour t=['E','B','D','F','D','D','B'] puis pour chacun des trajets définis plus haut : trajet, t1 et t2

Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Test de la fonction précédente
# me permet de voir que votre fonction à l'air correcte, c'est le cas si cette cellule ne renvoie pas d'erreur
from random import randint
for test in range(10):
    t=[chr(randint(65,90)) for _ in range(100)]
    assert occurencesBetD(t)==(t.count('B'),t.count('D'))
Question 7

Écrire une fonction estValide qui prend comme arguments une liste de listes u des utilités et une liste de caractères t, qui renvoie True si t est valide et False sinon

Python

Loading editor...

def estValide(u,t):
    ''' In : une liste de listes u et une liste de caractères
        Out: True si t est un trajet valide et False sinon'''
    pass

Tester votre fonction pour chacun des trajets définis plus haut : trajet, t1 et t2.

On vérifiera alors la réponse donnée à la question 4.

Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Test de la fonction précédente
# me permet de voir que votre fonction à l'air correcte, c'est le cas si cette cellule ne renvoie pas d'erreur
from random import randint
for test in range(100):
    v=[[0]*3 for _ in range(5)]
    t=[chr(randint(65,90)) for _ in range(6)]
    assert estValide(v,t)==(t.count('B')==4 and t.count('D')==2)
for test in range(100):
    p=randint(1,3)
    q=randint(1,3)
    v=[[0]*3 for _ in range(2)]
    t=['B']*(p-1)+['D']*(q-1)
    assert estValide(v,t)==(p==2 and q==3)
Question 8

Écrire une fonction sommeUtilite qui prend en arguments une liste de listes d’utilités u et un trajet t valide du robot, qui renvoie la somme des utilités des objets ramassés le long du trajet. On vérifiera alors la réponse donnée à la question 3.

Python

Loading editor...

def sommeUtilite(u,t):
    ''' In : une liste de listes u et une liste t de déplacements du robot
        Out: la somme des utilités des objets ramassés le long du chemin'''
    pass
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Test de la fonction précédente
# me permet de voir que votre fonction à l'air correcte, c'est le cas si cette cellule ne renvoie pas d'erreur
p,q=6,4
t=['B']*(p-1)+['D']*(q-1)
__u=[[0, 41, 49, 62], [44, 20, 95, 59], [76, 61, 44, 97], [100, 6, 23, 34], [99, 63, 64, 39], [85, 14, 63, 37]]
trajets=[['B', 'B', 'B', 'D', 'D', 'B', 'B', 'D'],['B', 'B', 'D', 'B', 'B', 'D', 'B', 'D'],['D', 'B', 'B', 'B', 'B', 'D', 'B', 'D']]
assert [sommeUtilite(__u,t) for t in trajets]==[413, 414, 355]

I. Une première idée : la stratégie par force brute

Pour déterminer le trajet optimal, on peut déterminer tous les trajets valides, puis à l’aide de la fonction précédente calculer celui qui est optimal. Dans l’exemple plus haut, on a lignes et colonnes. On trouve 715 trajets possibles ce qui se fait en un temps très raisonnable pour un ordinateur.

Question de math

Pourquoi 715 ?

Pour déterminer un trajet, il suffit de placer par exemple les déplacements B (on complète le reste par des D) et pour cela on a p-1=4 choix parmi p+q-2=13 donc il y a en tout

Question 9

Dans le cas où , on trouve un peu plus de trajets possibles. En faisant l’hypothèse que l’ordinateur nous donne la somme des utilités en seulement 0,00001 seconde, combien de temps faudra-t-il attendre pour avoir la somme maximale des utilités ?

II. Une autre idée : une approche gloutonne

L’idée d’un algorithme glouton consiste à se poser la question suivante : étant donné le robot en case , quel sera pour lui, localement, le meilleur choix entre aller vers la droite et aller vers le bas ?

Question 10

Proposer une réponse à cette question.

Question 11

Expliquer en quelques mots pourquoi cela ne donnera pas forcément un trajet optimal. Pour cela, on pourra s'appuyer sur l'exemple suivant :

0000000000100
10000000000
10000000000
10000000000
10000000000

En rouge, le trajet choisi par l'algorithme glouton ; en bleu, un autre trajet. La même grille en Python :

Python

Loading editor...

u = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100],
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

III. Une bien meilleure idée : la programmation dynamique

Pour tous entiers et tels que et , on note la somme maximale des utilités d’un trajet parmi tous ceux qui terminent à la case .

On rappelle qu'on dispose d'une liste de listes u de sorte que u[i][j]=u_{i,j} l’utilité de l’objet qui se trouve à l’intersection de la -ième ligne et de la -ième colonne (éventuellement nulle s'il n'y a pas d'objet à cet emplacement).

Question 12

Quelle est la valeur de ?

Question 13

À quoi correspond la valeur de ?

Question 14

Pour calculer , on va calculer de proche en proche les valeurs grâce à des relations. Justifier que pour tous entiers et tels que et , on a les trois égalités suivantes :

  • a)
  • b)
  • c)
Question 15

À l’aide des trois égalités précédentes, compléter au fur et à mesure à la main les valeurs .

Vous pouvez recopier le tableau ci-dessous sur papier pour le remplir.

j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9
i=00
i=12
i=2
i=3
i=4
Question 16

Écrire une fonction CalculeUtilite qui prend en argument une liste de listes d’utilités u et qui renvoie la liste de listes m telle que m[i][j] soit la somme maximale des utilités d’un trajet parmi tous ceux qui terminent à la case . On vérifiera alors la réponse donnée à la question précédente.

Python

Loading editor...

def calculeUtilite(u):
    ''' In : une liste de listes u
        Out: la liste de listes m tq
             m[i][j]=somme maximale des utilités parmi tous les chemins qui terminent en case (i,j)'''
    pass
Question 17

Tester votre fonction et comparer avec la réponse donnée à la question 15.

On pourra utiliser la fonction afficheMatrice ci-dessous pour afficher convenablement la liste de listes m renvoyée par la fonction CalculeUtilite.

Python

Loading editor...

def afficheMatrice(m):
    ''' In : une liste de listes m
        Act: l'affichage de cette liste de listes'''
    for i in range(len(m)):
        print(f'i={i:=2}',end=' :') # c'est une fstring, le {i:=2} affiche la valeur de i prenant la place de 2 caractères
        for j in range(len(m[i])):
            print(f'{m[i][j]:=3}',end=' ') # {m[i][j]:=3} affiche la valeur de m[i][j] prenant la place de 3 caractères
        print()
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Test de la fonction précédente
# me permet de voir que votre fonction à l'air correcte, c'est le cas si cette cellule ne renvoie pas d'erreur
v=[[99, 40, 86, 7], [34, 72, 85, 6], [51, 8, 99, 44], [77, 97, 84, 56], [11, 77, 84, 63], [75, 4, 68, 61]]
assert calculeUtilite(v)==[[99, 139, 225, 232], [133, 211, 310, 316], [184, 219, 409, 453], [261, 358, 493, 549], [272, 435, 577, 640], [347, 439, 645, 706]]
Question 18

Comment à l’aide de la liste de listes m peut-on reconstruire un trajet optimal ?

Indication : en partant de la valeur (tout en bas à droite), reconstruire un trajet optimal

Question 19

Compléter ci-dessous la fonction trajetOptimal qui prend en argument une liste de listes d’utilités u et qui renvoie un trajet optimal. On vérifiera alors la réponse donnée à la question précédente.

Python

Loading editor...

def trajetOptimal(u):
    ''' In : une liste de listes d'utilités u
        Out: une liste correspondant à un trajet optimal du robot'''
    m=calculeUtilite(u) # on récupère la liste de listes m qui va nous servir pour la reconstruction
    p=len(u) # nb de lignes
    q=len(u[0]) # nb de colonnes
    L=[] # le trajet optimal qu'on souhaite renvoyer
    i,j=p-1,q-1 # on part de tout en bas à droite
    while i>0 or j>0:
        if i>0 and ... :# le trajet optimal vient du haut
            L.append('B')
            i=i-1
        else:# le trajet optimal vient de la gauche
            L.append(...)
            ...
    L.reverse() # on renverse la liste puisqu'on est parti de la fin
    return L

Tester votre fonction

Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Test de la fonction précédente
# me permet de voir que votre fonction à l'air correcte, c'est le cas si cette cellule ne renvoie pas d'erreur
v=[[1, 5, 0, 1], [3, 2, 4, 0], [1, 1, 1, 5], [3, 3, 4, 1], [4, 5, 2, 0], [3, 1, 3, 2]]
assert trajetOptimal(v)==['D', 'B', 'D', 'B', 'B', 'B', 'B', 'D']

IV. Questions bonus

Bonus 1

Ecrire une fonction récursive trajetsOptimaux qui prend comme argument une liste de listes d’utilités u et qui renvoie une liste de tous les trajets optimaux.

L’idée est de constituer une file dans laquelle vous construisez peu à peu vos solutions. Dans cette file, on peut mettre initialement le triplet `(p-1,q-1,[])` où le dernier élément sera la liste que l'on construit peu à peu.
Python

Loading editor...

def trajetsOptimaux1(u):
    ''' In : une liste de listes d'utilités u
        Out: une liste correspondant à tous les trajets optimaux'''
    pass
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Test de la fonction précédente
# me permet de voir que votre fonction à l'air correcte, c'est le cas si cette cellule ne renvoie pas d'erreur
v=[[1, 5, 0, 1], [3, 2, 4, 0], [1, 1, 1, 5], [3, 3, 4, 1], [4, 5, 2, 0], [3, 1, 3, 2]]
L1=trajetsOptimaux1(v)
L=[['D', 'B', 'D', 'B', 'B', 'B', 'B', 'D'], ['D', 'B', 'B', 'B', 'B', 'D', 'B', 'D'], ['B', 'B', 'B', 'B', 'D', 'D', 'B', 'D']]
for x in L:
    assert x in L1
for x in L1:
    assert x in L

On décide maintenant de rajouter des obstacles sur le damier en supprimant certaines cases. La case contient maintenant la valeur lorsque la case est supprimée : le robot ne peut plus passer par cette case. Exemple : image.png

Bonus 2

Modifier la fonction calculeUtilite pour qu’elle fournisse à nouveau un trajet optimal en tenant comte de cette contrainte supplémentaire. Modifier également la fonction trajetOptimal puis tester vos fonctions.

Python

Loading editor...

def calculeUtilite(u):
    ''' In : une liste de listes u
        Out: la liste de listes m tq
        m[i][j]=utilité max d'un chemin parmi ceux qui terminent en case (i,j)'''
    pass
Python

Loading editor...

# Jeu de tests
u=[[0,0,0,0,-1,0,0,1,0,9],
   [2,0,0,0,0,8,0,0,0,0],
   [0,0,1,0,-1,0,-1,2,0,0],
   [-1,0,0,-1,8,0,4,0,0,0],
   [1,0,0,0,0,0,0,0,0,0]]
Python

Loading editor...

def sommeUtilite(u,t):
    ''' In : une liste de listes u et une liste t de déplacement du robot
        Out: la somme des utilités des objets ramassés le long du chemin
             et False si le trajet n'est pas possible'''
    pass
def trajetOptimal(u):
    ''' In : une liste de listes u
        Out: une liste correspondant un chemin optimal du robot'''
    pass
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# Jeu de tests
Python

Loading editor...

# un test où le trajet est impossible
u=[[0,0,0,0,0,0,0,1,0,9],
   [2,0,0,0,0,8,0,0,-1,0],
   [0,0,1,0,-1,0,0,2,0,0],
   [0,0,0,-1,8,-1,4,-1,0,-1],
   [1,0,0,0,0,-1,0,-1,-1,0]]
Python

Loading editor...

    
 
 
Entrez le code donné en cours pour accéder à la solution :