laissez-nous supposer que nous avons un arbre composé de n nœuds. La tâche consiste à trouver tous les chemins uniques les plus longs de l'arbre. Par exemple, si l'arbre ressemble à la suivante:
Alors il y a trois plus longues chemins uniques dans l'arbre: 1 - 2 - 3 - 4 - 5, 6 - 2 - 3 - 4 - 5 et 1 - 2 - 6.
Je veux trouver de manière programmée et stocker tous ces chemins de tels chemins pour un arbre donné. Une façon de le faire serait de calculer les chemins entre chaque paire de nœuds dans l'arbre, puis rejeter les chemins contenus dans n'importe quel autre chemin. Cependant, je cherche un moyen efficace de le faire. Mes questions sont les suivantes:
La raison pour laquelle je veux essayer de l'essayer est parce que j'essaie de résoudre ce problème: Knodes
6 Réponses :
Autant que je puisse comprendre, vous avez un arbre sans racine sélectionnée. Vos chemins admissibles sont les chemins qui ne permettent pas de visiter deux nœuds d'arbres (vous n'êtes pas autorisé à revenir). Et vous devez trouver tous ces chemins admissibles qui ne sont pas des sous-pathes d'un chemin admissible.
Donc, si j'ai bien compris, alors si un nœud n'a qu'un bord, que le chemin admissible soit démarrez ou arrêtez-vous à ce nœud. Si l'arborescence est connectée, vous pouvez obtenir de n'importe quel noeud à n'importe quel noeud par un chemin admissible.
Vous sélectionnez tous les nœuds avec un bord, appelez-le S. puis sélectionnez l'un de s et marchez l'ensemble de l'arbre entier qui enregistre les chemins vers les extrémités (chemin, pas la commande de marche). Ensuite, vous faites cela avec tous les autres articles de S et Supprimer des chemins dupliqués (ils peuvent être dans l'ordre inverse: comme à partir de 1: 1 - 2 - 6 et à partir de 6: 6 - 2 - 1).
Alors, ici, vous devez visiter tous les nœuds de l'arbre autant de fois que vous avez des feuilles dans l'arbre. La complexité dépend donc du facteur de ramification (dans le pire des cas, il est O (n ^ 2). Certaines optimisations peuvent réduire la quantité d'opérations, comme vous n'aurez pas à marcher dans l'arbre du dernier de S. < / p>
vous sélectionnez tous les nœuds avec un bord - qui s'appelle une feuille (dans un graphe non dirigé, une feuille est définie comme un sommet avec D (V) = 1, où d (.) est le degré ).
Je l'ai mentionné dans le dernier paragraphe. La raison pour laquelle je ne l'ai pas utilisée dans la description, que la question a été posée en termes d'arbres et généralement dans l'arborescence, le nœud racine ne compte pas comme feuille. Donc, dans cette situation, il ne serait pas clair que le nœud racine (s'il s'agit d'un nœud de degré 1) soit à s ou non.
La définition de root est un sommet où tous les nœuds sont accessibles de celui-ci. Cela n'a pas beaucoup de sens de parler d'une racine dans un graphique non dirigé, et surtout un arbre, car par définition - chaque noeud est une racine.
Je ne pense pas que cela mérite d'être discuté des définitions, il peut y avoir beaucoup d'entre eux en fonction des idées des auteurs mis dans la définition. Comme les nombres naturels peuvent inclure ou exclure 0 02, par exemple dans Wikipedia ("un graphique enraciné est un graphique dans lequel un sommet a été distingué comme une racine"). La définition fournie par vous a aussi beaucoup de sens. J'ai essayé d'écrire de cette façon, cela ne pouvait pas être mal compris. S'il est venu plus déroutant, la prochaine fois que je vais utiliser "feuille" dans cette situation.
dans cette image, les chemins les plus longs sont {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 3, 7}, {1, 2, 3, 8}, {1, 2, 3, 9}, {1, 2, 3, 10}
Pour arbre comme ceci stockant tous les chemins les plus longs vous coûtera O (n 2 )
Ce n'est pas correct. Stocker ces informations peut également être effectuée dans O (n). Vous pouvez représenter une voie par une concaténation de deux autres chemins. Donc, donc cela n'est pas une preuve qu'une meilleure classe de complexité n'est pas réalisable.
Pouvez-vous donner un exemple s'il vous plaît
Nous avons un chemin {1,2,3} nommé A . Ensuite, nous avons des chemins {3,4} nommé b4 , {3,5} nommé b5 et ainsi de suite . La solution est la solution concaténée {A, B4} , {A, B5} et ainsi de suite. Cette solution prend O (n) espace pour le chemin A . Un autre O (n) est utilisé pour les chemins B et un autre O (n) L'espace est utilisé pour les chemins concatérés. Laissant un total de O (n) espace.
Vous stockez des chemins pour que vous puissiez parcourir efficacement ces chemins de manière efficace (c'est-à-dire avec un tel stockage, vous ne pouvez pas arrêter le processus de calcul du coût O (N²). Ce que vous faites essentiellement, c'est stocker les chemins les plus longs de la forêt (c'est-à-dire une liste des arbres). Dans votre exemple A n'est qu'un chemin dans l'arborescence {1, 2, 3} . Donc, vous faites simplement transformer mon problème dans un autre problème. Si le nœud 1 avait deux autres enfants 1 ' et 1 ", alors vous deviez stocker le chemin {1', 1, 2, 3} & {1 ", 1, 2, 3} dans une autre liste. Maintenant, quels seront les chemins concatérés pour ce changement?
Le but est d'avoir une classe d'arbres où les solutions ne peuvent pas être codées avec moins de O (n ^ 2) espace. Je montre une telle classe d'arbres dans ma réponse. Il suffit de dire que vous êtes capable d'utiliser O (n ^ 2) L'espace des solutions de codage n'est pas utile, car des solutions utilisables uniquement O (n) peuvent toujours être Ballonné à utiliser O (n ^ 2) espace. Prouver l'autre moyen est le point ici.
Supposons que vous ayez un arbre binaire comme sur votre photo.
def leaf_paths(node, paths = [], stacks = {}, visited = set()):
visited.add(node)
if node.left is None and node.right is None:
for leaf, path in stacks.iteritems():
path.append(node)
paths.append(path[:])
stacks[node] = [node]
else:
for leaf, path in stacks.iteritems():
if len(path) > 1 and path[-2] == node:
path.pop()
else:
path.append(node)
if node.left and node.left not in visited:
leaf_paths(node.left, paths, stacks, visited)
elif node.right and node.right not in visited:
leaf_paths(node.right, paths, stacks, visited)
elif node.parent:
leaf_paths(node.parent, paths, stacks, visited)
return paths
for path in leaf_paths(root):
print [n.key for n in path]
Vous pouvez le faire dans (éditer: Temps non linéaire, quadratique). p> une sortie pour votre arbre sera: p>
[1, 2, 6] p>
[6, 2, 3, 4, 5] P>
[1, 2, 3, 4, 5] P>
BlockQuote> L'idée est de suivre toutes les feuilles visitées tout en parcourant un arbre. Et garder la pile de chemins pour chaque feuille. Donc, voici le compromis mémoire / performance. P> p>
Pourquoi l'ensemble visité devrait-il être nécessaire? Si vous commencez par la racine, le parent d'un nœud visité a déjà été visité au moment où le nœud est visité.
@Spacetrucker Nous visitons les nœuds parents jusqu'à trois fois pendant la traversée. C'est une traversée spéciale, pas comme dans / Pre / Post Commander Traversal. C'est un "voyageur" Traversal. Donc, vous devez visiter le noeud précédent pour aller juste après la gauche. Pour un arbre simple B ← a ← c Votre traversé devrait être "A-> B-> A-> C-> A". Vous pouvez optimiser la solution en commençant à la première feuille gauche et en terminant à la feuille de droite afin que vous fassiez moins de pas, mais vous aurez toujours besoin d'un ensemble visité.
@Spacetrucker J'ai utilisé visité surtout pour simplifier le code. Vous pouvez toujours vérifier où avez-vous eu une étape de récursion actuelle. Vous pouvez donc écrire un peu plus de code et jeter visite visité. L'idée est que si nous venions de droit, nous devrions retourner au parent autrement aller à l'enfant à droite (si elle existe)
Pourriez-vous s'il vous plaît élaborer plus sur la raison pour laquelle votre algorithme est linéaire? C'est loin d'être évident à cause de la récursion et de l'itération sur les piles.
@Spacetrucker ehm. On dirait que tu es absolument juste. Il n'est pas linéaire, O (n * l) ~ o (n ^ 2) :( Je n'ai pas pris en compte cette boucle de piles intérieures. Merci
@Spacetrucker Il y a une astuce avec la compression du chemin, de sorte que vous n'avez pas besoin de itérer sur toutes les piles, mais seuls spécifiques (chemins sont partagés entre les feuilles). Mais je ne peux pas dire si cela améliorera cet algorithme asymptotiquement
Un algorithme avec une complexité de temps ci-dessous Supposons un arbre binaire complet avec considère maintenant un arbre binaire presque complet avec pour le bit à l'index Comme nous l'avons déjà de statut qu'une solution d'arborescence avec Encodant maintenant chaque chiffre possible avec donc là-bas O (n ^ 2) peut n'existe que si toute solution pour un arbre avec N nœuds Peut être codé dans moins de O (n ^ 2) espace. n feuilles ( n = n journal n ). La solution au problème contiendra un chemin pour chaque ensemble de 2 feuilles. Cela signifie que la solution aura o (n ^ 2) éléments. Donc, pour ce cas, nous pouvons coder la solution comme des ensembles de feuilles de 2 éléments. M des feuilles, qui a été créée uniquement en supprimant arbitraire Feuilles d'un arbre binaire complet avec n feuilles. Lors de la comparaison de la solution de cet arborescence à celle de l'arbre binaire complet, les deux partagent un ensemble de chemins éventuellement vide. En fait, pour chaque sous-ensemble de chemins d'une solution d'un arbre binaire complet, il existera au moins un arbre binaire avec des feuilles M comme mentionné ci-dessus, contenant chaque solution d'un tel sous-ensemble. (Nous ignorons intentionnellement le fait qu'un arbre avec des feuilles m peut avoir encore plus de chemins dans la solution où au moins une partie des extrémités du chemin ne sont pas des feuilles de l'arbre binaire complet.) < P> Seule cette partie de la solution pour un arbre binaire avec m de feuilles sera codée par un numéro avec (n ^ 2) / 2 bits. L'index d'un peu dans ce numéro représente un élément dans la moitié supérieure droite d'une matrice avec des colonnes N et des lignes. n = 4 Ce serait: i sera défini si le chemin indéterminé ligne (i), colonne (i) est contenu dans la solution. m Les feuilles peuvent contenir n'importe quel sous-ensemble de la solution à l'arbre binaire complet. avec n> = m feuilles, chaque nombre binaire avec (n ^ 2) / 2 Les bits représenteront une solution pour un arbre avec M feuilles . (n ^ 2) / 2 bits avec moins de (n ^ 2) / 2 n'est pas possible. Nous avons donc montré que les solutions nécessitent au moins besoin O (n ^ 2) espace à représenter. Utilisation de n = n journal n d'en haut, nous donnons une condition d'espace d'au moins O (n ^ 2) . o (n ^ 2)
Prenons l'arbre qui ressemble à l'étoile avec Ensuite, vous avez La limite inférieure de la complexité ne peut pas être inférieure à O (n ^ 2). n nœuds et n-1 bords.
C (N-1, 2) Des chemins les plus longs uniques.
Mais un algorithme pourrait vérifier dans le temps O (n) , si l'arborescence est une étoile, puis écrivez la chaîne ordinaire c (n-1,2) comme solution temps constant. Donc, si vous n'exigez pas que pour une solution, tous les chemins doivent être exactement écrits avec les étiquettes de nœud, votre réponse ne prouve pas qu'il n'existe pas une meilleure solution.
Mais @bhoot dit: "Je veux trouver et stocker programmatiquement tous de tels chemins pour un arbre donné."
Oui, et la chaîne ordinaire c (n-1,2) stocke ces informations pour un arbre sous la forme d'une étoile si interprétée correctement. Ainsi, aucune information n'est perdue sur le stockage, pourquoi cela ne devrait-il pas être utilisé?
Je ne comprends pas, comment voudriez-vous générer des informations C (n-1, 2) des informations en moins que O (n ^ 2) complexité? Nous devrions tous les stocker. Je pense que @Bhoot l'a eu à l'esprit.
Je ne génère pas C (n-1,2) Informations mais seulement la chaîne ordinaire c (n-1,2) avec ses 8 caractères. L'OP ne définit pas ce qui devrait se passer avec les informations stockées plus tard, à l'exception de la mention de knodes. Donc, c'est parfaitement bien. Lorsque vous envisagez des requêtes si un chemin est contenu dans l'ensemble, que des tests contre C (n-1,2) est facile. Nous devons juste l'analyser et voir si les étiquettes de nœud en question sont dans la plage de n .
Dessine l'arbre. Soit V un sommet et p son parent. La longueur du chemin le plus long, y compris V mais non p = (hauteur de la sous-arbre gauche de V) + (hauteur du sous-arbre droit de V).
Le maximum sur tout V est le chemin le plus long du graphique. Vous pouvez calculer cela dans O (n):
Calculez d'abord toutes les hauteurs intermédiaires. Commencez aux feuilles et travaillez: (hauteur inférieure à V) = 1 + max (hauteur inférieure à gauche, hauteur en dessous de l'enfant droit)
Calculez ensuite la somme (hauteur de la sous-arbre gauche de V) + (hauteur du sous-arbre de droite de V) pour chaque sommet V et prenez le maximum. C'est la longueur du chemin le plus long dans le graphique.
Peut-être manquer le point, mais tous les chemins les plus longs ne sont-ils pas essentiellement tous les chemins de la racine (en supposant des arbres dirigés, comme le suggère une image) à toutes les feuilles? Cela peut être fait à l'aide de DFS avec du temps linéaire.
La photo est trompeuse. Nous avons des arbres non dirigés. Je vais remplacer la photo.
Que diriez-vous de BFS? Les sommets de la dernière couche sans bords sont des gagnants
On dirait que tout le chemin unique le plus long est surkillé pour votre problème.
@PHAMRUNG: Je veux juste penser au problème de la recherche de tous les chemins uniques en général. Je l'ai rencontrée deux fois cette semaine et je me demandais s'il est possible de calculer efficacement tous les chemins les plus longs uniques. J'ai été incapable de trouver une solution efficace.
@BHoot si le chemin est le plus long, alors comment peut-il y avoir plus d'une solution?
C'est un graphique ou un arbre binaire avec nœud root 3?
Donc, si le graphique n'est pas dirigé, pourquoi 6-2-3-4-5 n'est-il pas compté également? Pourquoi n'est-ce pas considéré comme unique?
@BHOOT Si les chemins sont uniques, il ne peut y avoir qu'un seul chemin le plus long en fonction de moi et par la manière dont les deux chemins que vous avez mentionnés ont le bord 1 à 2 courants, alors comment sont-ils uniques?
@Sumet Uniq! = Certains bords courants, UNIQ == tous les bords courants?
Vos questions sont trop claires
@amit: corrigé. Merci!
@ Vish4071: Pouvez-vous me laisser savoir dans quelle partie trouvez-vous difficile à comprendre? Je vais essayer de fournir une meilleure description.
Vous avez appelé
1 - 2 - 6 comme un chemin le plus long, alors qu'il n'est pas le plus long. On dirait que vous essayez de trouver tous les chemins de chaque des nœuds finaux. Tout chemin entre 1, 6 et 5 nœuds dans votre exemple. Ils ne sont pas plus longs.Comme l'a mentionné FL00R, il est totalement difficile de savoir ce que les moyens «les plus longs» dans ce contexte.
@Bhoot, ^ Ceci. Pourquoi 1-2-6 est-il le plus long chemin? Voulez-vous tous les chemins de tous les nœuds de feuilles à tous les autres nœuds de feuilles? Votre arbre est-il un arbre binaire? D'autres spécificités qui pourraient aider.
@ Vish4071: C'est unique. Il n'y a pas d'autre chemin qui contient des nœuds 1 - 2 - 6.
@Bhoot, 126 est unique, d'accord. Mais comment ça va le plus longtemps? Voir mon commentaire ci-dessus et répondez à toutes ces questions s'il vous plaît (si les réponses ci-dessous n'ont pas résolu votre problème, c'est-à-dire)
`@Bhoot Votre question n'est pas claire! Par exemple, vous n'expliquez pas la nature de votre graphique ou de ce que vous entendez par «plus long» ou «unique». Nous ne pouvons pas lire votre esprit. En outre, des exemples ne peuvent être une aide que pour confirmer la compréhension des mots disant ce qui se passe .
`@BHOOT Une définition d'un arbre est" un graphique non dirigé dans lequel deux sommets sont connectés Par exactement un chemin "alors peut-être que vous voulez dire quelque chose comme, avec cette définition, tous les chemins avec des nœuds d'extrémité de feuilles distincts? (Qui semble compatible avec votre algorithme proposé.)
Ce que vous proposez n'est pas une solution au problème que vous avez lié à, alors je pense que vous posez la mauvaise question
@Philipxy: L'objectif est de trouver cela compte tenu d'un ensemble de nœuds, existe-t-il un chemin dans lequel contient tous les nœuds de l'ensemble. À cette fin, j'essaie de résoudre le problème en stockant tous les «superpaths» possibles.
@Niklasb. Oui, il existe des moyens alternatifs de résoudre le problème. J'essaie de penser à savoir si nous pouvons le résoudre de cette manière. L'objectif de cette question est de penser à quoi sert la meilleure façon de stocker tous les chemins les plus longs uniques du graphique. La terminologie en question pourrait être un peu déroutante, mais je ne vois pas une meilleure façon de la mettre en avant. :)
@BHOOT: "L'objectif est de trouver cela compte tenu d'un ensemble de nœuds, existe-t-il un chemin dans lequel contient tous les nœuds de l'ensemble": c'est loin de votre question initiale en supposant que vous signiez "sous-ensemble de nœuds", la réponse est O (n): si le sous-ensemble contient plus de deux feuilles, la réponse est "non"; Si le sous-ensemble contient deux feuilles, calculez s'il existe un chemin entre eux en utilisant uniquement des nœuds dans le sous-ensemble, O (N); Les nœuds zéro ou un feuilles sont des cas triviaux.
Prenons l'arbre qui ressemble à l'étoile avec
n nœuds etn-1 bords. Ensuite, vous avezC (n-1, 2) des chemins les plus longs uniques. Donc la limite inférieure de la complexité est toujours O (n ^ 2)Astuce : Dessinez l'arbre. Soit V un sommet et p son parent. La longueur du chemin le plus long, y compris V mais non p = (hauteur de la sous-arbre gauche de V) + (hauteur du sous-arbre droit de V). Maximiser sur v.