Les algorithmes gloutons: pyramide de nombre

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.

3
7
6
1
2
9
8
5
4
2

Dans cet exemple 3 - 6 - 2 - 4 est un chemin quelconque de poids 3+6+2+4 = 15. Il n'est pas maximal.

  1. 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]
]

En utilisant un algorithme glouton:

Une stratégie peut être de choisir localement à chaque étape la case suivante de plus haute valeur:

3
7
6
1
2
9
8
5
4
2

Cet algorithme trouve dans cet exemple le chemin 3 - 7 - 2 - 5. Il s'agit d'un algorithme glouton.

  1. 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]

  1. 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.

En utilisant un algorithme force brute

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:

Poids du chemin ={sommet courant si hauteur(pyramide) = 1sommet courant + max(sous-pyramide gauche, sous-pyramide droite) sinon\text{Poids du chemin =} \begin{cases} \color{red}\verb"sommet courant "\color{black} & si \verb" hauteur(pyramide) = 1"\\ \color{red}\verb"sommet courant" \color{black}\verb" + max("\color{green}\verb"sous-pyramide gauche"\color{black}\verb", "\color{blue}\verb"sous-pyramide droite"\color{black}\verb") " & sinon \end{cases}

3
7
6
1
2
9
8
5
4
2
3
7
6
1
2
9
8
5
4
2

Dans cette exemple à l'étape de la case 3, on compare le résultat de la fonction sur la sous-pyramide de sommet 7 et celle de sommet 6.

  1. 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:

  1. Programmez la fonction recherche_meilleur_chemin(pyramide: list) en modifiant poids_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])