Startseite
Forum
Fragen
Suchen
Formeleditor
Über Uns
Registrieren
Login
FAQ
Suchen
Foren-Übersicht
->
Sonstiges
Antwort schreiben
Benutzername
(du bist
nicht
eingeloggt!)
Titel
Nachrichtentext
Smilies
Weitere Smilies ansehen
Schriftfarbe:
Standard
Dunkelrot
Rot
Orange
Braun
Gelb
Grün
Oliv
Cyan
Blau
Dunkelblau
Indigo
Violett
Weiß
Schwarz
Schriftgröße:
Schriftgröße
Winzig
Klein
Normal
Groß
Riesig
Tags schließen
Schreibt eure Formeln hier im Board am besten mit Latex!
So gehts:
Latex-Kurzbeschreibung
|
Formeleditor
[quote="TomS"]Super, das ist ein völlig neuer Ansatz. Ist bei mir etwas komplizierter, da mein A keine (0,1)-Matrix ist, sondern eine (-M,...,+M)-Matrix, d.h. dass i.A. ein gewichteter Graph mit Gewichten a_st vorliegt; dafür finde ich vergleichsweise wenig Literatur, aber ich gab' da keinen Stress. Jedenfalls danke nochmal.[/quote]
Optionen
HTML ist
aus
BBCode
ist
an
Smilies sind
an
BBCode in diesem Beitrag deaktivieren
Smilies in diesem Beitrag deaktivieren
Spamschutz
Text aus Bild eingeben
Alle Zeiten sind GMT + 1 Stunde
Gehe zu:
Forum auswählen
Themenbereiche
----------------
Mechanik
Elektrik
Quantenphysik
Astronomie
Wärmelehre
Optik
Sonstiges
FAQ
Sonstiges
----------------
Off-Topic
Ankündigungen
Thema-Überblick
Autor
Nachricht
bassiks
Verfasst am: 09. Okt 2016 15:55
Titel:
Mal so als "Brute-Force" Variante, hätte ich das mal so formuliert:
Z' = Z - Summe unterschrtitten - summe überschritten + summe beides
Der letzte Summand muss leider sein weil sonst Kombinationen zweimal gezählt werden. Ohne dass ich es kontrolliert habe (nicht mal geplottet oder ähnliches, einfach mal aufgeschrieben) komme ich auf was in der Form:
Zur Erläuterung: Bei den ersten beiden Teilen summiere ich einfach über alles was a unterschreitet oder b überschreitet.
m steht dabei für die Anzahl der Klassen welche a unterschreiten. Das heißt ich habe in diesen Klassen bereits mindestens m Schüler, aber maximal m*a Schüler. Das heißt ich summiere dann über die möglichen Kombinationen S-l Schüler auf N-m Klassen zu verteilen. Jeder Summand wird multipliziert mit den Möglichkeiten l Schüler auf m Klassen zu verteilen, da dies wiederrum unterscheidbare Konfigurationen abgeben würde.
Beim zweiten Summanden steht m für die Anzahl der Klassen welche b überschreiten. Ich habe also mindestens b*m Schüler, aber maximal S-N+m, denn ich will in den anderen N-m Klassen ja noch mindestens einen Schüler haben. Summiert wird über die möglichen Kombinationen S-l Schüler auf N-m Klassen zu verteilen, wiederrum mit dem Faktor der Möglichkeiten l Schüler auf die anderen m Klassen zu verteilen.
Der letzte Teil ist...naja...^^.
Hier war der Gedankengang, dass ich mindestens 2 Klassen mit über- oder unterschrittener Schülerzahl habe. m summiert über die unterschrittenen, dann bleiben noch k-m überschrittene Schüler. Das heißt ich habe mindestens m+(k-m)*b Schüler auf die anderen Klassen zu verteilen, maximal aber m*a+S-l-N+k, denn ich darf in m Klassen a nicht überschreiten, und will aber für meine N-k Klassen auch noch genug Schüler haben um mindestens einen darin sitzen zu haben. Summiert wird über die Möglichkeit S-k-j Schüler auf die übrig gebliebenen N-k Klassen zu verteilen, mit den Faktoren durch jeweils verschiedene Möglichkeiten j Schüler auf N-k+m Klassen und l Schüler auf m Klassen zu verteilen.
Ich hab hier nichts durchgerechnet oder vereinfacht. Zum vereinfachen bietet sich evt. eine Möglichkeit mittels Chu-Vandermonde an (
https://en.wikipedia.org/wiki/Vandermonde%27s_identity
).
Ich habe das auch nicht nochmal durchgedacht, ist also sicher irgendwo ein Fehler, aber evt. liefert es dir einen Ansatz.
TomS
Verfasst am: 09. Okt 2016 13:29
Titel:
Es geht voran.
Ich habe noch eine Frage zur Abschätzung der Kombinatorik bzw. der Komplexität. Gesucht ist die Anzahl der Möglichkeiten, S unterscheidbare Schüler auf N unterscheidbare Klassen zu verteilen. Für jeden Schüler stehen N Klassen zur Verfügung. Das liefert also zunächst
Diese Abschätzung ist jedoch praxisfern; man müsste eine zusätzliche Bedingung angeben, z.B. die minimale und die maximale Klassengröße.
Also: gesucht ist die Anzahl der Möglichkeiten, S unterscheidbare Schüler auf N unterscheidbare Klassen zu verteilen, wobei jede Klasse mindestens a und höchstens b Schüleranzahl haben muss.
Wie rechnet man das?
TomS
Verfasst am: 26. Sep 2016 21:51
Titel:
franz hat Folgendes geschrieben:
Darf ich das statische Mögen / Nichtmögen vorsichtig in Zweifel ziehen ...
Ja, aber das ist die Aufgabe.
franz hat Folgendes geschrieben:
Eine anspruchsvolle mathematische Spielerei sicher ...
Nee. Ich hatte das schon mal sehr einfach gelöst - speziell für dieses Beispiel. Ich möchte es jetzt aber allgemein und optimiert lösen, daher die Diskussion.
Im nächsten Schritt geht es um eine deutlich komplexere Aufgabe: Klassenbildung für ca. 170 Schüler, teilw. mit Migrationshintergrund, teilw. (fast) ohne Deutschkenntnisse, diese gemischt in Klassen mit Kindern mit guten Deutschkenntnissen, Auseinanderhalten von verhaltensauffälligen Schülern, Beachtung von Freundschaften, Zuordnung zu speziellen Lehrern, möglichst gleiche Anzahl von Jungen und Mädchen ... Da wirst du nicht die Kinder fragen wollen :-)
Die Zusatzbedingungen werden teilweise über Gewichte * Zwangsbedingungen realisiert, z.B.
franz
Verfasst am: 26. Sep 2016 18:10
Titel:
Darf ich das statische Mögen / Nichtmögen vorsichtig in Zweifel ziehen durch Themenabhängigkeit beispielsweise oder, bißchen nichtlinear, weil mache Schöler eine Gruppeneinteilung ablehnen - wegen des einteilenden Lehrers?
Eine anspruchsvolle mathematische Spielerei sicher, die mich etwas an die Berücksichtigung der Gebetswünsche von Mohammedanern oder Stillzeiten junger Mütter in der Kriegsplanung der Bundeswehr erinnert.
MI
Verfasst am: 26. Sep 2016 16:07
Titel:
In dem von mir verlinkten Artikel steht in der Conclusion, dass der Algorithmus sich ganz einfach auf gewichtete Graphen verallgemeiner lassen würde. Leider kenne ich mich da wirklich nicht aus.
Es wäre aber mal interessant das anzuwenden und vielleicht damit zu vergleichen was passiert, wenn man die Schüler selbst aussuchen lässt. Ich vermute, dass die schon ziemlich nahe am Optimum liegen würden. Man kann dann natürlich auch mal die Vorzeichen umkehren und Leute zusammenarbeiten lassen, die sich eben gerade nicht mögen
.
Gruß
MI
TomS
Verfasst am: 24. Sep 2016 17:58
Titel:
Super, das ist ein völlig neuer Ansatz.
Ist bei mir etwas komplizierter, da mein A keine (0,1)-Matrix ist, sondern eine (-M,...,+M)-Matrix, d.h. dass i.A. ein gewichteter Graph mit Gewichten a_st vorliegt; dafür finde ich vergleichsweise wenig Literatur, aber ich gab' da keinen Stress.
Jedenfalls danke nochmal.
MI
Verfasst am: 24. Sep 2016 16:14
Titel:
Wenn ich das richtig sehe, dann kann man das Problem doch so umformulieren:
Jeder Schüler bildet einen Vertex eines Graphen, jede Präferenz ein Edge mit Gewichtung (positiv/negativ). Die Aufgabe ist eine Partitionierung in
möglichst gleichgroße Teile zu finden, die das Gesamtgewicht aller Graphen der Partitionierung maximiert.
Da das gesamte Gewicht des Graphen feststeht (das ist einfach die Summe der Matrix A), ist die Maximierung des Gesamtgewichtes der Partitionierung äquivalent zur Minimierung des Gewichtes der Edges, die durchgestrichen werden (also von Schülern, die nicht in derselben Gruppe arbeiten).
Wenn ich das richtig sehe, laufen solche Probleme unter dem Namen
Graph partition
. Um mal ein Beispiel eines Papers zu finden, was so etwas macht (die Gruppengröße ist dabei nur "ungefähr gleich", ich weiß nicht, was das genau in der Praxis heißt, ich habe nur den Abstract gelesen) zum Beispiel dieses hier:
http://www.math.cmu.edu/~kandreev/kpart.pdf
Ich muss gestehen, dass ich genau Null Ahnung von Graphentheorie habe und ich könnte da was übersehen, aber vielleicht hilft ja zumindest die Umformulierung + der Name weiter!
Viele Grüße
MI
TomS
Verfasst am: 23. Sep 2016 17:50
Titel:
Noch eine Idee? Bei stackexchange rührt sich niemand.
Ich schwenke gerade auf threshold acceptance oder evtl. Sintflut um, da performanter. Kennt sich da jemand aus?
TomS
Verfasst am: 20. Sep 2016 14:10
Titel:
Vom Gefühl her bleibe ich bei diskreter Optimierung / 0-1-Programmierung und meinen o.g. Vorschlägen (die hab' ich schon mal implementiert und die funktioniert prinziell).
Trotzdem danke für die Idee.
Ich
Verfasst am: 20. Sep 2016 12:57
Titel:
Nö, wie gesagt kenne ich mich da nicht so aus. Aber nachdem es nur darum geht, dass die Funktion "Abstand" eine Zahl zurückgibt, sehe ich da kein Problem. Wenn's zu "hochdimensional" ist oder unterbestimmt, weil du nur ein paar Binärwerte hast, dann muss man vermutlich tricksen, könnte ich mir vorstellen.
In der englischen Wikipedia findest du aber genügend Beispiele, die man adaptieren könnte. Ob's dann funktioniert ist eine andere Frage, aber das ist schon die Klasse, in die dein Problem fällt.
TomS
Verfasst am: 20. Sep 2016 12:51
Titel:
Ich hat Folgendes geschrieben:
Eine vernünftige Funktion G zu wählen ist sicher einer der Schlüssel zum Erfolg ... Binäre Werte sind eine Untermenge der reellen Zahlen, die Abstandsfunktion kannst du schon bauen, und es gibt genug Algorithmen, die ohne Schwerpunkte arbeiten.
Hast du dazu eine Quelle?
Ich
Verfasst am: 20. Sep 2016 11:40
Titel:
Zitat:
Ich bin mir nicht sicher, ob das überhaupt als Abstandsfunktion modellierbar ist. Da kein Schüler gezwungen wird, seine Likes und Dislikes für alle anderen Schuler abzugeben, und da es eben auch negative Dislikes gibt, ist die Matrix A nicht positive definit. Es ist eine Bilinearform, mehr kann man dazu nicht sagen.
Na, durch Addition einer Konstante wird daraus eine positiv definite Abstandsfunktion. Wobei mir nicht klar ist, warum du darauf bestehst, man kann doch auch für negative Abstände Optimierungskriterien finden.
Zitat:
In der Clusteranalyse sieht es doch wie folgt aus:
Man optimiert nun G über die Zugehörigkeit der s zu den Clustern U_n sowie über die Schwerpunkte X_n der Cluster.
Nicht notwendigerweise. Eine vernünftige Funktion G zu wählen ist sicher einer der Schlüssel zum Erfolg.
Zitat:
Ich sehe folgende Unterschiede: Bei der CA sind alle Werte reell; bei mir sind alle Werte binär. Bei der CA liegt eine Abstandsfunktion vor, bei mir nicht. Bei der CA werden doch neben der Zugehörigkeit zu Clustern auch deren Schwerpunkte X_n variiert (je nach Zugehörigkeit berechnet).
Nein, so engstirnig definiert ist die CA nicht. Binäre Werte sind eine Untermenge der reelen Zahlen, die Abstandsfunktion kannst du schon bauen, und es gibt genug Algorithmen, die ohne Schwerpunkte arbeiten.
TomS
Verfasst am: 20. Sep 2016 11:24
Titel:
Ich hat Folgendes geschrieben:
Das ist Cluster Analysis. Das einzig Ungewöhnliche an deiner Aufgabenstellung ist die "Abstandsfunktion", die du statt einer "Positionsangabe" der Elemente zur Verfügung hast. Ich könnte mir vorstellen, dass ein solcher Positionsraum u. U. viele Dimensionen bräuchte und die Algorithmen dann schlecht funktionieren. Kenne mich aber nicht aus damit, vielleicht ist alles kein Problem.
Ich bin mir nicht sicher, ob das überhaupt als Abstandsfunktion modellierbar ist. Da kein Schüler gezwungen wird, seine Likes und Dislikes für alle anderen Schuler abzugeben, und da es eben auch negative Dislikes gibt, ist die Matrix A nicht positive definit. Es ist eine Bilinearform, mehr kann man dazu nicht sagen.
In der Clusteranalyse sieht es doch wie folgt aus:
Man optimiert nun G über die Zugehörigkeit der s zu den Clustern U_n sowie über die Schwerpunkte X_n der Cluster.
Ich sehe folgende Unterschiede: Bei der CA sind alle Werte reell; bei mir sind alle Werte binär. Bei der CA liegt eine Abstandsfunktion vor, bei mir nicht. Bei der CA werden doch neben der Zugehörigkeit zu Clustern auch deren Schwerpunkte X_n variiert (je nach Zugehörigkeit berechnet).
Entdecker22
Verfasst am: 20. Sep 2016 11:16
Titel:
Was für ein praktisches Problem deiner Frau liegt denn dahinter?
Bin neugierig
Ich
Verfasst am: 20. Sep 2016 10:10
Titel:
Das ist Cluster Analysis. Das einzig Ungewöhnliche an deiner Aufgabenstellung ist die "Abstandsfunktion", die du statt einer "Positionsangabe" der Elemente zur Verfügung hast. Ich könnte mir vorstellen, dass ein solcher Positionsraum u. U. viele Dimensionen bräuchte und die Algorithmen dann schlecht funktionieren. Kenne mich aber nicht aus damit, vielleicht ist alles kein Problem.
TomS
Verfasst am: 20. Sep 2016 09:32
Titel:
Danke!
Hab' die Frage mal dort gestellt:
Discrete optimization - optimized assignment of members to subsets / partitioning of a set to subsets
jh8979
Verfasst am: 19. Sep 2016 21:52
Titel: Re: Optimale Einteilung einer Menge in disjunkte Untermengen
Nice
TomS hat Folgendes geschrieben:
1) unter welchem Sichwort finde ich denn etwas zu diesem Optimierungsproblem? das hat in der Fachliteratur bestimmt einen Namen
Bestimmt
Zitat:
2) ist mein Ansatz sinnvoll?
Wäre auch mein erster, naiver Ansatz gewesen.
Zitat:
3) welche weiteren Lösungsmethoden kommen in Frage?
Wenn Zahlen dieser Größenordnung auftreten, denkt der Physiker natürlich an Statistische Physik/Thermodynamik. Seh aber so auf den ersten Blick keine sofort nützliche Analogie.
Zitat:
Die erste Frage ist mir am wichtigsten.
Sorry.
Ich hoffe ich hab die nächsten Tage Zeit darüber nachzudenken. Das Problem klingt ziemlich cool
PS: Da es mehr englischsprachige Nerds gibt: Hast Du math stackexchange schon probiert?
TomS
Verfasst am: 19. Sep 2016 21:31
Titel: Optimale Einteilung einer Menge in disjunkte Untermengen
Ich habe das Thema bereits im Matheboad gestellt, aber - wie so oft - bekommt man da keine Antwort.
Das Thema beschäftigt meine Frau praktisch und mich theoretisch.
Gegeben sei eine Schulklasse (Menge U), 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 Teilmengen U_n).
Die Schüler werden nummeriert:
Man kann jeder Untermenge U_n ein S-Tupel zuordnen
wobei die u_n^s 1 sind, wenn der s-te Schüler Element der Gruppe n-ten Gruppe ist, 0 sonst.
Gesucht ist die optimale Einteilung, so dass folgendes G maximal wird:
Die Anzahl N in n = 1..N für die Anzahl der Teilmengen U_n sowie die Gewichte a_st seien 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 Teilmenge n gehören.
Ich kann dies auf ein Pseudo-Skalarprodukt abbilden:
Die U_n definieren S-Tupel bzw. Vektoren in einem S-dim. Vektorraum. Die Anzahl der insgs. möglichen Konstellationen beträgt
Dabei kann der erste Schüler in einer aus N Gruppen sein, der zweite Schüler ebenfalls etc. Bei z.B. S=30 Schülern und N=6 Gruppen ergibt sich Z(6,30) = 6^30 = 2.2 * 10^23. In der Praxis wird man natürlich eine Minimal- und eine Maximalgröße der Gruppen festlegen, z.B. genau 5 oder 4 bis 6, so dass diese Zahl deutlich reduziert wird (jedoch immer noch zu groß ist, um alle Konstellationen durchzuprobieren).
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 s zu den Untergruppen U_n "würfle" und so das Maximum g über alle G suche
Fragen
:
1) unter welchem Sichwort finde ich denn etwas zu diesem Optimierungsproblem? das hat in der Fachliteratur bestimmt einen Namen
2) ist mein Ansatz sinnvoll?
3) welche weiteren Lösungsmethoden kommen in Frage?
Die erste Frage ist mir am wichtigsten.