Optimale Einteilung einer Menge in disjunkte Untermengen

17.09.2016, 17:32	TomS	Auf diesen Beitrag antworten »
Optimale Einteilung einer Menge in disjunkte Untermengen Das Thena beschäftigt meine Frau praktisch und mich theoretisch. Gegeben sei eine Schulklasse (Menge M), Vorlieben und Abneigungen der Schüler untereinander (ganzzahlige Gewichte a_st; s,t indiziert die Schüler) sowie eine Einteilung der Schulklasse in verschiedene Gruppen (paarweise disjunkte Untermengen U_n), z.B. für ein Spiel. Gesucht ist die optimale Einteilung, so dass G maximal wird: $\begin{eqnarray} G_n = sum_{\langle s,t \rangle_n} a_{st} \end{eqnarray}$ $\begin{eqnarray} G = \sum_n G_n \end{eqnarray}$ Die Anzahl N in n = 1..N für die Anzahl der Unternengen sei fest vorgegeben. Die Paare <s,t>_n sind so definiert, dass nur Paare in die Summation einbezogen werden, für die s,t zur selben Untermenge n gehören. Ich kann diese auf ein (Pseudo)-Skalarprodukt abbilden: $\begin{eqnarray} G_n = (U_n,A\,U_n) \end{eqnarray}$ Wobei U_n einen Vektor darstellt, der an der s-ten Stelle eine Eins enthält, wenn der s-te Schüler in U_n enthalten ist (sonst Null). Meine Idee wäre, dieses Problem mittels Monte-Carlo-Simulation / importance sampling und simulated Annealing zu lösen, indem ich die Zugehörigkeit der Schüler zu den Unterguppen "würfle" und so das Optimum suche. Fragen: - unter welchem Sichwort finde ich denn etwas zu diesem Optimierungsproblem? das hat in der Fachliteratur bestimmt einen Namen - ist mein Ansatz sinnvoll? - welche weiteren Lösungsmethoden kommen in Frage? - und welche Darstellung für U, G, ... wähle ich dann sinnvollerweise? Die erste Frage ist mir am wichtigsten.
17.09.2016, 17:35	TomS	Auf diesen Beitrag antworten »
RE: Optimale Einteilung einer Menge in disjunkte Untermengen Korrektur: $\begin{eqnarray} G_n = \sum_{\langle s,t \rangle_n} a_{st} \end{eqnarray}$
23.09.2016, 18:39	TomS	Auf diesen Beitrag antworten »
Hat niemand eine Idee?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »