Gruppenbildung, Algorithmus

C

CentralWay

0
Hallo,
ich habe eine Algorithmus-Frage.
Folgendes Szenario:
Eine Anzahl von Personen, 22 Themen. Jede Person wählt mindestens 5 Themen aus, mindestens zwei davon müssen mit der Priorität "1" angegeben werden, die anderen können mit der Priorität "2" oder "0" angegeben werden.

Also könnte die SQL-Tabelle etwas so aussehen:
|ID|Name|#1|#2|#3|#4|#5|...|#22| //Kopf
|1 |Hans | |1 |2 |1 |0 | |2 | //Prioritäten,

| | = Thema nicht gewählt
|1| = erste Priorität
|2| = zweite Priorität
|0| = gewählt ohne Priorität

Nun geht es darum, die Personen möglichst so auf die Themen augzuteilen, dass:
-in allen Themen 16-22 Personen sind
-möglichst viele 1-en berücksichtigt werden
-möglichst keine Themen Personen zugeordnet werden, die dieses Thema überhaupt nicht oder nur mit 0 gewählt haben.

Ich habe mir folgenes Überlegt:
Zuerst wird von allen Themen die 1-en Anzahl gezählt, dann habe ich wie eine "Beliebtheitsfolge". Sollte es ein Fach mit gar keinen 1-en geben, werden in diesem Fach die 2-en gezählt und gerade fest zugeordnet. Die dann zugeordneten Personen werden in der Tabelle als "fest" gesetzt und alle Daten neu in das Skript geholt, es beginnt wieder von vorne...

Und wies weiter gehen soll weiss ich eben nicht :) Wie würdet ihr das machen? Ich wäre sehr froh um Denkanstösse und möglichst auf dieses Szenario bezogene Algorithmen! (Sprache egal, ich werde es in SQL/php realisieren)

Liebe Grüsse und vielen Dank,
michi
 
Also ich würde tabellen so erstellen:
Themen(ID, Name)
Teilnehmer (ID, Name)
Kurse(ThemenID,TeilnehmerID,Interesse,...) //Also je eine "Veranstaltung"

Ich verstehe bloß nicht, worum es dabei gehen soll. Wenn jemand eine Vorlesung oder was auch immer mit 1 gewichtet, ist das seine Entscheidung. Es ist natürlich möglich, dass dieser schon von anderen mit 1 belegt wurde. Soll es eine max. Teilnehmerzahl geben?
 
Also soll ein Teilnehmer "gezwungen" werden, wenn es eine optimalere Konstellation gibt bzw. ein Kurs voll ist einen anderen auszuwählen?
 
Hm, ich würde es so machen:
zuerst die User auf die Themen nach 1 Auswahl verteilen - dabei auch erstmal nicht auf die Begrenzung achten.
Es werden wohl bestimmte Themen "überbelegt" und bestimmte kaum/gar nicht gewählt werden. Jetzt geht man so vor:

Teil1:
man nimmt nun ein "unterbelegtes" Thema (Bez: unter_Thema) und sucht nach einem User, der dieses Thema mit einer 1 markiert hat (und sich logischeriweise in einem anderen Thema befindet). Optimal wäre es, mit Usern aus einem am meisten "überbelegten" Thema (Bez: über_Thema) anzufangen.

Ist der gefundene User in einem Thema mit >16 User, verfrachte diesen User in das "unterbelegte" Thema. Wiederhole, solange das Thema "unterbelegt" ist oder sich keine User mehr finden/abziehen lassen.

In diesem Fall gehe zum nächsten unter_Thema und wiederhole die obigen Schritte.

Teil1 ende

Jetzt haben wir (abgesehen von der optimalen Situation, dann sind wir fertig ;) ) eher solche Verteilung: es gibt immer noch über_Themen deren User keine der unter_themen gewählt haben und/oder User können nicht mehr aus anderen Themen abgezogen werden, da das Thema dann <16 User hat.

Man kann also entweder zufällig jemanden aus den überfrachteten Themen aussuchen oder den Umstand berücksichtigen, dass User ja zwei 1-er Themen hatten und eventuell ein Tausch der User untereinander eine bessere Möglichkeit ergäbe. Bsp.
Thema1 überbelegt, Thema2 min-belegt und thema3 unterbelegt.
Kein User aus Thema 1 hat Thema2 belegt, aber dafür mehrere User auch Thema2 belegt. Im Thema2 gibt es wiederum User, die Thema3 gewählt haben. Wenn man nun geschickt tauscht, sind alle immer noch in ihren Lieblingsthemen. Bei 22 Themen kann eine solche Situation durchaus (verschachtelt)auftreten

Teil2:
Sind immer noch themen unterbelegt:

Code: 
für alle unter_Themen do:
   suche nach allen Usern, die das unter_Thema mit einer 1 gewählt haben    
   und noch nicht diesem Thema zugeordnet sind.
//Wir haben also eine "primäre"Liste, in der die User das unter_Thema 
//gewählt haben aber (da Teil1 korrekt abgearbeitet wurde) nicht 
//abgezogen werden können.

   arbeite die primListe ab;
od
Die Userliste können wir so abarbeiten:

Code: 
while primList<>NULL OR aktuelle_unter_Thema<16 User //Liste durchgehen
do
   aktueller_user=user aus primList;
   if sucheUndVertausche(Users_aktuelles_Thema)!=TRUE
     break;
   primList.next();
od

funktion sucheUndVertausche(Ziel_Thema,rekTiefe)
  if (rekTiefe<=0) return FALSE //(nichts gefunden);
  
  userList=suche_user_mit_thema(ZielThema);
  //es sollten nur User in der Liste sein, die nicht im Thema enthalten sind
  streiche_user_aus_Liste_die_im_Thema_sind(Liste,ZielThema);
  //da jeder User einem Thema zugeordnet ist
 // können wir auch die Useranzahl dieser Themen abfragen
   bestimmte für jeden User in der Liste das gewählte Thema 
   und damit auch Anzahl der User im Thema

   sortiere die Liste absteigend nach Anzahl der Mitglieder  in User's 
   gewähltem Thema

//Bsp: User1.aktThema=12, User in Thema12=28, User2.aktThema=14, User in Thema14=25 usw
//Liste: User1(28),User2(25),User3(22)
//die Sortierung hat den Vorteil, dass automatisch zuerst überfüllte 
//Themen abgearbeitet werden
 
If (User1_imThema_mit>16 Members)
   BLOCK
      verfrachte diesen User nach(ZielThema);
      return TRUE;
    END_BLOCK
else
    while liste<>NULL 
    WHILE_BLOCK
      aktUser=user aus der Liste;
      if (sucheUndErsetze(aktUsers_aktuellesThema,rekTiefe-1)==TRUE then
//dann heißt es, dass ein anderer User in das aktuelle Thema eingeschoben wurde
//und wir den aktUser "verwenden" können, da im Thema nun 17 User sind
      IF_BLOCK
          verfrachte aktUser nach (ZielThema);
           return TRUE;  //hier sind wir fertig
     IF_ BLOCK_END   
     liste.next();
   WHILE_ BLOCK_END
 
return FALSE; //die Liste wurde abgearbeitet, nichts gefunden
Rekursionstiefe braucht man, da ich im Moment nicht durchblicke, ob auch Loops möglich sind ;)

Es wird also Teil2 abgearbeitet, so dass nach bis zu einer bestimmten Tiefe nach möglichen Tausch-Kandidaten gesucht wird.
Teil2 Ende

Wenn Teil2 abgearbeitet wurde, haben wir zumindest eine suboptimale Lösung, also eine Verteilung, bei der die 1-Themenwahl möglichst gut berücksichtigt wurde.

Wenn immer noch Themen unterbelegt sind, kann man Teil2 wieder anwenden, nur dass diesesmal die Primärliste aus 2-er Kandidaten erstellt wird (und danach 0ler). "Suchen und Vertauschen" Funktion sollte aber imho nur nach 1-er Kandidaten suchen/vertauschen (sonst könnte es so sein, dass viele User in 2-er Themen landen, nur damit ein User nicht in ein ungewähltes Thema kommt)

So werden auch unbeliebte Themen mit 1-2-0 Usern gefüllt. Sind danach immer noch unterbelegte Themen vorhanden, so kann man alle User aus den überbelegten nehmen und eine "Lotterie" veranstalten ;)


Edit: mir fällt noch ein, dass die Primärlisten auch am besten absteigend sortiert sein sollten - so dass dann gleich die überbelegten Themen abgearbeitet werden.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben