Discussion :

[teuweng]

Bonjour,

Je travaille actuellement en qualité de stagiaire sur un projet éolien. Le but de ce projet est d'optimiser la longueur du réseau électrique qui les relie entre elles, je n'entre pas plus dans les détails sur les considérations électriques.

Suite à diverses hypothèses et conclusions, j'envisage donc un réseau qui serait tel que réprésenté en fichier joint, en arbre.
http://imageshack.us/photo/my-images/341/schma.png
D'un point de vue mathématique, il y a certaines hypothèses à considérer:
Les points sont fixés et leur coordonnées sont connues sous forme (x;y);
Un, ou plusieurs points centraux, peuvent être envisageable mais je crois qu'il est plus simple de considérer un seul point;
Un nombre maximal de points connectés sur une seule branche;
Aucun croisement de branche;

J'ai bien évidemment cherché au niveau de la théorie des graphes mais aucun ne correspond exactement au problème posé. En effet, le problème du voyageur de commerce parait semblable mais je ne vois pas comment prendre en compte le nombre maximal de points par branche.

J'ai également cherché au niveau de l'algorithme génétique où il serait également possible de trouver une solution, certe pas nécessairement optimale, mais suffisament bonne, mais là encore, un codage binaire est utilisé et je ne vois pas comment coder les emplacements des points et les distances qui les séparent en un nombre de bits acceptable. De plus, il faut tenir compte, à nouveau, des contraintes topologiques.

Un ami informaticien m'a conseillé de tester toutes les possibilités avec un algorithme le plus efficace possible mais je ne vois pas comment cela pourrait se faire en un temps raisonnable. Il y a environ 100 points!

Je complèterai bien entendu ce message au fur et à mesure des questions posées.

Je vous remercie par avance pour l'aide apportée. Certaines idées peuvent en amener d'autres donc n'hésitez pas.

[bertry]

Salut,

Je pense que ce sujet t'intéressera : Minimum spanning tree

[teuweng]

Bonjour,

Effectivement, j'ai déjà beaucoup cherché de ce côté de l'arbre minimum, qui a mon avis est un problème proche. Cependant, aucun cas ne se ramène au problème que je dois résoudre. Lorsqu'on prend en compte tous les éléments, notamment, celui d'un maximum de points par branche qui doivent être centralisés en un seul point, on s'éloigne probablement de l'optimum.

Merci pour votre aide.