Ich bin ein Tutor für Laborpraktiken an der Universität, basierend auf den Kommentaren der Studenten aus dem letzten Jahr, die wir, mein Chef und ich, ansprechen wollten. Mein Chef hat sich entschieden, ein C-Skript zu schreiben, und ich habe Python (Python-Einschränkung) ausgewählt, um unser Problem zu lösen.

Informationen

• Es gibt 6 Sitzungen
• Es gibt 4 Rollen
• Es gibt 6 Übungen
• Es gibt 32 Studenten
• Es gibt 4 Studenten pro Team

Problem :

Weisen Sie jedem Schüler 4 Rollen in 4 Übungen in 4 verschiedenen Sitzungen zu.

Einschränkungen:

1. Die Schüler sollten einmal eine Rolle spielen
2. Die Schüler sollten 4 von 6 verschiedenen Übungen machen
3. Die Schüler sollten nur eine Übung pro Sitzung machen
4. Der Schüler sollte denselben Partner nur einmal treffen

Vorlagen:

Hier ist die Vorlage, die ich für Schüler empfinde, bei der jedes Team aus 4 Schülern besteht. Den Positionen [0, 1, 2 oder 3] sind Rollen zugewiesen. Jede verfügbare Position ist von 1 bis 128 nummeriert

[# Semester
   [ # Session
     [ # Practice/Team
1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],
 [[25, 26, 27, 28],
  [29, 30, 31, 32],
  [33, 34, 35, 36],
  [37, 38, 39, 40],
  [41, 42, 43, 44],
  [45, 46, 47, 48]],
 [[49, 50, 51, 52],
  [53, 54, 55, 56],
  [57, 58, 59, 60],
  [61, 62, 63, 64],
  [65, 66, 67, 68],
  [69, 70, 71, 72]],
 [[73, 74, 75, 76],
  [77, 78, 79, 80],
  [81, 82, 83, 84],
  [85, 86, 87, 88],
  [89, 90, 91, 92],
  [93, 94, 95, 96]],
 [[97, 98, 99, 100],
  [101, 102, 103, 104],
  [105, 106, 107, 108],
  [109, 110, 111, 112]],
 [[113, 114, 115, 116],
  [117, 118, 119, 120],
  [121, 122, 123, 124],
  [125, 126, 127, 128]]]

Mit anderen Worten :

Dies ist eine Sitzung:

 [[1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],

Diese Teams machen die gleiche Übung:

[
    [1, 2, 3, 4],
    [25, 26, 27, 28],
    [49, 50, 51, 52],
    [73, 74, 75, 76],
    [97, 98, 99, 100],
    [113, 114, 115, 116]
]

Diese Positionen spielen die gleiche Rolle:

[
   1,
   5,
   9,
   13,
   17,
   21,
   25,
   ...
]

Was ich bisher habe:

Mit Python-Constraint konnte ich die ersten drei Constraints validieren:

Valid solution : False
            - sessions  : [True, True, True, True, True, True]
            - practices : [True, True, True, True, True, True]
            - roles     : [True, True, True, True]
            - teams     : [False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False]

Für diejenigen, die interessant sein mögen, mag ich einfach Folgendes:

Für jede Bedingung verwende ich AllDifferentConstraint . Zum Beispiel mache ich für eine Sitzung:

problem.addConstraint(AllDifferentConstraint(), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24])

Ich bin nicht in der Lage, das Team einzuschränken. Mein letzter Versuch im Großen und Ganzen semesterwar folgender:

    def team_constraint(self, *semester):
        students = defaultdict(list)

        # get back each teams based on the format [# Semester [ #Session [# Practice/Team ... 
        teams = [list(semester[i:i+4]) for i in range(0, len(semester), 4)]

        # Update Students dict with all mate they work with
        for team in teams:
            for student in team:
                students[student] += [s for s in team if s != student]

        # Compute for each student if they meet someone more than once 
        dupli = []
        for student, mate in students.items():
            dupli.append(len(mate) - len(set(mate)))

        # Loosly constraint, if a student meet somone 0 or one time it's find
        if max(dupli) >= 2:
            print("Mate encounter more than one time", dupli, min(dupli) ,max(dupli))
            return False
        pprint(students)
        return True

Fragen :

1. Kann ich für die Teambedingungen tun, was ich will? Ich meine, ich habe keine Ahnung, ob es möglich ist, jedem Schüler 12 Partner zuzuweisen, und jeder von ihnen trifft denselben Partner nur einmal.
2. Habe ich für die Teambeschränkung einen performanteren Algorithmus verpasst?
3. Irgendeine Pistole, der ich folgen kann?

Die Hauptfrage würde mit so etwas wie ...

   def person_works_with_different():
        # over all the sessions, each person works with each other person no more than once.
        # 'works with' means in 'same session team'
        for p in all_people:
            buddy_constraint = []
            for s in all_sessions:
                for g in all_teams:
                    p_list = [pv[k] for k in filter(lambda i: i[P] == p and i[S] == s and i[G] == g, pv)]
                    for o in all_people:
                        if o != p:  # other is not person
                            o_list = [self.pv[k] for k in filter(lambda i: i[self.P] == o and i[self.S] == s and i[self.G] == g, self.pv)]
                            tmp = model.NewBoolVar('')
                            buddy_constraint.append(tmp)
                            model.Add(sum(o_list) == sum(p_list)).OnlyEnforceIf(tmp)
                            # tmp is set only if o and p are in the same session/team
            # The number of times a student gets to take part is the number of roles.
            # The size of the group controlled by the number of roles
            model.Add(sum(buddy_constraint) = all_roles * (all_roles - 1)) 

Bearbeiten hinzugefügt

Ich habe mir gestern Ihr Problem noch einmal angesehen - (zugegebenermaßen nicht lange, da ich gerade viel Arbeit habe) und ...

Zunächst sehe ich, dass Ihre "Team" -Entität so ziemlich das ist, was ich als "Aktions" -Entität bezeichnet habe, und im Nachhinein denke ich, dass "Team" (oder "Gruppe") ein besseres Wort dafür war.

Wenn Sie die Einschränkungen immer noch als schwierig empfinden, empfehlen wir Ihnen, sie aufzubrechen und einzeln zu bearbeiten - insbesondere die Einschränkungen für Team / Person / Sitzung, gefolgt von den Einschränkungen für Rolle / Aufgabe.

/ Bearbeiten hinzugefügt

team: a gathering of 4 persons during a session
person (32): a participant of a team
session (6): time: eg, 8am -10am
role (4): what responsibility a person has in an action
task (6): type of action

A person does:
 0..1 action per session-group
 1 role per action
 1 task per action
 0..1 of each task
 1 of each role in an action
 4 persons in an action

A person meets each other person 0..1 times
An action requires exactly 4 people

Ich hatte kürzlich ein ähnliches Problem und wandte mich am Ende den OP-Werkzeugen zu. https://developers.google.com/optimization/cp/cp_solver

Sehen Sie sich insbesondere das Problem mit der Planung von Krankenschwestern an: https://developers.google.com/optimization/scheduling/employee_scheduling#nurse_scheduling

Wie auch immer, das Problem ist nicht zu komplex, daher wäre die Verwendung eines Lösers für Sie möglicherweise übertrieben.

Ebenso ist es für diese Art von Problem möglicherweise besser, ein Diktat mit Tupelschlüssel zu verwenden, um Ihre Variablen zu speichern, als verschachtelte Listen:

{Team, Sitzung, Person: BoolVar}

Der Hauptgrund ist, dass Sie dann Einschränkungen über Filter anwenden können, was viel einfacher ist, als verschachtelte Listenmanipulationen durchführen zu müssen, um beispielsweise eine Einschränkung auf Personen / Teams anzuwenden (wobei Person Index 2 und Team Index ist) 0):

for p in all_persons:
    for t in all_teams:
        stuff = [b_vars[k] for k in filter(lambda i: i[2] == p and i[0] == t, b_vars)]
        model.Add(sum(stuff) == 4)  # persons per team == 4

Nur eine Idee für einen Permutationsalgorithmus, bei der jede Iteration auf einen der Schüler oder auf eine Sitzung konzentriert werden kann:

Session 1:
Roles
1,2,3,4
Students
1,2,3,4

(Note is 1st permutation 1234)

Sess 2 for student 1
Roles 1234
Students 5,1,7,6

Hier findet Schüler 2 in Sitzung 1 von Schüler 1 statt und geht so weiter

Roles 1234
St 2,5,6,7 

Weiter mit Schüler 1 S3 R 1234 St 10,9,1,8

S4
R 1234
St 11,12,13,1

Am Ende entfernen Sie Interaktionen für Schüler 1, wie bei Permutationen für die nächste Iteration, die Sie aktuell entfernen.

Es ist wie ein Zauberwürfel.

Wenn Sie dies codieren oder einen Code mit diesem Algo kennen, lassen Sie es mich wissen.

Vielleicht mit den itertools Permutationen

Sitzungen, die> als Praktiken sind, sind meiner Meinung nach nicht so relevant für ihre Anzahl. Nur ein Pool, um mehr zu nehmen, wenn Sie ausgehen oder mehr Platz für die Rotation. Vielleicht könnte das Problem vereinfacht werden, indem zuerst 4 Sitzungen = Übungen angestrebt werden?