Scheduling: Alle Kombinationen der Zahlen 1-28 in 4x4 matrix
Davyd
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 31.08.2015, 19:57
Titel: Scheduling: Alle Kombinationen der Zahlen 1-28 in 4x4 matrix
Moin moin.
Es geht um Scheduling.
Problem: Es gibt 8 Teams. Diese sollen an jeweils 4 Orten einem anderen Gegner gegenüberstehen. Kein Team soll ein anderes zwei mal sehen. Kein Team soll einen Ort zwei Mal sehen.
=> 8x4 matrix
Ansatz: Reduzierung der Teams auf mögliche Paarungen
1-2, 1-3, 1-4, (...), 2-3, 2-4, (...), 7-8 => 28 Möglichkeiten
Somit mache ich aus der 8x4 matrix schonmal eine 4 x 4 matrix und spare rechenzeit
Ich hatte mir gedacht, dass ich sicher mit matlab jetzt alle möglichen kombinationen der zahlen 1-28 in einer 4x4 matrix rausfinden kann. Von mir aus kann es auch ne Stunde dauern, den code durchlaufen zu lassen - aber das problem muss ich bis morgen gelöst haben.
Bisher habe ich die paarungen folgend gespeichert:
Code:
anzahl = 8;
z = 1;
for i = 1:anzahl-1 for j = i+1:anzahl
t{z} = [i,j];
z=z+1;
end end;
dann ist z = 21 und t{z} die paarung mit zwei teams.
Ich hatte mir gedacht das ganze mit for-schleifen zu machen und dann nach und nach die vorgänge mit kriterien einzugrenzen (z.b. dass die zahlen nicht zweimal vorkommen können, etc). Aber da ich kein Matlab Profi bin, frage ich hier mal um professionellen rat.
Mein ziel ist es übrigens, dass das script nachher auch kombinationen für 6, 10 und 12 teams finden kann, deshalb halte ich es variabel.
ich hoffe ich habe mein problem präzise genug beschrieben und mir kann jemand helfen.
BTW: round robin scheduling kenne ich - habe ich probiert - bringt aber nix, da jedes team genau einmal an einem ort sein soll
Muss jedes Team mal gespielt haben? Gibt ja auch noch ne Menge Lösungen, bei denen einige Teams überhaupt nicht antreten müssen.
Wenn die Lösung für dein Problem tatsächlich alle Kombinationen der Zahlen 1-28 sind, dann bekommst Du am Ende 28! = 3,05e29 Kombinationen heraus. Wenn Du es geschickt machst und jede Kombination als matrix aus 2 uint8 speicherst, benötigt jede Kombination 16 Bit = 2Byte Speicher. Deine Ergebnismatrix ist also 6,1e29 Byte groß. Das ist eine Speichermenge, die so groß ist, dass es dafür nicht mal mehr ein passendes SI-Präfix gibt. Wahlweise ist es 600.000 mal die Kapazität des Utah Data Center, wenn man die großzügigste Schätzung der Kapazität nimmt. Oder 2e11 mal das, was besagtes Rechenzentrum speichern kann, wenn man von der kleinsten geschätzten Kapazität ausgeht. In Tagen wäre das ungefähr das Alter unseres Universums.
Davyd
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 31.08.2015, 23:03
Titel:
Jedes Team muss 4 mal antreten, aber nicht gegen jedes andere.
Wenn ich mir mögliche paarungen anschaue, kann ich diese nummerieren und in gruppen einteilen
Gruppe 1: 1. 1-2; 8. 1-8
Gruppe 2: 9. 2-3; 14. 2-8
Gruppe 3: ....
Dann kann ich als einschränkung direkt sagen: Nr 1 kann nicht in der gleichen zeile mit einer zahl aus gruppe 2 stehen. Nr 2 kann nicht in der gleichen zahl mit gruppe 3 stehen, etc. (das wäre dann ja: 1-2 und 2-x in der selben zeile -> nicht möglich)
Mich interessieren auch nicht alle lösungen, sondern nur eine einzige.
es muss doch mit den oben genannten einschränkungen möglich sein, so etwas in nicht allzulanger zeit zu berechnen?
Davyd
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 31.08.2015, 23:09
Titel:
Vielleicht zur verdeutlichung nochmal eine tabelle, die das gelöste problem mit 10 teams an 5 orten darstellt:
Die Stops sind die Orte. Die Spalte ganz links sind die Zeitpunkte, zu denen die jeweils nächste runde anfängt.
Jetzt gilt es für 8 statt 10 teams paarungen zu finden, dass jedes Team jeden ort nur einmal sieht und kein team ein anderes zweimal sieht. Ich weigere mich zu glauben, dass dies unmöglich ist.
Ok, also Dein konkretes Problem ist, dass Du morgen ein Turnier veranstaltest und Du wirklich nur eine einzige sinnvolle Lösung brauchst, damit das nicht ausfallen muss, richtig? :D
Womöglich lässt sich dieses System auch auf Deine anderen Anzahlen von Teams übertragen. Spontan wüsste ich nicht, warum es schief gehen sollte. So lange die Anzahl der Teams geteilt durch die Anzahl der Orte gleich der Anzahl der Teams ist, die sich in einem Match gegenüber stehen, müsste das eigentlich klappen.
Nachtrag: es gibt natürlich keine einzige Kombination, bei der ein Team weniger als 4 mal gespielt haben muss. Da habe ich mich oben vertan.
Davyd
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 31.08.2015, 23:54
Titel:
Ja, schön wäre es, wenn es so einfach wäre. Allerdings finden alle runden Zeitgleich statt. Es ist also so ne art sudoku, wo in jeder zeile die zahlen 1-8 stehen müssen
aber danke schonmal für deine zeit das ganze ist ja doch schwieriger als man meint
Davyd
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 01.09.2015, 00:11
Titel:
Habe jetzt die folgende Lösung gefunden:
Trotzdem bleibt mein Problem bestehen. ich interessiere mich immernoch für eine variable anzahl an teams und orten
ok ich hab mal was zusammengeschustert... das ist aber noch nicht sehr gut. aber vielleicht gibt es anregungen die man weiterentwickeln kann.
Code:
for m=1:100000
norte=4;
nteams=8;
teams=1:nteams;
matchup=nan(norte,2*norte);
vs=cell(nteams,1); %teams gegen die gespielt wurde
try% manchmal werden kombinationen gewählt die nicht aufgehen. darum das try for k=1:norte
for l=1:norte
teams2=setdiff(teams,matchup(:,2*l-1:2*l)); % teams die noch nicht am ort gespielt haben
teams2=setdiff(teams2,matchup(k,:)); %teams die noch nicht um die zeit spielen
matchup(k,2*l-1)=teams2(randi(numel(teams2))); % ein team zufällig auswählen
teams2=setdiff(teams,matchup(:,2*l-1:2*l)); % teams die noch nicht am ort gespielt haben
teams2=setdiff(teams2,vs{matchup(k,2*l-1)}); % teams die noch nicht gegen das schon eingetragene team gespielt haben
teams2=setdiff(teams2,matchup(k,:)); % teams die nicht um die zeit spielen.
matchup(k,2*l)=teams2(randi(numel(teams2))); % zufälligen gegner auswählen
vs{matchup(k,2*l)}=[vs{matchup(k,2*l)},matchup(k,2*l-1)]; % begegnung in die vs tabelle eintragen
vs{matchup(k,2*l-1)}=[vs{matchup(k,2*l-1)},matchup(k,2*l)]; % begegnung in die vs tabelle eintragen end end catch err
end ifall(~isnan(matchup(:))) %% falls eine lösung gefunden wurde abbrechen. break end end
Habe nochmal ein bisschen nachgedacht: ich fürchte, das Problem ist nur durch Raten (ausprobieren) lösbar. Das Programm ist dann wirklich nicht mehr sehr weit von einem Sudoku-Solver entfernt, der auch ausprobieren kann.
@winkow: ich weiß nicht, ob ich das Ergebnis richtig interpretiere, aber irgendwas haut da noch nicht ganz hin. Bekomme an einem Ort z.B. die Paarungen 1-3 und 3-1 raus.
@winkow: ich weiß nicht, ob ich das Ergebnis richtig interpretiere, aber irgendwas haut da noch nicht ganz hin. Bekomme an einem Ort z.B. die Paarungen 1-3 und 3-1 raus.
hmm ist mir bis jetzt in den testläufen noch nicht passiert.
ort sind die spalten. also ort 1 ist spalte 1 und 2 ort 2 ist spalte 3 und 4
eigendlich sollte das von dir beschrieben verhalten nicht möglich sein durch setdiff. aber kann natürlich falsch sein mein code.
_________________
Ah, dann habe ich es falsch gelesen. In meinem Kopf sind die Orte zwar auch die Spalten, die Paarungen aber jeweils nebeneinander und nicht untereinander.
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum 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. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
das ganze ist ja doch schwieriger als man meint
RSS