Bonjour !
Est-ce que quelqu'un pourrait brièvement m'expliquer le principe de fonctionnement de l'arbre de Steiner. Quelqu'un l'aurait-il programmé sous Turbo pascal par exemple. SI oui je suis preneur !
Merci d'avance
Vincent
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
l'arbre de Steiner (steiner tree)
Bonjour !
Est-ce que quelqu'un pourrait brièvement m'expliquer le principe de fonctionnement de l'arbre de Steiner. Quelqu'un l'aurait-il programmé sous Turbo pascal par exemple. SI oui je suis preneur !
Merci d'avance
Vincent
http://fr.wikipedia.org/wiki/Arbre_de_Steiner
Le problème est NP-complet. Je ne connais pas d'algo classique pour ce problème
Sur l'arbre de Steiner...
Permet-il bien de trouver le chemin minimum passant par n points donnés du plan (j'entends chemin qui passe et non relie tous les points entre eux.)?
Quels ouvrages consulter à ce sujet ?
Merci
Vincent
Je n'ai pas compris ta question jusqu'au moment où j'ai vu ton autre message dans ce même forum (je ne l'avais pas lu). La réponse que te donne Jean-Marc.Bourguet est la bonne (comme la plupart du temps, pour ne pas dire toujours). J'ai l'impression que tu en doutes...
Il y a plus d'explications et une référence sur le wikipedia anglais
http://en.wikipedia.org/wiki/Steiner_tree
Une introduction plus poussée avec plus de références bibliographiques
http://www.csie.ntu.edu.tw/~kmchao/tree05spr/Steiner.pdf
C'est un problème difficile. Pour y accéder, il est quasi-nécessaire d'avoir de bonnes connaissances en algorithmique et en optimisation (enseignées en bac+3 et bac+4)
Répondre avec citation
Partager