0

我正在尝试制定一个教学时间表，其中一位老师有一定数量的学生每周单独教授一次（例如音乐课）。学生必须轮换，即不能每周在同一时间上课（同一时间课程之间允许的最小间隔，我称之为“轮换期”）。想出最简单的形式是微不足道的：

        Week 1  Week 2  Week 3  Week 4  Week 5  Week 6
10.00   Alice   Edgar   David   Charles Bertha  Alice
10.30   Bertha  Alice   Edgar   David   Charles Bertha
11.00   Charles Bertha  Alice   Edgar   David   Charles
11.30   David   Charles Bertha  Alice   Edgar   David
12.00   Edgar   David   Charles Bertha  Alice   Edgar

但我希望用户能够添加规则，例如 Alice 不能在第 3 周完成 10.30 或 11.00 等。我从一个简单的回溯循环开始，但很快意识到可能性的数量使这不可行。我不是一个很有经验的程序员，我是否意识到这可能会引导我进入高级编程技术。但如果有人能给我一些关于如何解决这个问题的想法，我将非常感激。我当然四处寻求帮助，但大多数讨论似乎是针对更复杂的任务，即生成整个学校的时间表。基因编程是否值得研究？我正在使用 php 将程序构建为网页。

4

3 回答 3

0

非常感谢您的各种建议。数独链接对于可能使用的方法列表非常有帮助。我想我已经找到了解决问题的方法，所以这是一种答案：

我正在使用两个简单的简单回溯循环，一个用于每一列，一个用于其中的每个插槽。每次都会计算最受约束的列，如果无法填充一列，则清除该列并返回最后一个填充的列。每个插槽都记住了它的一系列可能，所以我们可以从我们离开的地方继续。第一个循环寻找一个整齐的瞳孔块，如上例所示。如果此操作失败，则如果插槽数多于学生，则类似的循环允许列稍后开始和结束。如果这仍然不起作用，则第三个循环允许列中出现间隙（对老师来说不太好）。到目前为止，如果有人想看到它的实际效果，就在这里： http: //www.studio-soft.co.uk/timetables/

（目前只有第一个循环活动）。

格雷斯顿

于 2013-11-25T18:05:43.503 回答
0

如果您假设每个学生都必须每周来，并且从不每周在同一时间来，那么您的规则集与数独非常相似。如果是这种情况，您可能需要考虑查找一些用于解决该问题的算法，因为就解决方案探索和规则而言，它们几乎相同。

我知道那里的数独求解器以9 x 9 的速度工作，并在几分之一秒内求解。根据您的课程/周的大小，那里的技术可能会一直适用，而无需进入启发式求解器（或遗传算法等）。我建议wiki并查看backtracking、exact cover或（他们称之为）brute-force。

如果那没有帮助。你能澄清一下你对最终时间表的期望吗？例如从“默认”计划中最小化掉期的数量，或者诸如此类？另外，您是否有任何理由将其视为多周问题？问题是否可以减少为每周问题，而几周之间没有链接/连接？最后，您如何表示您的例外情况？你如何指出哪些时间对哪些学生不利？

于 2013-11-12T20:35:04.460 回答
0

用算法解决这个问题可能在计算上非常昂贵，但对于少数学生来说可能是可行的，例如您示例中的 6 个学生。

对您有利的一件事（与更一般的时间表问题相比）是学生必须每周在不同时间上课的约束。这显着减少了搜索空间。我认为我说的可能排列的数量是正确的：

n! * (n - 1)!

是n学生的数量，也是生成时间表的周数。

要解决此问题，请生成所有有效时间表的集合，并在执行此操作时检查每个生成的时间表是否符合学生指定的约束集。

您可能不需要存储这些时间表中的任何一个：如果您生成的时间表不会违反任何约束，则将其发布；如果是，请跳至下一个时间表。

如果您没有太多限制，则此方法应快速生成有效的时间表。另一方面，如果有足够的限制以使时间表不可能，则需要进行大量检查以确保没有时间表有效（在 6 名学生中，有 86,400 次检查，但随着学生人数的增加而迅速增加。）

鉴于您的要求，您使用遗传计算解决此问题的想法可能行不通。GC 擅长快速找到问题的良好解决方案（并且已成功用于时间表问题），但无法证明解决方案不存在。

于 2013-11-14T12:20:59.040 回答