Approche du projet Euler #18

Question

J'étudie un projet Euler. Plus précisément le numéro 18.
Pour résumer, l'idée est de trouver le chemin maximal d'un triangle :

   3
  7 4
 2 4 6  
8 5 9 3

3 + 7 + 4 + 9 = 23.

La plupart des gens indiquent que l'on résout correctement ce problème en travaillant de bas en haut au lieu d'utiliser un algorithme qui travaille de manière "avide" de haut en bas.

Je peux comprendre que le fait de commencer par le haut et de descendre en sélectionnant le maximum que vous trouvez est "à courte vue" et peut ne pas être le maximum global.

Mais pourquoi l'approche consistant à aller du bas vers le haut est-elle meilleure ?
Il me semble qu'il souffre du même problème.

Par exemple, dans le triangle de l'exemple, nous aurions (en partant du bas) :
9+6+4+3=22 < 23

Alors pourquoi commencer par le bas ?

Answer 1

C'est ce qu'on appelle la programmation dynamique.

Vous avez un tel triangle :

   3
  7 4
 2 4 6  
8 5 9 3

Lorsque vous vous déplacez du bas vers le haut, vous pouvez calculer les meilleurs choix de la dernière itération. Dans ce cas, on prend la dernière ligne 8 5 9 3 et maximiser la somme en plus de la ligne précédente.

Itération 1 : Supposons que vous êtes sur last-1 étape.

Vous avez la ligne 2 4 6 nous allons l'itérer.

De 2 vous pouvez aller soit à 8 ou 5, donc 8 est meilleur (maximiser votre résultat à partir de 2) donc vous calculez d'abord la somme 8 + 2 = 10.

De 4 vous pouvez aller à 5 ou 9 donc 9 est meilleur (maximiser votre résultat à partir de 4) donc vous calculez la deuxième somme 9 + 4 = 13.

De 6 vous pouvez aller soit à 9 ou 3, donc 9 est encore meilleure (maximiser votre résultat à partir de 6) et vous calculez donc la troisième somme 9 + 6 = 15.

C'est la fin de la première itération et vous avez obtenu la ligne de sommes 10 13 15 .

Maintenant, vous avez un triangle de dimension inférieure :

    3
  7  4
10 13 15  

Continuez ainsi jusqu'à ce que vous obteniez une valeur, qui est exactement 23.

Answer 2

La différence n'est pas entre le top-down et le bottom-up. La différence est entre les méthodes avides et les méthodes "frontière".

Un algorithme avide ne vous aidera pas nécessairement, car vous ne pourrez pas récupérer si la meilleure partie de l'arbre est hors de portée. Par exemple : un algorithme avide choisirait le chemin 1-3 de haut en bas. Il manquerait entièrement le 9.

    1
   2 3
  9 1 1

Pour trouver le vrai maximum, il faudrait essentiellement parcourir presque tous les chemins.

L'approche ascendante, telle qu'elle est décrite, n'a pas ce problème. Elle examine au plus n*(n-1) chemins : 2 pour chaque élément. Cependant, le fait de l'appeler l'approche "ascendante" est trompeur.

Pourquoi ? Parce qu'il existe une approche descendante qui est équivalente. L'essentiel est que vous avez une sorte de "frontière" avec les meilleurs résultats pour tous les arbres situés derrière la frontière. Que vous déplaciez la frontière vers le haut ou vers le bas est secondaire. Pour l'approche descendante de l'exemple ci-dessus, vous calculez pour chaque ligne la somme de chaque élément et le maximum des deux meilleurs totaux au-dessus :

     1
    3 4
  12 5 5

Dans l'approche ascendante, vous calculez pour chaque ligne la somme de chaque élément et le maximum des deux meilleurs totaux situés en dessous. Dans l'ordre inverse :

  9  1 1
   11 4
    12

Le travail est à peu près égal dans ces deux approches, descendante et ascendante.

Answer 3

En utilisant votre exemple, la façon "ascendante" de l'aborder est la suivante :

En examinant la rangée du bas, le maximum que vous pouvez obtenir de chaque élément est

8,5,9,3

En examinant la rangée suivante, le maximum que vous pouvez obtenir de chaque élément est (selon que vous allez à gauche ou à droite de celui-ci) :

2+max(8,5),4+max(5,9),6+max(9,3) = 10,13,15

C'est donc génial ; nous avons éliminé 2 lignes en les écrasant pour les remplacer par une seule ligne, ce qui réduit le problème à

     3
   7   4
10  13  15

Évidemment, on peut continuer à le répéter. En examinant la rangée suivante, le maximum que vous pouvez obtenir de chaque élément est

7+max(10,13),4+max(13,15) = 20,19

Et donc, à partir du haut, le maximum que vous pouvez obtenir c'est

3+max(20,19) = 23

QED.

Answer 4

En fait, il n'est pas nécessaire de commencer de bas en haut ; vous pouvez tout aussi bien commencer de haut en bas, à condition de le faire correctement.

La façon dont il fonctionne de bas en haut est mieux illustrée en prenant ce qui se passe à chaque niveau de la pyramide. Le chemin doit sûrement traverser chaque niveau à un moment donné.

    x
   x x
  x h x
 x y y x
x y y y x

Disons que c'est h . D'après la définition des chemins admissibles, le chemin ne peut que descendre dans le y -Ce problème est similaire à celui de l'original : si nous trouvons un chemin maximal à travers les endroits marqués, nous pouvons trouver un chemin qui ne soit pas trop long. y et le chemin maximal de tout le triangle passe en fait par h il suivra sûrement un chemin maximal dans y (si ce n'est pas le cas, vous pouvez échanger la partie du chemin dans le plus petit triangle et obtenir un meilleur chemin global).

Ainsi, si vous structurez votre algorithme de haut en bas en calculant le chemin maximal à partir du nœud actuel vers le bas, vous obtenez le résultat correct (c'est-à-dire la valeur du chemin maximal, à partir de laquelle vous pouvez facilement obtenir le chemin lui-même).

Cela prend O(N) (N étant le nombre de chiffres), car pour chaque endroit, il suffit de considérer deux chemins et d'utiliser les valeurs précalculées du niveau inférieur.

Pratiquement le même algorithme peut être mis en œuvre de manière descendante, en commençant par le haut et en effectuant une récursion vers le bas, à condition de mémoriser le résultat.

best_length(node)
{ 
  if(node is terminal)
    return value(node)
  int m = 0
  for(next : lower neighbors of node)
    m = max(best_length(next), m)
  return m + value(node);
}

Une autre possibilité de faire cela de haut en bas serait d'inverser le calcul. On commence par le haut, pour chaque nœud en considérant ses voisins supérieurs, et on obtient la longueur du chemin du haut se terminant dans ce nœud (au lieu du chemin allant de ce nœud vers la rangée du bas). À la fin, vous rassemblez les données de la rangée inférieure et vous avez terminé.

Answer 5

Adopter une approche ascendante élimine des chemins en allant uniquement du haut vers le bas ajoute des chemins potentiels.

Parce que vous éliminez les mauvais chemins plus rapidement, en faisant un en premier lieu la recherche devient la solution optimale. Une recherche en profondeur dans l'une ou l'autre direction est à la fois erronée (comme vous l'avez montré) et lente.