Théorie des graphes

[ThomasPayet97436]

Bonjour,
Je me retrouve face à un problème qui me semble être un problème de théorie des graphes, domaine dans lequel je n'ai encore aucune connaissance.
Le problème est le suivant :
On pose m (entier naturel) choix comprenant chacun n (entier naturel) sous choix.
Chaque sous-choix est relié à tous les autres sous-choix des choix autres que celui auquel il appartient.
Ces liens (arêtes?) possèdent chacun un coût (réel positif).
Objectif : Ecrire un algorithme permettant de choisir un sous-choix dans chaque choix pour que la somme des coûts des arêtes ainsi retenues soit minimale.
La méthode brute consistant à comparer toutes les combinaisons possibles devient rapidement lourde ici.
Je cherche donc de l'aide (documents, explications...).
Merci d'avance
-----

[MissJenny]

bonjour, je n'ai pas l'impression que cette question relève réellement de la théorie des graphes. Pour chaque paire d'objets tu as un coût mais attribuer ce coût à une arête n'apporte rien il me semble.

[gg0]

Bonjour.

Ton explication n'est pas très claire. "comprenant chacun n (entier naturel) sous choix." ? Faut-il comprendre qu'il y a mn sous-choix au total, ou seulement n sous-choix ? D'autre part, peut-on choisir plusieurs fois le même sous-choix, auquel cas il suffit, pour chaque choix de chercher le sous-choix le moins cher, ou faut-il m sous-choix différents.
Pour tout éclaircir, présente un exemple avec m et n inférieurs à 3.

Cordialement.

[ThomasPayet97436]

Tout d’abord merci pour vos réponses.

Pour répondre à MissJenny :
J’avais présenté le problème tel quel à mon prof en illustrant par un schéma en prenant m=n=3 et il s’est tout de suite dirigé vers la théorie des graphes (en essayant d’appliquer l’algo de dijkstra), mais il est vrai que cela peut être complètement hors sujet. Si tu as des suggestions (problèmes similaires, simple piste …) je suis à l’écoute

Pour répondre à gg0:
Il y a en effet mn sous-choix au total.
Mon problème modélise une situation réelle. Je vous la présente en espérant éclairer les choses :
Je modélise un trafic aérien. On pose m vols différents (choix). Les vols peuvent s’effectuer à n altitudes différentes (l’attribution d’une altitude à un vol représente donc un sous-choix). Deux vols à une même altitude risquent de se croiser, ce danger est représenté par un coût. Objectif : attribuer une altitude à chaque vol pour que le coût total soit minimal.
Évidemment si m est inférieur à n, il suffit d’attribuer une altitude différente à chaque avion.
En espérant vous avoir éclairci

[A voir en vidéo sur Futura]

[MissJenny]

je pensais que les sous-choix formaient m ensembles disjoints et je ne voyais pas l'intérêt de considérer ce graphe m-parti, mais en fait c'est le contraire : les m ensembles ne sont qu'un.

[gg0]

Finalement, cette notion de "sous-choix" obscurcit tout. Pour chaque avion, il y a n altitudes possibles, et on évite d'en mettre 2 à la même altitude. Tu dis "ce danger est représenté par un coût." Si le coût est uniforme, la répartition des avions aux différentes altitudes est sans effet : Si on a 3 altitudes et 4 avions, et que mettre un avion à une altitude où il y en a déjà un coûte 1, on place les 3 premiers, et placer le quatrième coûte 1, quelle que soit l'altitude choisie. Si l'altitude a elle aussi un coût, alors on le mettra à l'altitude la moins coûteuse.
Si le coût n'est pas uniforme, l'algorithme "placer au moins cher" fonctionne bien en général, sauf s'il y a potentialisation avec d'autres facteurs.

Cordialement.

NB : J'ai déjà rencontré ce genre d'optimisation où toutes les solutions sont équivalentes; dans un article d'une revue habituellement sérieuse, comme exemple d'une méthode d'affectation.

[ThomasPayet97436]

Le coût n’est pas uniforme et dépend de la distance minimale atteinte par deux avions lors de leur croisement. Je ne suis pas sûr de bien saisir ce qu’est l’algorithme «*placer au moins cher*». Ne nous donnerait-il pas une solution éventuellement peu coûteuse au lieu d’une solution ayant le coût total minimal ?

Auriez-vous une référence ? Le nom de la revue ou des mots clés qui préciseraient mon travail de recherche ?

[gg0]

Non, je n'ai pas de nom de revue; par contre, les termes "algorithmes d'affectation", " algorithme glouton", pourraient te donner quelques idées.