Discussion :

[tomjr]

Bonjour à tous !

Voila mon problème qui me taraude depuis très longtemps maintenant :

Un directeur d'école veut séparer « n » élèves dans « k » classes. Le nombre d'élèves dans une classe doit être compris entre un « min » et un « max » fixé. Le directeur veut créer des classes où les élèves s'entendent le mieux possible.

Si l'on résume cela sous forme de graphe, les sommets sont des élèves, tous reliés entre eux. Les arcs entre les sommets représentent la valeur de l'entente entre deux élèves. Cette valeur est proche de 0 si deux élèves s'entendent très bien. Cette valeur est très élevée si ces deux élèves se détestent.

Donc, si je prend un exemple : j'ai 100 élèves ; je dois créer 3 classes entre 30 et 40 élèves qui s'entendent le mieux possible.

1) Existe-il des heuristiques efficaces pour ce genre de problème ?

Si j'inclus maintenant le directeur dans ce problème, c'est aussi un sommet qui est relié à tous les élèves avec une valeur d'entente. Le directeur souhaite en plus qu'il y ait un délégué par classe. Ce délégué sera l'élève de la classe qui s'entend le mieux avec le directeur.

2) L'heuristique ici doit prendre en compte le directeur et cela complique le problème : doit-on d'abord choisir les classes et ensuite les délégués, ou choisir les délégués et les classes ensuite ?

J'ai plusieurs idées sur ces questions mais je suis à court d'idées neuves…

Merci d'avance.

[Obsidian]

Si l'on résume cela sous forme de graphe, on a un graphe planaire dont les sommets sont des éleves, tous reliés entre eux.

Pardon, mais je ne vois pas du tout pourquoi ton graphe aurait besoin d'être planaire. En plus, s'ils sont tous reliés entre eux (c'est-à-dire que chaque élève des relations avec tous les autres), il est impossible d'obtenir un graphe planaire au delà de quatre élèves.

J'ai plusieurs idées sur ces questions

Par exemple ?

[Trap D]

Celà me fait penser au problème des mariages stables même s'il y a quelques différences. Peut-être une piste à creuser ? la programmation par contraintes, il y a des solveurs en Prolog.

[tomjr]

Pardon, mais je ne vois pas du tout pourquoi ton graphe aurait besoin d'être planaire. En plus, s'ils sont tous reliés entre eux (c'est-à-dire que chaque élève des relations avec tous les autres), il est impossible d'obtenir un graphe planaire au delà de quatre élèves.

Désolé, une erreur de vocabulaire. Le graphe ne sera évidemment pas planaire tu as raison. J'ai édité mon message précédent.

Pour ce qui est de mes idées les voici:

A chaque itération, on prend l'arc de coût minimum et on colorie les deux sommets adjacents de la même couleur (en vérifiant tout de même si ces "colorations" respectent les contraintes de min et de max).

Ce serait un peu long d'expliquer tout l'algo mais avec cette technique, j'obtiendrai au final mes classes d'élèves.

Comme je pensais ramener ce problème à un problème d'arbre couvrant de poids minimal, je pense que j'appliquerai les algos de PRIM ou Kruskal sur ces "classes" pour obtenir des arbres et ainsi minimiser le poids des classes.

J'ai du mal à être clair, pas facile d'expliquer tout ça par écrit...

J'avais l'impression d'être face à un problème assez banal mais j'ai beaucoup de mal à trouver des problèmes similaires sur le net.

Celà me fait penser au problème des mariages stables

Je te remercie, je vais regarder ça de plus près.

[Trap D]

J'ai retrouvé une discussion sur le groupe google Prolog qui aborde un sujet similaire. Je pense qu'il y a de bonnes choses à en tirer.

[tomjr]

J'ai quelques faibles notions en Prolog, je vais essayer de comprendre tout ça.

Mais au final, mon projet sera codé en C!

[Trap D]

Evidement, ça risque d'être un peu différent !

[kent149]

Bonjour à tous!
Moi aussi j'ai a peu près le même problème, mon but est de créer un réseau de télécommunication. Le directeur serait un satellite et les élèves des centres à regrouper. Je pensais utiliser PRIM pour faire un grand arbre et ensuite le "couper" en autant de groupes qu'on le souhaite. Qu'en pensez vous?