Calculez le chemin le plus long entre deux nœuds. dans l'exemple d'arbre binaire ci-dessous, il est C'est ce que j'ai maintenant et pour l'arbre donné Il suffit de retourner 0. Je crois que je manque un concept clé quelque part ... mon cerveau devient fou quand j'essaie de suivre le flux d'exécution ...
Le chemin est dans une arche.
La signature de la méthode est la suivante: 
Suis-je raison en disant que, en trouvant le chemin le plus long parmi la racine, ses nœuds de gauche et de droite puis recueille sur ses nœuds de gauche et de droite les transmettent le chemin le plus long de l'invocation de la méthode précédente et enfin (quand?) Retournez le chemin le plus long, je Je ne suis pas certain de savoir comment vous allez le retourner ...
9 Réponses :
Peut-être que c'est aussi simple: c'est plus compliqué que celui qui pourrait penser à première vue. Considérons l'arborescence suivante: Dans ce cas, le nœud racine n'est même pas dans le chemin le plus long ( Donc, ce que vous devez faire est ce que vous devez faire est ce que vous devez faire est ce qui suit: Pour chaque nœud puis décidez, quelle combinaison maximise la longueur du chemin: Donc, je ferais un petit piratage et que chaque nœud ne renvoie pas juste un seul A-7-4-2-5-8- b ). n , vous devez calculer ce qui suit:
l )
r )
l )
r )
l + r + 2 , c'est-à-dire d'un sous-path dans le sous-arbre de gauche au nœud actuel et du nœud actuel à travers un sous-path dans le sous-arbre droit
l , c'est-à-dire juste prendre la sous-arbre de gauche et exclure le nœud actuel (et donc le sous-arbre à droite) du chemin
r , c'est-à-dire juste prendre le sous-arbre de droite et exclure le nœud actuel (et donc laissé sous-arbre) du chemin
int , mais un triple d'entiers contenant (l + r + 2, l, r) . L'appelant doit alors décider de ce qu'il faut faire avec ce résultat selon les règles ci-dessus.
Merci, mais j'ai essayé et ça retourne juste zéro. Quant à moi oublier d'ajouter le retour, je l'ai ajouté et il a enregistré 4, mais cela ne représente que la voûte s'étendant du nœud racine ... Autres arches plus longtemps qu'il n'était simplement ignoré.
En fait, le chemin le plus long est de 6 (par exemple: A-7-4-2-5-8-B). C'est un bon exemple, cependant.
@Daniel Hmmm comme je l'ai compris que le chemin est de la forme d'une arche (à l'envers V).
@timenomad: Vous devrez peut-être demander des éclaircissements à votre instructeur. 9-7-4-2-5-8-B est toujours "une arche" pour moi. Voir aussi: en.wikipedia.org/wiki/path_(Graph_Theory)
Pourquoi avons-nous besoin l et r ? Je ne suis pas capable de penser à un cas d'angle où l + r + 2 ne fera pas le tour.
Aussi pourquoi est-ce l + r + 2 ? Ne devrait-il pas être l + r + 1 ? Pour le nœud 2 L est 3 (4-7-a / 9) et R est 3 (5-8-B) de sorte que la longueur sera 3 + 3 + 1 [pour noeud racine] ?
Un algorithme correct est:
Cet algorithme fonctionnera certainement et vous n'êtes pas limité aux arbres binaires non plus. Je ne suis pas sûr de votre algorithme:
Je suis juste en disant que, en trouvant le chemin le plus long parmi la racine, ses nœuds de gauche et de droite, puis recueillent sur ses nœuds de gauche et de droite qui leur transmet le plus long chemin de l'invocation de la méthode précédente et enfin (quand ???) Retourner Le chemin le plus long, je ne suis pas certain de la façon dont vous allez le retourner ...
Parce que je ne comprends pas ce que vous décrivez exactement. Pouvez-vous le travailler à la main sur un exemple ou essayer de mieux l'expliquer? De cette façon, vous pourriez avoir une meilleure aide à comprendre si c'est correct ou non.
Vous semblez essayer d'une mise en œuvre récursive de la même chose simplement simplifiée pour les arbres binaires. Votre code semble plutôt compliqué pour ce problème cependant. Vérifiez la discussion ici pour une implémentation plus simple.
En ce qui concerne la baisse ne se limite pas aux arbres binaires: consultez: en.wikipedia.org/wiki/longest_path_problem < / a> Cet étage, que le problème (au moins pour les graphiques arbitraires) est NP-complet.
@Phimuemue - Oui, je veux dire tant que le graphique est toujours un arbre.
+1: Ceci trouve correctement le chemin le plus long dans un arbre non dirigé (je suppose que c'est aussi le diamètre en cas d'arbres).
1. Trouver une boucle. 2. Entrez-le. 3. ... 4. Bénéfice!
1. Trouvez une boucle dans un arbre. 2. Vendre une arbre incroyable avec des boucles aux théoriciens de Newbie Graph. 3. Bénéfice.
Je pense que vous êtes surcharge des choses.
Pensez au chemin le plus long qui traverse le nœud N et ne mène pas au parent de n. Quelle est la relation entre la longueur de ce chemin et les hauteurs des deux sous-groupes reliés à N?
Après avoir compris cela, vérifiez l'arborescence de raisonnement récursivement comme celui-ci:
Le chemin le plus long pour un sous-arbre avec la racine N est le chemin le plus long des trois suivants:
Et si, pour chaque nœud pour chaque noeud de terminal (nœuds ayant maintenant, le H de chaque nœud et f ( (vous devez déterminer ce qui remplace les deux placements «??». Il y a des choix qui font de ce travail de stratégie. Je l'ai testé personnellement.) alors, Vous devez être capable d'écrire des implémentations récursives de F et h pour faire fonctionner ce code; Cependant, cette solution est terriblement inefficace. Son but est juste de comprendre le calcul. Pour améliorer l'efficacité, vous pouvez utiliser Mémoisation ou convertir ceci en un calcul non récursif utilisant des piles. n , votre objectif était de calculer ces deux nombres:
n ): la longueur du chemin le plus long dans l'arbre enraciné à n
n ): la hauteur de l'arbre enracinée à n .
null nœuds gauche et droit), il est évident que F et H sont tous les deux 0. n est:
n.left et n.right sont les deux null
n.left ) Si seulement n.left est non- null
n.right ) Si seulement n.right est non- null
n.left ), h ( n.right )) Si les deux n.left et et n.right ne sont pas- null
n ) est:
n.left et n.right sont les deux null
n.left ), h ( n )) si seulement n.left est non- null
n.right est non- null
n.left et n.right sont non- null
LongestPath (nœud n) est juste f ( n ):
Eh bien, Umm si j'ai bien compris votre question correctement, voici ma solution [mais en C ++ (je suis désolé)]:
Voici ma solution récursive en C ++:
int longest_dis(Node* root) {
int height1, height2;
if( root==NULL)
return 0;
if( root->left == NULL ) && ( root->right == NULL )
return 0;
height1 = height(root->left); // height(Node* node) returns the height of a tree rooted at node
height2 = height(root->right);
if( root->left != NULL ) && ( root->right == NULL )
return max(height1+1, longest_dis(root->left) );
if( root->left == NULL ) && ( root->right != NULL )
return max(height2+1, longest_dis(root->right) );
return max(height1+height2+2, longest_dis(root->left), longestdis(root->right) );
}
public int longestPath() {
int[] result = longestPath(root);
return result[0] > result[1] ? result[0] : result[1];
}
// int[] {self-contained, root-to-leaf}
private int[] longestPath(BinaryTreeNode n) {
if (n == null) {
return new int[] { 0, 0 };
}
int[] left = longestPath(n.left);
int[] right = longestPath(n.right);
return new int[] { Util.max(left[0], right[0], left[1] + right[1] + 1),
Util.max(left[1], right[1]) + 1 };
}
Mise en œuvre simple:
int maxDepth(Node root) {
if(root == null) {
return 0;
} else {
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
return ldepth>rdepth ? ldepth+1 : rdepth+1;
}
}
int longestPath(Node root)
{
if (root == null)
return 0;
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
int lLongPath = longestPath(root.left);
int rLongPath = longestPath(root.right);
return max(ldepth + rdepth + 1, max(lLongPath, rLongPath));
}
Ce serait O (n ^ 2). Il devrait y avoir une meilleure solution de O (n)
Prendre en compte @Phimuemue Exemple et @IVLAD Solution, j'ai décidé de vérifier moi-même, alors voici ma mise en œuvre de la solution @IVLAD en Python:
def longestPath(graph,start, path=[]):
nodes = {}
path=path+[start]
for node in graph[start]:
if node not in path:
deepestNode,maxdepth,maxpath = longestPath(graph,node,path)
nodes[node] = (deepestNode,maxdepth,maxpath)
maxdepth = -1
deepestNode = start
maxpath = []
for k,v in nodes.iteritems():
if v[1] > maxdepth:
deepestNode = v[0]
maxdepth = v[1]
maxpath = v[2]
return deepestNode,maxdepth +1,maxpath+[start]
if __name__ == '__main__':
graph = { '1' : ['2','3'],
'2' : ['1','4','5'],
'3' : ['1'],
'4' : ['2','6','7'],
'5' : ['2','8'],
'6' : ['4'],
'7' : ['4','9','a'],
'8' : ['5','b'],
'9' : ['7'],
'a' : ['7'],
'b' : ['8']
}
"""
1
/ \
2 3
/ \
4 5
/ \ \
6 7 8
/ \ \
9 a b
"""
deepestNode,maxdepth,maxpath = longestPath(graph,'1')
print longestPath(graph, deepestNode)
>>> ('9', 6, ['9', '7', '4', '2', '5', '8', 'b'])
Comment gérez-vous le cas où l'arbre binaire est essentiellement une liste liée? Par exemple, le 2-3-13 (13 est la racine 3 à gauche de 13 et 2 est laissé de 3). Si le résultat soit 2?