java - 寻找最佳时间表的算法

Question

我正在寻找一种算法或一般方法来解决以下问题:

学生 A,...,M 被指定参加各个模块的笔试。铭文如下表所示。如果每个学生每天可以做一次考试，那么至少需要多少天来组织这节课？

          |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)

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