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 :D
Vincent
Version imprimable
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 :D
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
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)