Konfliktfreie Menge finden < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
(da 1. Posting muss man das wohl hinschreiben)
Hallo zusammen,
ich arbeite momentan an einer größeren Projektarbeit und bin dabei nun auf folgendes praktisches Problem gestoßen:
Abstrakt ausgedrückt, habe ich eine gewisse Anzahl von Mengen mit Untermengen, bspw:
Menge1 = { (1,2,3,4), (4,3,2,1), (5,6,7,4) }
Menge2 = { (0,1,9,9), (8,9,7,4) }
...
MengeN = ...
Nun geht es in erster Linie darum, aus allen Mengen jeweils ein Untermenge zu wählen, so dass die endgültige Auswahl konfliktfrei ist. In diesem Minimalbeispiel für die Menge1 und Menge2 wäre das also: (5,6,7,4) aus Menge1 und (0,1,9,9) aus Menge2. Für das Beispiel sind es nun Zahlen, die also ohne Konflikt sein sollen. Im Endeffekt ist das ja aber egal, ob es Zahlen oder bspw. Lebensmittel sind. Ziel ist es also immer, die Untermengen so zu wählen, dass Elemente der Untermenge in keiner anderen Untermenge vorkommen.
Im Endeffekt sind diese Untermengen auch gewichtet, d.h., sobald eine konfliktfreie Auswahl getroffen wurde, soll dahingehend optimiert werden, dass die Summe aller Gewichte Minimal wird.
Die Frage ist also:
1) wie wähle ich effizient eine konfliktfreie Menge?
2) wie optimiere ich mein Ergebnis?
Die Anzahl der Mengen ist ~200 wobei jede für sich genommen ca. 30 Untermengen besitzt. Die tatsächliche Anzahl ist also durchaus überschaubar!
Ich habe zwar schon nach Algorithmen bzw. Vorgehensweisen gesucht, bin aber leider noch nicht auf das gestoßen was mir mein Problem löst.
Danke für eure Hilfe!
algonoob
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:08 Do 18.04.2013 | | Autor: | sandp |
hey,
ich probier dir mal zu helfen, obwohl ich auch kein Profi in solchen Sachen bin.
Soweit ich das sehe gehört dein Problem zu den CSPs (Constraint Satisfaction Problems) heißt sowas wie Probleme mit Nebenbedingungen.
Da gibts Möglichkeiten wie die Backtracking-Suche.
Um die Backtracking-Suche zu optimieren gibt es Ansätze wie Foward Checking.
Ich denke wenn du nach diesen Begriffen suchst, wirst du einiges finden, ansonsten kann ich dir auch noch Auskunft geben.
Gruß
sandp
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Mi 01.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
