Problème de l'arbre de Steiner

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.

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 : $S_{1}$ et $S_{2}$

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.

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.

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

Voir aussi

Liens externes

• (en) Viggo Kahn, « Minimum Steiner Tree », sur A compendium of NP optimization problems, mars 2000
• (en) Ronald L Graham: The Shortest Network Problem, film de 1988
• (en) « Steiner tree problem », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)

Bibliographie

• (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).