On souhaite parcourir une pyramide de nombres, de haut en bas, en se déplaçant à chaque fois d’une ligne vers le bas, légèrement sur la gauche ou sur la droite.
Le poids d’un chemin est la somme des nombres parcourus par ce chemin. L’objectif est de trouver le chemin de poids maximal.
Dans cet exemple 3+6+2+4 = 15
. Il n'est pas maximal.
Identifiez "à la main" le chemin de poids maximal. Donnez son poids.
On peut représenter cette structure par la liste de listes suivante:
pyramide = [
[3],
[7,6],
[1,2,9],
[8,5,4,2]
]
Une stratégie peut être de choisir localement à chaque étape la case suivante de plus haute valeur:
Cet algorithme trouve dans cet exemple le chemin
Programmez la fonction
recherche_chemin(pyramide: list)
dont le but est de renvoyer le chemin de poids maximal sous forme de liste en utilisant un algorithme glouton.
>>> recherche_chemin(pyramide)
[3, 7, 2, 5]
Le chemin renvoyé par la fonction algorithme glouton est-il optimal? Quel est le problème de cet algorithme?
Pour identifier le chemin optimal, on n'a pas d'autre choix que de tester plusieurs chemins pour passer au moins une fois sur toutes les cases de la pyramide.
Une stratégie peut être de résoudre la question du choix du "meilleur suivant" en traitant récursivement la case de droite et celle de gauche comme 2 sommets de leur propre "sous-pyramide".
On peut se baser sur le raisonnement récursif suivant:
Dans cette exemple à l'étape de la case
Programmez la fonction récursive
poids_meilleur_chemin(pyramide: list)
(et d'autres paramètres si besoin) qui renvoie le poids du chemin de poids maximal.
>>> poids_meilleur_chemin(pyramide)
22
Bonus:
Programmez la fonction
recherche_meilleur_chemin(pyramide: list)
en modifiantpoids_meilleur_chemin(pyramide: list)
qui renvoie le poids du chemin et la liste des sommets traversés correspondant au chemin de poids maximal.
On pourra utiliser la propriété python qui autorise à renvoyer 2 objets (ex: un entier et un tableau) comme dans l'exemple:
def fonction(tab, chemin=None, poids_chemin=0):
if chemin is None:
chemin = []
# Ajout de l'élément courant de tab dans chemin
chemin = chemin + [tab[0]]
poids_chemin += tab[0]
if len(tab) == 1:
# Renvoi d'un couple de valeurs qui remontent les appels récursifs
return poids_chemin, chemin
# Slicing de tab pour passer à l'indice suivant
new_tab = tab[1:]
return fonction(new_tab, chemin, poids_chemin)
>>> tab = [0,1,2,3]
>>> fonction(tab)
(6, [0,1,2,3])