Problème de l'arbre de Steiner — Wikipédia

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).
Solution pour quatre points. Dans cet arbre, il y a deux points de Steiner : et

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.

Définitions

[modifier | modifier le code]

Il existe plusieurs variantes du problème.

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

Définition d'optimisation combinatoire : graphes

[modifier | modifier le code]

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].

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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é

[modifier | modifier le code]

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].

Notes et références

[modifier | modifier le code]
  1. (en) « Steiner tree problem », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne)
  2. a et b (en) Viggo Kahn, « Minimum Steiner Tree », sur A compendium of NP optimization problems,
  3. « Welcome », sur www.steinertreesbook.com (consulté le )
  4. « GeoSteiner Homepage », sur www.geosteiner.com (consulté le )

Liens externes

[modifier | modifier le code]

Bibliographie

[modifier | modifier le code]
  • (en) F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Elsevier, North-Holland, 1992, (ISBN 0-444-89098-X) (Annals of Discrete Mathematics, vol. 53).