Discussion :

[Myrne]

Bonjour à tous,

J'essaye de résoudre le problème suivant: http://projecteuler.net/problem=18

Pour être exact, je l'ai résolu en bruteforce, et vu qu'il y a un peu plus tard un problème identique avec 2^99 chemins possibles, j'aimerais bien le résoudre d'une façon un peu plus propre, mais je n'ai absolument aucune idée de par où commencer.

Je ne demande pas de solution, puisque le jeu c'est justement de la trouver par moi même, mais si vous aviez des propositions de méthodes/algorithmes qui pourraient se révéler efficaces, je suis preneur.

Merci d'avance !

[kwariz]

Bonjour,

tu peux essayer différentes pistes ... partons du triangle où je numérote les positions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

P(i) est la valeur du sommet i, FG(i) (resp. FD(i)) est l'indice du fils gauche (resp. droit) du sommet i.
SM(i) est la valeur chemin de somme maximum partant du sommet i.
Pour tous les sommets i situés à la base du triangle on a trivialement P(i)=SM(i).
On va essayer de scinder le problème en problèmes équivalent plus petits :
Crois-tu pouvoir montrer qu'en fait on a :
SM(i)=P(i) + MAX( SM(FG(i)), SM(FD(i)) ?

Autrement dit, le chemin se somme maximum à partir d'un noeud emprunte le chemin de somme maximum le plus grand entre ses deux fils ?

Si tu le peux alors la solution est toute trouvée ...
L'implémentation peut être récursive du haut vers le bas, et tu peux aussi en trouver une super simple qui part du bas pour remonter ...

Bonne recherche

[Myrne]

Merci pour cette réponse, j'ai trouvé ma solution en démontrant ce que tu proposes

Si je prends le triangle suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65

En prenant, dans la ligne du bas, la première paire (20, 04), il est évident que venant d'au dessus (le 18), j'irai à gauche pour choisir le plus grand nombre de la paire. Je vais donc remplacer mon 18 par la somme 20+18.

En faisant cela pour chaque paire de la ligne inférieure (04-82, 82-47, ...), j'obtiens un nouveau triangle:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
75
95 64
17 47 82
38 117 169 70
00 00 00 00 00

Si je continue à remonter de cette manière, j'obtiens de façon immédiate la somme maximale (et le chemin si je garde une trace de chacun des choix).

Je mets le sujet en résolu, mais par contre, je ne comprends pas comment tu peux trouver la solution en partant du haut:
j'ai démontré ta proposition en partant du bas, par récurrence. Mais du coup, l'application de cette proposition se fait aussi en partant du bas.

Comment pourrais-je partir du haut? En partant de la pointe en haut du triangle, le fils ayant la valeur maximale ne sera pas forcément le choix à faire pour obtenir le chemin de somme maximale, et je ne vois pas comment l'on pourrait anticiper cela.

Un exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
   0
  10 0
 10 0 0
10 0 0 99

Avec ce triangle, le chemin de somme maximale est celui où l'on part tout le temps à droite, et il n'est pas possible d'anticiper cela avant la dernière ligne, si l'on part du haut.
Y-aurait-il quelque-chose que j'aurai mal compris?

[prgasp77]

Sinon Dijkstra marche très bien.

[kwariz]

En fait la solution du haut vers le bas est tout simplement l'implémentation naïve d'un algo récursif tout simple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
SommeMax( sommet )
debut
  si sommet n'a pas de fils alors
    retourner poids(sommet)
  sinon
    somme_gauche = SommeMax(fils_gauche(sommet))
    somme_droite = SommeMax(fils_droit(sommet))
    retourner poids(sommet) + MAX( somme_gauche, somme_droite )
  fin si
fin

Cette implémentation naïve n'est pas performante du tout car énormément de calcul sont fait plusieurs fois. Si on fait un petit dessin on voit que si on part de 0 on fait un appel pour le calcul du sous arbre gauche (rouge), puis pour le sous arbre droit (bleu) et que la partie violette est calculée plusieurs fois ...



Pour éviter de recalculer on peut utiliser une technique de mémoïsation qui elle sera plus performante et qui si on la regarde de plus près nous amène à la solution que tu as trouvée : la solution bas vers le haut qui est constructive, itérative et de bonne complexité ... idéale non ?

D'ailleurs si on raisonne sur la hauteur h de ton triangle on obtient comme nombre de noeuds n=h(h+1)/2 dont h noeuds sur la dernière ligne. La solution récursive naïve aura une complexité en O(2^h)=O(2^sqrt(n)), la solution récursive mémoïsée sera en O(h^2)=O(n) et la solution itérative également en O(n)=o(h^2).

[Myrne]

Ok je vois, donc la solution naïve du haut vers le bas, c'est exactement ce que j'avais fait quand je parlais de bruteforce =)

Merci beaucoup pour ces explications !