工作坊注册算法 - 多个工作坊和回合 - workshop registration algorithm

我目前正在为学生开发一个研讨会注册系统，学生可以在该系统中注册多个研讨会。学生可以从5个工作坊中进行选择，这些工作坊在所有4轮中都有。每个讲习班可容纳19名学生。

现在，我想制作一种算法，自动注册一名学生，并尽可能高效地为每一轮选择一个研讨会。

一个学生不能在多轮中选择同一个工作室。

现状：

Round 1 - space available
Workshop1 - 1 
Workshop2 - 6
Workshop3 - 1
Workshop4 - 0
Workshop5 - 4
total 12 spaces available
Round 2 - space available
Workshop1 - 1
Workshop2 - 8
Workshop3 - -1
Workshop4 - 3
Workshop5 - 1
total 12 spaces available
Round 3 - space available
Workshop1 - 1
Workshop2 - 7
Workshop3 - 1
Workshop4 - 2
Workshop5 - 1
total 12 spaces available
Round 4 - space available
Workshop1 - 0
Workshop2 - 4
Workshop3 - 0
Workshop4 - 5
Workshop5 - 3
total 12 spaces available

最好的方法是什么？

这就是我试图为一个有研讨会的学生添加的内容。

int[] chosenWorkshops;
bool workshopFound;
foreach(var round in rounds)
{
    workshopFound = false;
    foreach(var workshop in round.workshops.orderByDescending(q => q.space))
    {
        if(!chosenWorkshops.contains(workshop.ID) && workshop.space > 0)
        {
            chosenWorkshops.push(workshop.ID);
            workshopFound = true;
            break;
        }
    }
    if(!workshopFound) break;
}
if(chosenWorkshops.length == rounds.length)
{
    var student = new Student();
    foreach(var workshopID in chosenWorkshops)
    {
        student.RegisterWorkshop(workshopID);
    }
} else {
    throw new InsufficientSpaceException();
}

这个代码的问题是，它可能在最后一轮中用完了选项，因为上一轮中的可用选项已经在前几轮中使用了。

有人能把我推向正确的方向吗？

我不知道我是否完全理解你的问题，但是，如果你想让你的研讨会尽可能地填满，每个学生都应该参加所有的课程，那么我想你可以用以下方式

您可以创建一个额外的类，其中包含一个回合的订阅，并实现一个回合包含对有问题的研讨会的引用。

然后以"最佳"的方式组织数据（大多数课程都有尽可能多的人参加，并且举办了所有回合+研讨会），比如

class Organizer {
  public IList<Workshop> Workshops { get; } = new List<Workshop>();
  public IList<Student> Students { get; } = new List<Student>();
  public IList<Round> Rounds { get; } = new List<Round>();
  public void Add(Workshop workshop) {
    if (workshop == null || Workshops.Contains(workshop)) {
      return;
    }
    Workshops.Add( workshop );
  }
  public void Add(Student student) {
    if (student == null || Students.Contains(student)) {
      return;
    }
    Students.Add( student );
  }
  public void Add(Round round) {
    if (round == null) {
      throw new ArgumentException( "Round should be set!" );
    }
    if (round.Workshop == null) {
      throw new ArgumentException( "Round.Workshop must be set!" );
    }
    Rounds.Add( round );
    Add( round.Workshop );
  }
  public IList<Subscription> CreateSubscriptionsList(bool enableAverageAttendees = true) {
    IList<Subscription> results = new List<Subscription>();
    int totalRoomAvailable = Rounds.Sum( round => round.AvailableSpace ) / Workshops.Count;
    int totalUniqueRounds = Rounds.GroupBy( round => round.StartsAt.ToShortDateString() + round.EndsAt.ToShortDateString() ).Count();
    int averageStudentsPerRoundCount = (int)Math.Floor((totalRoomAvailable - (Students.Count * totalUniqueRounds)) / (double)Workshops.Count);
    // per round
    foreach ( var round in Rounds ) {
      // get all the students, with the nr of courses they are enlisted with already
      // and sort by ascending
      var additions = (from student in Students
                      select new { Student = student, CourseCount = results.Count( i => i.Student.Equals( student ) ) })
                      .OrderBy(i => i.CourseCount);
      // check how many should be added in this round
      int count = !enableAverageAttendees ? round.AvailableSpace : (averageStudentsPerRoundCount > 0 ? averageStudentsPerRoundCount : round.AvailableSpace + Math.Abs(averageStudentsPerRoundCount));
      // add all that don't attend a course at the same time, or did this course already
      foreach (var addition in additions ) {
        if (results.Any(subscription => subscription.Student.Equals(addition.Student) 
            && (round.Workshop.Equals(subscription.Round.Workshop) 
              || (round.StartsAt >= subscription.Round.StartsAt && round.EndsAt <= subscription.Round.EndsAt))
            )) {
          continue;
        }
        results.Add( new Subscription() { Round = round, Student = addition.Student } );
        count--;
        if (count <= 0) {
          break;
        }
      }
    }
    return results;
  }
}

如果使用以下参数运行：

6门课程
3轮（间隔一周）
15名学生

输出将类似于：

Workshop C# course
Round #1: 11/17/2015 - 11/18/2015
Student 1
Student 2
Round #7: 11/24/2015 - 11/25/2015
Student 13
Student 14
Round #13: 12/1/2015 - 12/2/2015
Student 10
Student 11
Workshop HTML 5
Round #4: 11/17/2015 - 11/18/2015
Student 7
Student 8
Round #10: 11/24/2015 - 11/25/2015
Student 4
Student 5
Round #16: 12/1/2015 - 12/2/2015
Student 1
Student 2
Workshop JS course
Round #3: 11/17/2015 - 11/18/2015
Student 5
Student 6
Round #9: 11/24/2015 - 11/25/2015
Student 2
Student 3
Round #15: 12/1/2015 - 12/2/2015
Student 14
Student 15
Workshop ReactJS course
Round #6: 11/17/2015 - 11/18/2015
Student 11
Student 12
Round #12: 11/24/2015 - 11/25/2015
Student 8
Student 9
Round #18: 12/1/2015 - 12/2/2015
Student 5
Student 6
Workshop Vb.net course
Round #2: 11/17/2015 - 11/18/2015
Student 3
Student 4
Round #8: 11/24/2015 - 11/25/2015
Student 15
Student 1
Round #14: 12/1/2015 - 12/2/2015
Student 12
Student 13
Workshop Webdesign
Round #5: 11/17/2015 - 11/18/2015
Student 9
Student 10
Round #11: 11/24/2015 - 11/25/2015
Student 6
Student 7
Round #17: 12/1/2015 - 12/2/2015
Student 3
Student 4

作为一个数据结构，我有以下类：

class Subscription {
  public Round Round { get; set; }
  public Student Student { get; set; }
}
abstract class IDIdentity {
  public int ID { get; set; }
}
class Workshop : IDIdentity {
  public string Name { get; set; }
}
class Round : IDIdentity {
  public Workshop Workshop { get; set; }
  public DateTime StartsAt { get; set; }
  public DateTime EndsAt { get; set; }
  public int AvailableSpace { get; set; }
}
class Student : IDIdentity {
  public string Name { get; set; }
}

您可以使用约束满足问题求解器来解决此问题。例如，使用CSPNET

如果创建代表学生及其4个时间段的类Workshop和类StudentSlot，则可以使用Variable<StudentSlot, Workshop>来跟踪研讨会分配给给定学生时间段的情况。

// The variables are the StudentSlots and the domain is the workshops they want to attend
IReadOnlyCollection<Variable<StudentSlot, Workshop>> studentAssignmentVariables = 
    studentSlots.Select(ss => new Variable<StudentSlot, Workshop>(ss, 
    studentChoices[ss.Student])).ToList();

然后你可以创建几个约束：一个是检查每个学生只参加一次研讨会：

var workshopsCanBeAttendedAtMostOnce = studentAssignmentVariables.GroupBy(x => x.UserObject.Student)
    .Select(gp => new AllDifferentConstraint<StudentSlot, Workshop>(gp));

还有另一个限制条件，即检查没有一个研讨会的学生人数超过19人（您需要自定义限制条件）。

现在你可以要求求解器来求解它。

var problem = new Problem<StudentSlot, Workshop>(studentAssignmentVariables, constraints);
var solver = new RecursiveBacktrackSolver<StudentSlot, Workshop>();
var solution = solver.Solve(problem, CancellationToken.None);

CSPNET的源代码在Github上，在那里你可以看到递归回溯是如何在给定约束的情况下解决问题的。

此处为完整样本：https://gist.github.com/IanMercer/d7670577d5e88ab2bdf6

工作坊注册算法 - 多个工作坊和回合

相关内容

最新更新

热门标签：