Supposons que j'avais ce graphique acyclique dirigé (DAG) , où il y a un bord dirigé de Chaque nœud (autre que les nœuds de la rangée inférieure) aux deux nœuds ci-dessous:
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
4 Réponses :
Le meilleur algorithme serait de
open the file, set a counter to 0. read each line in the file. for every line you read, increment the counter. close the file. that counter is your answer.
Poids le plus grand? c'est complètement différent
Un tableau bidimensionnel fonctionnerait bien. Vous pouvez aborder cela en utilisant une première traversée d'une largeur et marquant chaque nœud visité avec la somme maximale du chemin de ce nœud.
Par exemple:
Lorsque les nœuds de feuilles sont marqués, rendez-vous rapidement à travers eux pour voir ce qui est maximal. Ensuite, vous commencez en arrière en comparant le poids du nœud actuel, le poids des nœuds parents et le poids des bords.
Je représenterais ce triangle avec un vecteur de vecteurs de Démarrez à la rangée inférieure et comparez chaque paire de nombres ajoncé. Prenez le plus grand et ajoutez-le au nombre au-dessus de la paire: Travaillez votre chemin vers le haut et lorsque vous avez terminé, la pointe du triangle contiendra la plus grande somme. int s.
Cette solution de programmation dynamique est simple et rapide. C'est comme ça que j'ai résolu le projet Euler # 18 et # 67.
Ne devrait-il pas être lu «3» au lieu de «11» dans le premier résultat intermédiaire?
SPOILERS Une façon dont vous pourrait résoudre le problème consiste à transformer les données en arbre (graphique en réalité) et à écrire un algorithme récursif qui trouvera le chemin maximum à travers l'arborescence en réduisant l'arbre en petits sous-arbres (jusqu'à ce que vous ayez un arbre avec un seul nœud) et commencer à aller à partir de là. J'aime beaucoup les algorithmes récursives et travailler avec des arbres, je suis donc allé de l'avant et j'ai écrit un programme pour le faire: IT imprimé 7 -> 3 -> 8 -> 7 -> 5
chemin ajouté jusqu'à 30
Cette solution est trop inefficace (complexité exponentielle contre linéaire).
@jpalecek lequel est linéaire? De plus, ce n'est pas trop inefficace pour moi et il n'y avait aucune exigence d'efficacité :) Le programme fonctionne plus rapidement que je ne peux clignoter. Je viens de le faire pour m'amuser quand même de montrer un autre moyen, et ce problème est juste pour le plaisir.
La meilleure réponse votée ( Stackoverflow.com/a/9154380/51831 ) est linéaire, ainsi que toutes les réponses sur le Projet Euler N ° 18 Question ( Stackoverflow.com/Questtions/8002252/ELLER- Projet-18-Appoa Ch ). Est-ce qu'il court plus vite que vous ne pouvez clignoter sur des arbres de hauteur 30? Vous pouvez coder ce que vous voulez pour vous amuser, mais ce n'est pas quelque chose qu'un professionnel devrait accepter.
Et BTW, avec une petite torsion, votre solution serait également linéaire. Qui est un autre point contre accepter une solution exponentielle.
@jpalecek Je ne l'ai pas testé sur des arbres de hauteur 30 mais je n'ai pas besoin de parce que cela n'est pas utilisé sur les arbres de hauteur trente. Pardonne-moi, mais je n'ai pas lu où il était un professionnel et la solution à son problème entrait dans un produit commercial. Je pense que votre bowvote est vraiment inutile. Vous dites «Vous pouvez coder ce que vous voulez pour vous amuser», mais ce n'est pas tout ce qui est pour le plaisir? Je pense que vous prenez cela trop au sérieux.
Seth, l'OP n'a pas dit qu'il «le fait juste pour le plaisir», et il n'a pas dit qu'il l'utilisait sur des arbres de hauteur <30 ans, il est fort probable qu'il utilisera des arbres plus grands. L'OP a également demandé "quel algorithme serait le mieux" et, malheureusement, une solution exponentielle serait proche de l'inutile dans la plupart des scénarios, c'est pourquoi le vôtre n'est pas une bonne réponse à la question donnée.
Qu'entendez-vous par «chemin maximum»? Une traversée de la racine à un nœud de feuille qui rencontre les nœuds les plus intermédiaires?
... le chemin avec la somme totale maximale?
@Huntermcmillen apparemment le chemin à travers lequel les chiffres s'additionnent à la plus grande valeur
Ce que je voulais dire était le plus grand poids. 7,3,8,7,5 donne le plus grand poids. Mal tomber au poids.
@Sethcarnegie La question est confuse car l'OP énumère une trajectoire maximale de "7, 3, 8, 7, 5" qui est longueur 5, mais tous les autres trajets de la racine à une feuille sont la même longueur
@Huntermcmillen non, il voulait dire que
7, 3, 8, 7, 5 Tous additionnent à un plus grand nombre que la somme des nombres d'un autre chemin à travers l'arbreDupliqué possible de Projet Euler # 18 Approche
FWIW, ce graphique n'est pas un arbre. Un nœud d'arbre n'a qu'un seul parent. Ce type de structure s'appelle un graphique acyclique direct: direct car chaque bord a une direction et acyclique car il n'y a aucun moyen de revenir à un nœud.