Problème de l'arbre de Steiner
Pour les articles homonymes, voir 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.
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]
- (en) « Steiner tree problem », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne)
- (en) Viggo Kahn, « Minimum Steiner Tree », sur A compendium of NP optimization problems,
- « Welcome », sur www.steinertreesbook.com (consulté le )
- « GeoSteiner Homepage », sur www.geosteiner.com (consulté le )
Voir aussi[modifier | modifier le code]
Liens externes[modifier | modifier le code]
- (en) Viggo Kahn, « Minimum Steiner Tree », sur A compendium of NP optimization problems,
- (en) Ronald L Graham: The Shortest Network Problem, film de 1988
- (en) « Steiner tree problem », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne)
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).
