Remove ads

En algorithmique, le problème de l'arbre de Steiner est un problème d'optimisation combinatoire. Il porte le nom du mathématicien Jakob Steiner. Ce problème est proche du problème de l'arbre couvrant minimal et a des applications en conception de réseaux, notamment les circuits électroniques et les télécommunications.

Thumb
Solution pour trois points. Le point de Steiner est au centre des trois autres points (il n'y a pas de connexion directe entre A, B et C).
Thumb
Solution pour quatre points. Dans cet arbre, il y a deux points de Steiner : et
Remove ads

Définitions

Il existe plusieurs variantes du problème.

Définition générale : espace métrique

Dans un espace métrique, étant donné un ensemble de points P, un arbre pour P est un réseau (c'est-à-dire un ensemble de chemins connectés) tel que tous les points soient reliés, et un arbre est dit de Steiner si la longueur totale du réseau est minimale[1].

Définition géométrique : espace euclidien

Dans la variante euclidienne du problème, l'espace métrique est un espace euclidien.

Définition d'optimisation combinatoire : graphes

Le cadre le plus classique en optimisation combinatoire est le suivant : étant donné un graphe G, dont les arêtes ont des poids, et un sous-ensemble S de sommets de G, trouver un ensemble d'arêtes de poids minimal tel que le sous-graphe induit soit connexe et contienne tous les sommets de S[2].

Remove ads

Propriétés du problème d'optimisation combinatoire

Comparaison avec le problème de l'arbre couvrant minimal

Dans les deux problèmes, étant donné un ensemble V de sommets, il s'agit de trouver un arbre A de coût minimal reliant tous les sommets de V (où le coût de l'arbre est défini comme la somme du coût de ses arêtes). Contrairement au problème de l'arbre couvrant minimal où tous les sommets de l'arbre A doivent être dans V, dans le problème de l'arbre de Steiner il est autorisé d'utiliser des points en dehors de V.

Algorithmes et complexité

Il existe différentes contraintes que l'on peut appliquer à l'arbre. La plupart des problèmes sont NP-complets (donc considérés comme difficiles à calculer). Quelques cas de figures[Lesquels ?] sont solubles en temps polynomial. Il existe des algorithmes d'approximation pour le problème[2], par exemple une (2-2/|S|)-approximation peut être obtenue en calculant un «arbre couvrant à terminaux de coût minimum» (minimum cost terminal spanning tree), c'est-à-dire un arbre couvrant dans un graphe adapté.

Un des algorithmes les plus connus est celui fournit par Melzack[3] en 1961 consistant à partir du problème à trois sommets posé par Fermat résolu par le mathématicien Italien Evengelista Torricelli. Il s'agit de réduire le nombre de points pour revenir à ce problème et ensuite faire revenir les points au fur et à mesure. Avant Melzack il n’existait aucun moyen de résoudre un problème à plus de 20 points. A ce jour l'algorithme exact le plus efficace semble être GeoSteiner[4].

Remove ads

Notes et références

Voir aussi

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads