Discussion :

[svince]

Bonjour à tous !


Je souhaiterais savoir s'il est possible selon vous de générer un
programme en turbo pascal qui permettrait de tracer le trajet minimum entre n points du plan. Je ne parle pas du problème du voyageur de
commerce. Il s'agit de créer un trajet passant par chaque point, mais sans qu'ils soient tous reliés entre eux... Vous trouverez un exemple de ce que je veux obtenir entre 4 points sur le site http://formesoptimisees.free.fr/plan9.htm
Si oui comment s'y prendre ?


Merci d'avance.


Vincent

[Eric Sigoillot]

Bonjour,

Même en regardant le site, ce n'est pas clair. Je vous renvoie par ailleurs vers le forum Algorithmes qui sera plus approprié...

@++

[j.p.mignot]

N'est-ce pas tout simplement un problème de calcul de géodésique?

[svince]

Je ne pense pas, non...

[Jean-Marc.Bourguet]

J'ai pas changé d'opinion: ce que tu cherches, c'est les (Minimal) Steiner Tree. D'ailleurs tu sembles avoir vu ma réponse dans fr.comp.algorithmes puisque tu as fait ici une nouvelle demande avec Steiner Tree...

Pour le reste, je ne peux faire mieux que

[svince]

OK, merci ! Je vais faire ça !

Vincent

J'ai pas changé d'opinion: ce que tu cherches, c'est les (Minimal) Steiner Tree. D'ailleurs tu sembles avoir vu ma réponse dans fr.comp.algorithm puisque tu as fait ici une nouvelle demande avec Steiner Tree...

Pour le reste, je ne peux faire mieux que :google2:

[leyee]

Ton probleme n'est pas la recherche d'un arbre couvrant (minimum si les aretes sont ponderes) dans un graphe complet? En tout cas ça y ressemble : pour cela tu as des algos de faible complexité (Prim et Kruskal)

[Jean-Marc.Bourguet]

Ton probleme n'est pas la recherche d'un arbre couvrant (minimum si les aretes sont ponderes) dans un graphe complet? En tout cas ça y ressemble : pour cela tu as des algos de faible complexité (Prim et Kruskal)

Non, il peut introduire des points supplémentaires.