如何解决这个组合算法问题

作为 提出了一个解决方案(我称之为 日程

两个元组A和B冲突,如果

• 考官相同,考试不同,时间段重叠
• 这个学生已经和考官一起参加了另一项考试

注意 冲突不同于 日程

下限:

• 总时间必须大于最劳累学生的考试总长度。

1. 随机分配测试, 每个人都有不同的考官。一些 箱子包装可用于重新订购 学生:他会在下学期完成的 最短可能时间。
2. 对于其他学生,如果该学生必须参加任何已经安排的考试,则与之前安排的考试共享时间、地点和考官。
3. 以最劳累的学生为例(比如:计划外测试的最高次数),分配元组,这样就不会违反任何约束,如果必要的话,增加更多的时间和考官
4. 如果任何学生有计划外的测试,转到2。

改进上述第2步中的选择对改进至关重要;这种选择可以形成启发式搜索的基础。上述算法试图以牺牲学生时间为代价,尽量减少所需的考官人数(学生可能会提前结束一次考试,而在一天的最后一次考试中,中间什么都没有)。然而,它保证会产生法律解决办法。与不同的学生一起运行它可以用来为坚持合法答案的GA生成“起始”解决方案。

总的来说,我认为像这样的问题没有“完美的答案”,因为有太多的因素必须考虑到:学生希望尽可能减少他们花在自我检查上的总时间,就像考官一样;我们希望尽可能减少考官的数量,但对于一个考官能在一个房间里堆多少学生,也有实际的限制。此外,我们希望安排的时间“公平”,所以没有人明显比其他人更糟。因此,最好的办法就是让这些旋钮被摆弄,结果被知道(总时间、每个学生的快乐程度、每个考官的快乐程度、考试规模、公平感),并允许用户探索参数空间,做出明智的选择。

我建议使用SAT解算器。尽管这个问题可能是NP难的,但优秀的SAT求解者通常可以处理数十万个变量。退房 Chaff MiniSat 举两个例子。

不要过早地将自己局限于遗传算法,有 many other approaches .

更具体地说,只有当你能将两个解的一部分组合成一个新的解时,遗传算法才是真正有用的。对于这个问题来说,这看起来相当困难,至少如果有相似数量的人和考试,那么他们中的大多数人会直接互动。

下面是一个关于如何用GA建模的例子。

使用符号:

• T(nr)

让一个人的基因表达一个完整的预订时间表。 i、 e.个人是特定预订的列表:(i,j,t,d)

• 我是第i个考生[1,N]
• j是第j个考官[1,?]
• t是考生必须参加的第t次考试[1,t]

使用具有以下属性的适应度函数进行评估:

• 对所有被双倍录取的考官进行处罚
• 对考官闲暇时间的处罚
• 对未在规定时间内分配的考生进行处罚
• 期间内预约的每位考生的考试奖励

此函数将具有确定双人预订等的所有逻辑。。你有完整的个人计划,你现在运行的逻辑,知道每次考试的时间,在每个预订,以确定健身,你增加/减少相应的预订分数。

要使其正常工作,请考虑:

• 定义合适的GA算子

以理智的方式开始:

• 在时间段内随机选择d
• 随机排列(1,2,…,N),然后从中选取i(避免重复),对于j和t也是如此

正确的GA运算符:

说你有预约 A. 和 (一、二、三)

你可以交换a_i和b_i,你可以交换a_j和b_j,a_d和b_d,但是交换a_t和b_t可能没有意义。

你也可以循环,最好用一个例子来说明,如果N*T=4,一个完整的预订是4个元组,然后你将沿着i或j或d循环,例如沿着i循环:

a_i = b_i
b_i = c_i
c_i = d_i
d_i = a_i

你也可以考虑约束编程。看看Prolog,或者更现代的逻辑编程表达式, PyKE