J'ai une question qui fait partie de mon programme.
Pour un arbre T = (V, E), nous devons trouver le nœud V dans l'arborescence qui minimise la longueur du chemin le plus long de V sur tout autre nœud.
Alors, comment nous trouvons le centre de l'arbre? Y a-t-il seulement un seul centre ou plus?
Si quelqu'un peut me donner un bon algorithme pour cela afin que je puisse obtenir l'idée sur la manière dont je peux rentrer dans mon programme.
3 Réponses :
Considérez un arbre avec deux nœuds? Quel est le centre? L'un ou l'autre suffira, Ergo Un arbre peut avoir plus d'un centre.
Maintenant, pensez à ce que cela signifie être le centre. Si toutes les branches ont la même hauteur, le centre est la racine (tous les chemins traversent la racine). Si les branches sont de différentes hauteurs, le centre doit être la racine ou dans la branche avec la plus grande hauteur, sinon le chemin maximum est supérieur à la hauteur de la branche la plus haute et la racine serait un meilleur choix. Maintenant, à quelle distance la plus haute branche est-elle nécessaire pour regarder? La moitié de la différence de hauteur entre la branche la plus haute (de la racine) et la prochaine branche la plus haute (si la différence est au maximum 1, la racine suffira). Pourquoi, parce que lorsque nous descendons la plus grande succursale d'un niveau, nous allongeons le chemin du nœud le plus profond de la plus grande branche la plus grande la plus grande et réduisant la distance au nœud le plus profond de la branche actuelle par une. Finalement, ils seront égaux lorsque vous avez traversé la moitié de la différence de profondeur. Au moment où nous descendons la plus grande succursale, nous devons simplement choisir à chaque niveau la sous-branche la plus haute. Si plus d'un ait la même hauteur, nous en choisissons simplement une arbitraire.
Essentiellement, ce que vous faites est de trouver le chemin le plus long dans le graphique, qui est la distance entre la branche la plus haute de l'arborescence et la prochaine branche la plus haute, puis trouvez le nœud central sur cette branche. Parce qu'il peut y avoir plusieurs chemins de même longueur que le chemin le plus long et la longueur du chemin le plus long peut être même, vous avez plusieurs centres possibles.
Si le point moyen exactement n'existe pas, comment pourrions-nous choisir? Je veux dire, si le moyen le plus long est A-B-C, A-B a la longueur 1 et B-C a la longueur 2? Ou un exemple plus complexe?
Choisissez une arbitraire, si vous avez simplement besoin d'un nœud qui qualifie ou construit un ensemble de centres, si vous avez besoin de tout ce qui vous qualifie.
Plutôt que de faire ce problème de devoirs pour vous, je vais vous demander à travers le processus de pensée qui obtient la réponse ...
1) Que feriez-vous avec le graphique ABC (trois sommets, deux bords, et définitivement acyclique)? Imaginez un instant que vous devez mettre des étiquettes sur certains sommets, vous savez que vous allez obtenir le minimum de la plus longue trajectoire du sommet «Centre». (B, avec éventuelle label "1"), mais ce faisant en une étape nécessite des pouvoirs psychiques. Alors, demandez-vous ce que B est 1 à deux pas. Si le plus long chemin de B est 1, et nous venons d'entrer un pas à l'envers le long de ce chemin, quelle est la longueur de notre chemin jusqu'à présent? (chemin le plus long = 1, -1 pour le dos d'une étape. AHA: 0). Donc, cela doit être l'étiquette des feuilles. P>
2) Qu'est-ce que cela suggère comme une première coupe pour un algorithme? Marquez les feuilles "0", marquent leurs amont "1", marquent leurs amont "2" et ainsi de suite. En marchant des feuilles et comptant la distance comme nous allons ... p>
3) umm ... nous avons un problème avec le graphique A-B-C-D. (À partir de maintenant, un sommet étiqueté sera remplacé par son étiquette.) Étiquetage des feuilles "0" donne 0-bc-0 ... Nous ne pouvons pas obtenir deux centres ... Heck, que faisons-nous dans le plus simple condition 0-b-1? Nous voulons étiqueter B avec "1" et "2" ... Poignez-les dans l'ordre inverse ... p>
en 0-B-1, si nous étendons le chemin de B laissé par un, Nous obtenons un chemin de longueur 1. Si nous étendons le chemin de B à droite, nous obtenons 2. Nous voulons suivre "la longueur du chemin le plus long de V à tout autre nœud", nous souhaitons donc garder une trace du chemin le plus long à b. Cela signifie que nous marquons B avec un "2". P> in 0-bc-0, l'ordinateur ne simultanément em> mise à jour b et c. Il met à jour l'un d'eux, donnant le 0-1-C-0 ou 0-B-1-0, et la mise à jour suivante donne 0-2-0 ou 0-2-1-0. B et C sont tous deux "Centre" de ce graphique car chacun d'entre eux répond à la demande "Le nœud V dans l'arborescence qui minimise la longueur du chemin le plus long de V à tout autre nœud." (Cette longueur est 2.) P> Ceci conduit à une autre observation: le résultat du calcul ne doit pas étiqueter un graphique, il est de trouver le dernier sommet que nous nous étiquetons et / ou le sommet qui finit par le plus grande étiquette. (Il est possible que nous ne trouvions pas de bonne façon de commander des étiquettes, nous allons donc vous retrouver à trouver le maximum à la fin. Ou peut-être que nous le savons.) P> 4) Maintenant, nous avons quelque chose comme: faites deux copies du graphique - la copie étiquetée et la copie de la combustion. Le premier rangera les étiquettes et c'est celui qui aura la réponse finale dedans. La copie de brûlage deviendra plus petite et plus petite lorsque nous supprimons les sommets non étiquetés (pour trouver de nouveaux sommets marquables). (Il existe d'autres moyens d'organiser cela afin que seule une copie du graphique soit utilisée. Lorsque vous arrivez à la fin de la compréhension de cette réponse, vous devriez trouver un moyen de réduire ces déchets.) Contour: P>
label = 0
while the burndown graph is nonempty
collect all the leaves in the burndown-graph into the set X
for each leaf in the set X
if the leaf does not have a label
set the leaf's label (to the current value of label)
delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
label = label+1
find the vertex with the largest label and return it
Il y a deux approches pour le faire (les deux couronnes en même temps):
Sélectionnez n'importe quel sommet Le chemin de Vous n'utilisez que 2 appels BFS qui exécute dans V1 sur votre arbre. Exécutez BFS de ce sommet. Le dernier sommet ( v2 ) que vous procéderez sera le sommet le plus éloigné de v1 . Organisez maintenant un autre BFS, cette fois de Vertex v2 et obtenez le dernier sommet v3 .
v2 à v3 est le diamètre de l'arborescence et votre centre se situe quelque part dessus. Plus précisément, il se situe au milieu de cela. Si le chemin a 2N + 1 points, il n'y aura que 1 centre (dans la position n + 1 ). Si le chemin a 2n , il y aura deux centres aux positions n et n + 1 . .
2 * O (v) heure.
Vous ne pouvez pas déterminer si v1 et v2 a du parent en commun. Vous prenez un sommet et prenez ses enfants. Ensuite, vous trouvez le chemin le plus long à partir de chacun de leurs enfants séparément en utilisant BFS et prenez les deux chemins les plus longs. Enfin, prenez le point central du chemin d'une feuille à l'autre.