Minimisation cheminement externe graphe
Bonjour
Voici l'énoncé de l'exercice qui me pose problème.
Soit $X$ un ensemble fini non vide muni d'une fonction poids $w$ à valeurs positives et soit $\mathcal{A}$ la classe des arbres binaires dont $X$ est l'ensemble de nœuds externes.
Donner un algorithme de complexité polynomiale de calcul d'un arbre $A \in \mathcal{A}$ qui minimise la longueur de cheminement externe de $A$ pondérée par $w$, i.e., la quantité
$$
\sum_{x \in X} w(x) p_{A}(x),
$$ où $p_{A}(x)$ est la profondeur du nœud $x$ dans l'arbre $A$.
Auriez-vous des idées d'algorithmes qui pourraient convenir ou bien juste des pistes ?
Les seuls idées qui me viennent en tête sont soit des algorithmes non polynomiaux, soit ne donnent pas une solution minimale.
Merci d'avance.
Voici l'énoncé de l'exercice qui me pose problème.
Soit $X$ un ensemble fini non vide muni d'une fonction poids $w$ à valeurs positives et soit $\mathcal{A}$ la classe des arbres binaires dont $X$ est l'ensemble de nœuds externes.
Donner un algorithme de complexité polynomiale de calcul d'un arbre $A \in \mathcal{A}$ qui minimise la longueur de cheminement externe de $A$ pondérée par $w$, i.e., la quantité
$$
\sum_{x \in X} w(x) p_{A}(x),
$$ où $p_{A}(x)$ est la profondeur du nœud $x$ dans l'arbre $A$.
Auriez-vous des idées d'algorithmes qui pourraient convenir ou bien juste des pistes ?
Les seuls idées qui me viennent en tête sont soit des algorithmes non polynomiaux, soit ne donnent pas une solution minimale.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Choisir les deux successeurs parmi les deux sommets de plus grand poids
etc...
Cette partie est linéaire si suppose, au préalable, de trier les sommets par poids décroissant ...ton pb se ramène à trouver des algos de tris polynomiaux ...et cela n'en manque pas dans tous les bouquins pour débuter l'informatique.
Je crois que tu n'as pas compris le problème, les éléments de $X$ sont des nœuds externes, autrement dit des feuilles. Un éléments de $X$ ne peut donc pas être la racine de l'arbre, ni un nœud interne.
Les nœuds internes n'ont d'ailleurs eux aucun poids.
Ou bien alors c'est moi qui n'ai pas compris.
Pour moi, cela ressemble à un problème de programmation linéaire, se résolvant avec un algorithme type simplexe et non pas un simple tri.