Minimisation cheminement externe graphe

Cere · September 2021

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.

AlainLyon · September 2021

Prendre pour racine $x_1$ le sommet de plus grand poids.
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.

Cere · September 2021

Bonsoir et merci de ta réponse.
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.

AlainLyon · September 2021

D'accord j'avais compris "tous les noeuds". C'est ce que sous-entend la formulation. S'il s'agit seulement de noeuds externes alors oui cela se ramène à un simplexe en nombre entiers : pour une classe de tels problèmes il existe des cas où la complexité est polynomiale voir ce lien sur WikipédiA

AlainLyon · September 2021

Si le théorème de Lenstra ne peut pas s'appliquer alors il faut trouver une heuristique. Il y a une méthode dont je me souviens et qui est appelée "Branch and Bound". Grosso modo ayant trouvé la racine (heurisitique : le sommet de plus grand poids) il faut descendre l'arbre en éliminant, par une heuristique (i.e. un critère suffisant mais forcément nécessaire), à chaque profondeur d'un noeud interne l'arbre des successeurs gauche ou droit, à la manière dont réfléchissent les joueurs d'échecs qui éliminent d'emblée un coup faible éliminant des pans entiers de l'arbre des combinaisons de coups. Les méthodes "Branch and Bound" (brancher et borner) conduisent souvent à des algorithmes polynomiaux. Je suggère: à chaque étape mettre à gauche le descendant de plus grands poids, à droite celui de poids suivant (bound) et descendre à droite (branch), l'algorithme semble récursif et Il faut alors prouver que cette heuristique conduit à une complexité polynomiale....et à l'arbre minimum

Minimisation cheminement externe graphe

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 8