寻找最佳时间表的算法

Question

我正在寻找解决以下问题的算法或一般方法：

同学A,...,M各模块笔试题记。题词如下table。如果每个学生每天可以做一次考试，组织这节课至少需要多少天？

          |A|B|C|D|E|F|G|H|I|J|K|L|M|
Module 1  | | | |X| |X|X| |X|X| | | |
Module 2  |X| | | | |X| | | |X|X| | |
Module 3  | |X| | | | | |X| | |X| |X|
Module 4  |X| | |X| | | | | | | | | |
Module 5  | | |X| |X| | | | |X| | |X|
Module 6  | | |X| | | | |X| | | | | |
Module 7  |X|X| | | | | | |X| |X| | |
Module 8  | | |X| | | |X| | | | |X| |

我如何解决这个问题？

Answer 1

有图形着色。

为每个模块创建一个节点，每当学生有模块 i 和 j 时，节点 i 和 j 之间就有一条边。给图表上色，颜色代表天数。只要模块不能在同一天，节点之间就会有一条边，因此着色给出了有效的时间表。最少的着色给出最短的时间表。

作为实际解决实例的建议（即图形着色算法），对于这个大小，我会采用一种简单的相当蛮力的方法，有点像这样：

for k in 1 ..
    tryColour(k, 1)

tryColour(k, i):
    if i > numnodes:
        found it
    for c in 1 .. k:
        if node i can have colour c:
            colours[i] = c
            tryColour(k, i+1)

我没有注意那里的细节，只是为了这个想法：选择一个节点，给它一个不是立即不可能的颜色，然后递归地给其余的着色。如果递归着色为空，请使用下一种颜色重试。用越来越多的颜色做这件事，直到找到解决方案。

Answer 2

一旦出现 table 不兼容，应该如下所示：

a[1] = [2,4,5,7,8]
a[2] = [1,3,4,5,7]
a[3] = [2,3,5,6,7]
a[4] = [1,2,7,8]
a[5] = [1,2,3,6,8]
a[6] = [3,5,8]
a[7] = [1,2,3,4]
a[8] = [1,5,6]

我认为它的想法是：

创建一个日节点，将一个模块及其不兼容的模块放入其中。
然后，只要任何给定节点仍有未解决的不兼容模块：
- 从该节点弹出一个不兼容的模块，
- 要么将其放置在兼容的节点中，要么创建一个新的日节点
- 然后从它仍然存在的任何其他日期节点中删除该模块

每个日节点都有一个当天将发生的模块列表，以及当天不能发生的模块列表。不过，我不完全确定如何证明它是最优的。好像是，因为它考虑了与最先看到的模块的不兼容问题。

快速而肮脏的 python 实施示例：https://repl.it/BY2B

寻找最佳时间表的算法

Algorithm to find optimal timetable

java

algorithm

permutation