Maximum Path Sum (Project Euler)
Posté le 16/10/2016 à 11:04
On cherche à trouver, dans un arbre binaire, à trouver le chemin pour lequel la somme de tout les noeuds est maximale. Comme précisé dans la note de bas de page du problème 18 de Project Euler, si la hauteur de l'arbre est limitée, il est possible de résoudre ce problème en parcourant toute les différentes possibilités. Le nombre de chemins possible est égal à $2^{n-1}$, $n$ étant la hauteur maximale de l'arbre. Dans le problème $n^{o}18$, l'arbre est de hauteur $n=14$, le nombre de possibilité est donc de $16384$. Dans le problème $n^{o}67$, l'arbre est de hauteur $100$. Il y a donc $2^{99}$ chemins possibles. Il serait bien entendu plus qu'optimiste de passer par une méthode dite de force brute.
La méthode que je décris ci-dessous permet de réduire la complexité du problème de manière très importante. En effet, au lieu de parcourir $2^{n-1}$ chemins possibles, on peut résoudre le challenge en ne parcourant chaque nœud de l'arbre qu'une seule fois.
Partons d'un problème simple, un arbre à trois nœud : une racine et deux feuilles, il y a donc trois valeurs. Le chemin est très facile à trouver dans ce cas : on choisis la feuille la plus grande. Ce chemin a une valeur de $S = T[\text{racine}] + \text{max}\left(T\left[\text{fils_gauche}\right], T\left[\text{fils_droit}\right]\right)$. On se rends compte que l'on a plus besoin des feuilles. La valeur $S$ représente complètement le chemin à valeur maximal si l'on remplace la valeur de $T\left[\text{racine}\right]$ directement par $S$.
Replacons dans le contexte de notre arbre de hauteur $n=14$. En effectuant l'opération décrite ci-dessus sur tout les noeuds dont les fils sont des feuilles, on peut obtenir les chemins maximisant de ces noeuds et retirer les feuilles qui ne nous sont plus utiles. Les noeuds précédemment choisis deviennent donc des feuilles de l'arbre. Le nouvel arbre a donc une hauteur $n=13$. Nous pouvons recommencer, faisant passer la hauteur de l'arbre à $n=12$, $n=11$,... ect. Une fois l'arbre réduit à un seul noeud, on a la valeur du chemin maximal.
La méthode que je décris ci-dessous permet de réduire la complexité du problème de manière très importante. En effet, au lieu de parcourir $2^{n-1}$ chemins possibles, on peut résoudre le challenge en ne parcourant chaque nœud de l'arbre qu'une seule fois.
Partons d'un problème simple, un arbre à trois nœud : une racine et deux feuilles, il y a donc trois valeurs. Le chemin est très facile à trouver dans ce cas : on choisis la feuille la plus grande. Ce chemin a une valeur de $S = T[\text{racine}] + \text{max}\left(T\left[\text{fils_gauche}\right], T\left[\text{fils_droit}\right]\right)$. On se rends compte que l'on a plus besoin des feuilles. La valeur $S$ représente complètement le chemin à valeur maximal si l'on remplace la valeur de $T\left[\text{racine}\right]$ directement par $S$.
Replacons dans le contexte de notre arbre de hauteur $n=14$. En effectuant l'opération décrite ci-dessus sur tout les noeuds dont les fils sont des feuilles, on peut obtenir les chemins maximisant de ces noeuds et retirer les feuilles qui ne nous sont plus utiles. Les noeuds précédemment choisis deviennent donc des feuilles de l'arbre. Le nouvel arbre a donc une hauteur $n=13$. Nous pouvons recommencer, faisant passer la hauteur de l'arbre à $n=12$, $n=11$,... ect. Une fois l'arbre réduit à un seul noeud, on a la valeur du chemin maximal.