学生时间调度算法

我需要找到一个算法来找到最好的时间来让我们说一个研究小组。该系统具有关于一组学生及其课程表的信息。系统应该给与会面时间，与任何人的课程时间表没有冲突。什么是解决这个问题的最好方法。我正在寻找任何调度算法，但没有找到合适的人。学生时间调度算法

在此先感谢

来源

2010-01-18 user171034

我记得这个问题的最佳解决方案是由遗传算法

产生的解看到此链接http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx

来源

2010-01-18 16:00:24 dfens

我不认为GA对这个问题会有很大的帮助，因为没有适合评估解决方案的标准。乙醚是空闲的时间段，或者没有。 – 2010-01-18 16:16:16

，因为有一个最佳解决方案可以在小于指数时间内找到，所以GA真的不需要！ – Agos 2010-01-18 16:17:59

不，你正在考虑制定一个时间表，这是一个NP-Complete问题。这个问题要简单得多。 :) – JPvdMerwe 2010-01-18 16:20:57

有趣的问题。

这是我会做什么：

首先，对齐所有timescheduals，为了一切学生（例如开始星期一，每天在24小时devided）。您可以为每个周期使用布尔值或整数，并将它们存储在数组中。
然后一起对所有调度执行加法操作。

然后看起来是这样的，例如：

Student A: 11100000111111100000 
Student B: 00000011111000010001 
Student C: 00000000111111110001 
_______________________________+ 
      11100022333222220002 
       ^^^   ^^^

然后，你需要使用一个简单的循环，其保持当前的轨迹找到所有间隙在阵列中（用零区）零长度。记忆开始和结束索引并将其翻译回来（步骤1的反向）到一个时间区域。

来源

2010-01-18 16:03:10 Pindatjuh

谢谢，我正在寻找更多的算法方法。 – user171034 2010-01-18 16:05:22

+1为简单起见。研究小组的规模和一天中的职位空缺数量足够小，以至于对这个NP问题的大多数暴力方法都是一种选择。对上述解决方案的一个推动是使用整数数组（每个学生一个数组，每个时隙一个整数）并且对时隙值进行求和而不是对它们进行求和，即布尔方式。这个系统允许SUM数组提供更好的选择“第二选择”的指导，即当一些学生不可用时满足可能性。 – mjv 2010-01-18 16:16:14

谢谢，更新了这个例子。 – Pindatjuh 2010-01-18 16:30:13

这是一个匹配的问题，并且可以通过maximum flow algorithm

每个学生和研究组被解决是在一个有向图，并输入用于一个节点的每个学生具有一个流动单元作为输入，并连接到所有研究组中节点。每个研究节点组具有无限的输出能力，当网络中的流量是最大的，你有你的正确组合

也Introduction to Algorithms（流网络章）见

来源

2010-01-18 16:04:13 Alon

+1。欲了解更多相关材料，请查阅http：// en。wikipedia.org/wiki/Linear_Programming – Agos 2010-01-18 16:20:21

最大流量远不是简单的代码，使用一分钟的分辨率就可以轻松使用某种类型的蛮力。 – JPvdMerwe 2010-01-18 16:29:28

每天有24*60 = 1440分钟。所以你可以很容易地蛮力，因为你不需要超过一分钟的准确度。不过，我要描述一个简单的DP。

您可以创建一个布尔数组来存储该分钟中组的学生是否有班级。你也有第二个数组。该数组存储此块中和左侧的空余数量。所以你可以做的是从右向左遍历布尔数组，如果块中有一个类，则使数字为0，否则将其加1，再加上前一分钟的数字。

不过，我觉得我的解释缺乏的，所以这里是伪代码：

blocked = <boolean array>; 
numtoleft = <array containing the counts>; 
if blocked[0]: 
    numtoleft[0] = 0; 
else: 
    numtoleft[0] = 1; 

for i = 1 to 1440-1: 
    if blocked[i]: 
     numtoleft[i] = 0; 
    else: 
     numtoleft[i] = numtoleft[i-1];

然后你可以通过“numtoleft”阵列中发现的最大数量容易找到的最大的开放式插槽，您可以添加限制到你正在看的时代。

编辑：

下面是蟒蛇的算法：

def largestslot(blocked, startminute, endminute): 
    numtoleft = [0]*1440 
    numtoleft[startminute] = 0 if blocked[startminute] else 1 
    for i in xrange(startminute+1, endminute+1): 
     numtoleft[i] = 0 if blocked[i] else 1 
    ansmax = max(numtoleft[startminute:endminute+1) 
    ansi = numtoleft.index(ansmax) 
    return (ansi-ansmax, ansi)

来源

2010-01-18 16:08:15 JPvdMerwe

我不认为这是一个优雅的解决方案。 – user171034 2010-01-18 16:10:05