Le problème de Steiner  

 

 Présentation:

Un arbre de Steiner  est un graphe qui recouvre un ensemble donné de points de l'espace métrique tel que la distance totale sur ses bords soit minimale. 

En théorie:

 

Soit G = (V,E,d) un graphe symétrique dans un espace métrique où V est un ensemble de points de G, E est un ensemble d'arêtes de G et d une distance métrique.

Soit S un sous-ensemble de V.

Soit D(g) = somme d(ei) où g est un graphe possédant un nombre ei d'arêtes.

Soit X un ensemble d'arbres de G étendu sur S. La construction d'un arbre de Steiner T répond à la définition suivante:

 T = (V',E', d) élément de X tel que D(T) = inf{ D(x) : x élément of X}

 

Histoire

 

Au cours du 17ième siècle, le mathématicien français Pierre de Fermat chercha comment on pouvait trouver un point P dans un triangle de manière à ce que la longueur totale des arêtes concourantes au point P soit la plus petite possible. Ce problème fut résolu plus tard par Torricelli.

Le problème de Steiner est la généralisation de cette question permettant d'ajouter pour un nombre arbitraire d'arêtes et de points. Ce problème a trouvé de multiples applications  dans un panel de disciplines très étendu. Malheureusement, il a été démontré que ce problème fait partie de la classe des problèmes NP-complets.

De par l'importance de ses travaux qui constituent des défis mathématiques, Jacob Steiner contribua à la recherche de solutions à ce problème.

  Un algorithme.

 

Bien que ce problème soit de classe NP-complet, Il existe des algorithmes heuristiques qui ont été conçus pour approcher la solution exacte dans un temps polynomial.

 

A Steiner tree is a tree in a distance graph which spans a given subset of vertices (Steiner points) with the minimal total distance on its edges.

 Formally:

 

Let G = (V,E,d) be an undirected graph in metric space where V is the set of vertices in G, E is the set of edges in G and d is the metric distance method.

Let S be a subset of V.

Let D(g) = sum d(ei) where g is a graph with indexed edges ei.

Let X be the set of trees in G which span S.

Find T = (V',E',d) element of X such that D(T) = inf{ D(x) : x element of X}

 

   

History

 

In the 17th century, the ubiquitous French mathematician Pierre Fermat asked how we could find a point P in a triangle with the distances from P to the vertices being as small as possible. This problem was later solved by Torricelli.

The Steiner Problem is a generalisation of this question allowing for an arbitrary number of initial vertices and an arbitrary number of vertices to be added. This problem has found uses across a wide array of disciplins. Unfortunately, it has been shown to be NP-complete.

Though the importance of his contributions to mathematics goes unchalanged, it is unclear what Jacob Steiner contributed to this problem.

   

 

 An algorithm.

 

Though this problem is NP-complete, certain heuristic algorithms have been designed to approximate the result within polynomial time. This is such an algorithm taken from Kou et al.

 

 

 

 
Pour télécharger le document pdf qui présente les bases topologiques 
du problème de Steiner, cliquer ici. (format zip)
                                   

 

Une autre manière de présenter le problème de Steiner:
 
Le problème de la minimisation d’un arbre de Steiner (MStT) se pose de la
façon suivante :
Etant donné un ensemble P de n points d'un espace métrique E, appelés points initiaux,
trouver un ensemble S de points additionnels, appelés points de Steiner, tel
que la longueur de l’arbre soit minimale. Ce problème est considéré comme faisant partie 
de la classe des problèmes NP-complet.
En dehors du fait que ce problème est particulièrement bien adapté pour un
traitement par algorithmes génétiques, il est d’une grande importance pratique.
A titre d’exemple, nous pouvons citer la conception de grands réseaux
(télécommunication, distribution électrique, pipelines,. . .).
Il est probable que le cas le plus connu de cette application est celui fourni par
Gilbert pour la mise en réseau des grandes villes américaines. Traitement qui lui
a fait baisser le coût total de l’ordre de 240 millions de dollars en considérant
les arbres minimaux de Steiner (MStT) plutôt que les (MSpT) pour lesquels
on minimise le nombre de points de Steiner. Dans le cas de cette étude, on
envisage de construire les MstT. 
Pour minimiser un MStT, il est nécessaire de connaître le nombre de points
de Steiner et leur position sur le plan. Ce plan comme on l’a dit plus haut est
considéré comme NP-complet. C’est-à-dire que l’effort de calcul nécessaire
pour construire la solution optimale est tellement important (il croît exponentiellement
avec le nombre de nœuds) que seuls les problèmes avec 17 nœuds
ont été résolus de façon exacte à ce jour. Quelques cas à 30 nœuds ont 
également été résolus.
Pour obtenir des solutions quasi-optimales pour des problèmes à grand nombre
de nœuds, on utilise des heuristiques. Le logiciel à télécharger met en oeuvre des 
algorithmes heuristiques personnels. Il se décline en français et en anglais.
 
                  Steiner
 Pour télécharger le constructeur d'arbres de Steiner, cliquer ici. (format zip)
   C:/Program files/Sciences/Steiner.exe
                       ESteiner
To download the english version of the Steiner trees solver, click here.
(standard zip)
 C:/Program files/Sciences/ESteiner.exe
 
                   
Si vous souhaitez signaler une erreur ou apporter des idées pour améliorer le constructeur d'arbres de Steiner, vous pouvez le faire en écrivant à l'auteur.

                                                                                                             

                                                                                  (Sans fichier accroché SVP)
 
Haut de page >>
Retourner à la page d'accueil >>