Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

kombinatorische Optimierung: n Elemente in Gruppen stecken.
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> kombinatorische Optimierung: n Elemente in Gruppen stecken.
 
Autor Nachricht
Giles2k
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.01.2009
Beiträge: 4

BeitragVerfasst am: 08 Feb 2009 - 08:10:50    Titel: kombinatorische Optimierung: n Elemente in Gruppen stecken.

Hallo,
mein Problem:
n Personen sollen sich in Gruppen von maximal 4 Personen treffen.
Jede Person hat 1 bis 10 Eigenschaften.
Innerhalb einer solchen Gruppe haben die Personen eine gemeinsame Eigenschaft.
Jede Person soll in genau eine Gruppe gesteckt werden.
Wie muss ich vorgehen um eine möglichst kleine Anzahl von Gruppen mit möglichst vielen (max=4) Personen zu bekommen?

Beispiel zur Verdeutlichung mit nur 6 Eigenschaften (,wobei beim eigentlichen Problem k fest ist):
Menge P von 12 Personen: P = {1,2,3,4,5,6,7,8,9,10,11,12}
Menge E1 der Personen mit der Eigenschaft 1: {2,3,5,7,12}
Menge E2 der Personen mit der Eigenschaft 2: {2,4,5,6,8,9,12}
Menge E3 der Personen mit der Eigenschaft 3: {1,2,4,5,7,10,11,12}
Menge E4 der Personen mit der Eigenschaft 4: {3,6,8,9}
Menge E5 der Personen mit der Eigenschaft 5: {4,6,8,9,11}
Menge E6 der Personen mit der Eigenschaft 6: {1,2,4,5,7,10,11,12}
=> eine optimale Gruppierung: G = {(1,2,4,5),(3,6,8,9),(7,10,11,12)}

Ich komme nicht auf einen Algorithmus mit der ich zu einer Menge P und den Eigenschaftsmengen E1,...,E10 eine optimale Gruppering findet. Kombinatorisch betrachtet ist es schon bei wenigen Personen wie im Beispiel zu zeitaufwendig alle Möglichkeiten durchzuprobieren.

vielen Dank im Vorraus
Kleinhilbert
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 04.11.2006
Beiträge: 81

BeitragVerfasst am: 11 Feb 2009 - 19:04:21    Titel:

Hallo Giles2k!

Für solche Probleme kann man die Heuristik „Lokale Suche“ verwenden. Die garantiert zwar keine Optimallösung, kommt aber meist in kurzer Zeit zu guten bis sehr guten Lösungen.
http://de.wikipedia.org/wiki/Lokale_Suche

Eine zulässige Lösung könnte man so repräsentieren:
Bsp:
12 Personen, hier Mengen 1 bis 7
x = [1 1 2 1 3 4 5 6 7 2 1 1]
Zur Menge 1 gehören Person 1, 2, 4, 11, 12;
zur Menge 2 gehören Person 3 und 10 usw.

Als Nachbarschaft könnte man im Vektor x nacheinander jede Person von einer Menge in eine andere Menge tun.
Bsp:
Reihenfolge der Suche
permutation = [10 3 1 4 6 5 8 7 2 9 11 12] (zufällige Permutation)
Jetzt nimm zuerst Person 10 und ändere die Zugehörigkeit von Person 10 im Vektor x.
Falls Zielfunktion kleiner wird behalte Lösung sonst mache die Änderung rückgängig.
Falls alle Änderungen für Person 10 probiert, dann nimm Person 3 und ändere ihre Zugehörigkeit zu einer Menge im Vektor x.
Falls Zielfunktion kleiner wird behalte Lösung sonst mache die Änderung rückgängig.
usw.

Die Zielfunktion sollte für „schlechte“ Lösungen einen großen Wert haben für „gute“ Lösungen einen kleinen Wert.
Wenn in jeder Gruppe maximal 4 Personen seinen sollten, dann kann ich beispielsweise bei Überschreitung dieser Zahl 1 pro Überschreitung addieren.

Viele Grüße
Ronald
Giles2k
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.01.2009
Beiträge: 4

BeitragVerfasst am: 12 Feb 2009 - 20:55:51    Titel:

vielen Dank!

Ich hatte schon befürchtet selbst eine Simulation durchführen zu müssen.
Kleinhilbert
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 04.11.2006
Beiträge: 81

BeitragVerfasst am: 15 Feb 2009 - 16:35:43    Titel:

Hallo Giles2k!

Für „wenige“ Variablen kann man so was natürlich per Hand lösen. Ab einer bestimmten Problemgröße kommt man um den Computereinsatz nicht mehr herum.
Die von mir vorgeschlagene Heuristik „lokale Suche“ kommt in sehr kurzer Zeit zu relativ guten Lösungen. Praktischerweise wird man z.B. 1000 Läufe der lokalen Suche ausführen und sich die beste Lösung merken. Dies sollte mit einem heutigen Computer und einem schnellen Compiler nur ein paar Sekunden dauern.

Viele Grüße
Ronald
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> kombinatorische Optimierung: n Elemente in Gruppen stecken.
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum