Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Optimierungsproblem
Borg-Cube - Do 06.11.25 14:48
Titel: Optimierungsproblem
Hallo
Ich habe folgendes Optimierungsproblem und bin ein wenig ratlos wie ich das umsetzen könnte.
Es geht um die Planung von Konferenzschienen mit mehreren Personen.
Es soll 3 Slots geben, in den Slots finden jeweils mehrere Konferenzen von Teams parallel statt. Jedem Team sind feste Teilnehmer zugeordnet. Die Teilnehmer gehören aber zum Teil mehreren Teams an.
Die Teams in den Slots sollen so gesetzt werden, dass jede Person in einem Slot an max. 1 Konferenz eingeplant ist.
Beispiel
Slot 1:
Team A (P1,P2,P3)
Team B (P4, P5, P6)
Team C (P7, P8, P9)
Das wurde bisher händisch gemacht und war teilweise sehr viel Arbeit, die Anzahl der Teams ist aber inzwischen so groß, dass es unverhältnismäßig lange dauert, daher hatte ich überlegt, ob man das mit einem Programm lösen könnte.
Wahrscheinlich ist es sinnvoll für jedes Team ein arry zu erstellen und dann da irgendwie zu vergleichen (oder im schlimmsten Fall bruteforcen?).
Da es ggf. keine Lösung für die Kombinationen gibt könnte man als Zusatzkriterium hereinnehmen, dass z.b. die ersten 2 Personen unbedingt dabei sein müssen, der Rest wäre schön, wenn es aber nicht geht, dann ist das halt so. Die Anzahl der fehlenden Personen zu minimieren wäre dann der optimale Zustand.
Wie könnte man sowas umsetzen?
Moderiert von 
Th69: Topic aus Grafische Benutzeroberflächen (VCL & FireMonkey) verschoben am Fr 07.11.2025 um 09:42
Sinspin - Fr 07.11.25 12:16
Kennst du Prolog? Das ist ein perfekter Kandidat zum lösen solcher Probleme.
Das basiert auf Brute Force.
Allerdings lässt sich recht einfach beschreiben was man will, den Rest macht Prolog.
Ich kann mich erinnern das wir sowas wie dein Beispiel mal im Studium hatten.
Ist aber so ewig her das ich da fast bei Null anfange.
Borg-Cube - Fr 07.11.25 14:18
Hast du einen Link wo ich da weitere Infos dazu finden kann?
Blup - Mi 12.11.25 10:17
Dieser Lösungsansatz berücksichtigt noch kein Zusatzkriterium.
Wenn jede Person eine fortlaufende Nummer erhält, lassen sich Mengen von Personen als Bitfelder darstellen.
Die können durch einfache binäre Operatoren verknüpft werden.
Jedes Team und jeder Slot hat eine Menge von Personen.
Überscheiden sich die Personen nicht ( Slot
and Team = [leere Menge] ), kann das Team dem Slot hinzugefügt werden ( Slot
or Team).
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| Person Team Lösung 1 Lösung 2
A B C D Slot 1 = A+B+C Slot 2 = D Slot 1 = A+D Slot 2 = B+C
1 1 0 0 0 1 0 1 0
2 1 0 0 0 1 0 1 0
3 1 0 0 0 1 0 1 0
4 0 1 0 0 1 0 0 1
5 0 1 0 0 1 0 0 1
6 0 1 0 1 1 1 1 1
7 0 0 1 0 1 0 0 1
8 0 0 1 0 1 0 0 1
9 0 0 1 1 1 1 1 1 |
Quelltext
1:
2:
3:
4:
5:
6:
7:
| Eine Funktion der eine Liste von Teams übergeben wird:
Lege einen neuen Slot an.
Finde alle Kombinationen, mit denen der aktuelle Slot aus den restlichen Teams gefüllt werden kann.
Für jede gefunde Kombination:
Wurden alle Teams verwendet, wird die Lösung gespeichert.
Andernfalls rekursiver Start der Funktion mit den noch nicht verwendeten Teams.
Entferne den angelegten Slot |
Die gefundenen Lösungen können bewertet und ausgewählt werden.
Die Reihenfolge der Slots kann nachträglich geändert werden, aber das ist im Prizip keine andere Lösung.
Borg-Cube - Mo 17.11.25 02:06
Danke für den Input. Das schaue ich mir alle mal in Ruhe an.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!