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'arbre qui minimise la longueur du chemin le plus long de v à tout autre nœud.Centre de recherche de l'arbre
alors comment trouver le centre de l'arbre? Est-ce qu'il peut y avoir seulement un centre ou plus?
Si quelqu'un peut me donner un bon algorithme pour cela, je peux avoir une idée sur la façon dont je peux intégrer mon programme.
Considérons un arbre avec deux nœuds? Quel est le centre? L'un ou l'autre suffira, un arbre peut avoir plus d'un centre. Maintenant, pensez à ce que signifie être le centre. Si toutes les branches ont la même hauteur, le centre est la racine (tous les chemins passent par la racine). Si les branches sont de hauteurs différentes, le centre doit être soit la racine, soit la branche avec la plus grande hauteur, sinon le chemin maximum est plus grand que la hauteur de la plus grande branche et la racine serait un meilleur choix. Maintenant, jusqu'où devons-nous regarder la plus grande branche? La moitié de la différence de hauteur entre la branche la plus haute (de la racine) et la branche la plus haute suivante (si la différence est d'au plus 1, la racine suffira). Pourquoi, parce que nous descendons la branche la plus haute d'un niveau, nous allongons le chemin vers le nœud le plus profond de la branche la plus haute suivante et réduisons la distance jusqu'au nœud le plus profond de la branche actuelle. Finalement, ils seront égaux quand vous avez traversé la moitié de la différence de profondeur. Maintenant que nous descendons la plus grande branche, nous devons simplement choisir à chaque niveau la plus grande sous-branche. Si plus d'un a la même hauteur, nous en choisissons un arbitrairement. Essentiellement, ce que vous faites est de trouver le plus long chemin dans le graphique, qui est la distance entre la branche la plus grande de l'arbre et la branche la plus haute suivante, puis de trouver le nœud du milieu sur cette branche. Parce qu'il peut y avoir plusieurs chemins de la même longueur que le chemin le plus long et la longueur du chemin le plus long peut être pair, vous avez plusieurs centres possibles.
Plutôt que de faire ce problème de devoirs pour vous, je vais vous demander par le processus de pensée qui obtient la réponse ...
1) Que feriez-vous avec le abc graphique (trois sommets, deux bords, et définitivement acyclique)? Imaginez un instant que vous ayez à mettre des étiquettes sur certains des sommets, vous savez que vous obtiendrez le minimum du plus long chemin sur le sommet «central». (b, avec éventuellement l'étiquette "1") Mais faire cela en une étape nécessite des pouvoirs psychiques. Alors demandez-vous ce que b est à 1 pas de. Si le plus long chemin vers b est 1, et que nous avons reculé d'un pas le long de ce chemin, quelle est la longueur de notre chemin jusqu'ici? (chemin le plus long = 1, -1 pour le retour en arrière, Aha: 0). Donc ça doit être l'étiquette pour les feuilles.
2) Qu'est-ce que cela suggère comme première coupure pour un algorithme? Marquer les feuilles "0", marquer leurs amont "1", marquer leurs amont "2" et ainsi de suite. Marcher à partir des feuilles et compter la distance que nous allons ...
3) Umm ... Nous avons un problème avec le graphique a-b-c-d. (A partir de maintenant, un sommet étiqueté sera remplacé par son étiquette.) L'é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" ... Manipuler ceux-ci dans l'ordre inverse ...
En 0-b-1, si on étend le chemin de b à gauche, on obtient un chemin de longueur 1. Si nous étendons le chemin de b à droite, nous obtenons 2. Nous voulons suivre "la longueur du plus long chemin de v à tout autre nœud", donc nous voulons garder une trace du chemin le plus long vers b. Cela signifie que nous marquons b avec un "2".
0-b-1 -> 0-2-1
Dans 0-b-c-0, l'ordinateur ne fait pas simultanément mise à jour b et c. Il met à jour l'un d'eux, en donnant 0-1-c-0 ou 0-b-1-0, et la mise à jour suivante donne 0-1-2-0 ou 0-2-1-0. Les deux b et c sont les "centres" de ce graphe puisque chacun d'entre eux répond à la demande "le nœud v dans l'arbre qui minimise la longueur du chemin le plus long de v à tout autre nœud." Ceci conduit à une autre observation: Le résultat du calcul n'est pas d'étiqueter un graphe, c'est de trouver le dernier sommet que nous étiquetons et/ou le sommet qui se termine par le plus grand label. (Il est possible que nous ne trouvions pas un bon moyen de commander des étiquettes, donc nous finirons par avoir besoin de trouver le maximum à la fin ou peut-être nous le ferons.)
4) Alors maintenant nous avons quelque chose comme: Faire deux copies du graphique - la copie étiquetée et la copie de burn-down. Le premier va stocker les étiquettes et c'est celui qui aura la réponse finale. La copie de gravure deviendra de plus en plus petite au fur et à mesure que nous en supprimerons des sommets non étiquetés (pour trouver de nouveaux sommets étiquetables). (Il existe d'autres façons d'organiser cela pour que seule une copie du graphique est utilisé lorsque vous arrivez à la fin de comprendre cette réponse, vous devriez trouver un moyen de réduire ces déchets..) Aperçu:
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
5) Si vous regardez réellement cette course, vous remarquerez plusieurs possibilités de raccourcis. Y compris le remplacement de la recherche sur la dernière ligne du contour avec une méthode beaucoup plus rapide pour reconnaître la réponse.
Et maintenant pour des astuces de stratégie générale pour les problèmes d'algorithme:
* Faites quelques petits exemples à la main. Si vous ne comprenez pas comment faire les petits cas, vous ne pouvez pas sauter directement et dire à l'ordinateur comment faire les gros cas. * Si l'une des étapes ci-dessus semblait non motivée ou totalement opaque, vous devrez étudier beaucoup, beaucoup plus difficile à bien faire en informatique. Il est peut-être la science informatique ne vous appartient pas ...
Il y a deux approches pour le faire (les deux pistes en même temps):
Sélectionnez un sommet v1 sur votre arbre. Exécutez BFS à partir de ce sommet. Le dernier sommet (v2) que vous allez suivre sera le dernier sommet de v1. Exécutez maintenant un autre BFS, cette fois à partir du sommet v2 et obtenez le dernier sommet v3.
Le chemin de v2 à v3 est le diamètre de l'arbre et votre centre se trouve quelque part dessus. Plus précisément, il se trouve au milieu de celui-ci. Si le chemin a 2n + 1 points, il y aura seulement 1 centre (dans la position n + 1). Si le chemin a 2n points, il y aura deux centres aux positions n et n + 1.
Vous n'utilisez que 2 appels BFS qui s'exécutent en 2 * O(V) heure.
Si le point exactement au milieu n'existe pas, comment pourrions-nous choisir? Je veux dire, si le plus long chemin est a-b-c, a-b a la longueur 1, et b-c a la longueur 2?Ou un exemple plus complexe? – cnhk
Choisissez-en un de manière arbitraire, si vous avez simplement besoin d'un nœud qui se qualifie, ou construisez un ensemble central, si vous avez besoin de tout ce qui est admissible. – tvanfosson