Question analogique du problème de l'arbre de Steiner

→ **MyCalcs** profile · de **CariceHouten** » 19 Avr 2021, 07:14

Salut à tous, je fais un projet où j'ai un tas de points fixes d'emplacement connu et j'ai besoin de créer un réseau de cordons qui relient chacun de ces points fixes à n nombre de points placés. Ces points placés doivent être placés à un emplacement tel que la longueur totale du cordon entre tous les points soit minimisée.

Le meilleur analogue que j'ai pu trouver est le problème de l'arbre de Steiner, où un réseau de cordons d'une longueur minimale est créé pour connecter chaque point à n'importe quel autre point. Je recherche un problème / une solution similaire, mais les points fixes doivent uniquement être connectés à l'un des points placés (et non liés à tous les autres points).

Faites-moi savoir si j'ai besoin de clarifier quelque chose et merci d'avance.

→ **MyCalcs** profile · de **Bisam** » 20 Avr 2021, 09:12

Je pense que ton problème est celui de "l'arbre couvrant minimal". Tu peux utiliser l'algorithme de Kruskal ou l'algorithme de Prim pour le résoudre.

→ **MyCalcs** profile · de **Noemie79** » 12 Mai 2023, 07:33

Salut les gars,

J'suis dans un projet où j'ai plein de points fixes avec des emplacements connus. Mon délire, c'est de créer un réseau de cordons qui relie chaque point fixe à n points placés. Et ces points placés doivent être positionnés de manière à minimiser la longueur totale des cordons entre tous les points.

Le problème qui se rapproche le plus de ça, c'est celui de l'arbre de Steiner. C'est quand tu crées un réseau de cordons avec la longueur minimale pour connecter tous les points entre eux. Mais moi, j'veux un truc similaire, sauf que les points fixes doivent être connectés à un seul point placé (pas tous les points).

Dites-moi si y'a besoin de clarifications, et merci d'avance pour votre aide.

→ **MyCalcs** profile · de **Bisam** » 12 Mai 2023, 10:19

Es-tu la même personne que @CariceHouten, qui a posé exactement la même question il y a deux ans ?

Après une recherche un peu plus poussée que ma réponse de l'époque, je vois que le problème de l'arbre de Steiner est NP-complet. Celui que tu évoques semble en être une simplification mais je ne vois pas ce que tu veux dire par "connectés à un seul point placé (pas tous les points)".

Peux-tu donner un exemple pour illustrer ton cas ?