我正在搜索一种解决以下问题的算法或一般方法:
学生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| |
我该怎么解决这个问题?
发布于 2015-11-09 19:01:05
用图形着色。
为每个模块设置一个节点,每当学生有模块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)
我没有注意细节,只是为了这个想法:选择一个节点,给它一个不是立即不可能的颜色,然后递归地给其余的颜色。如果递归着色结果为空,请用下一种颜色重试。用越来越多的颜色做这件事,直到你找到解决方案。
发布于 2015-11-09 19:55:45
一旦您有了一个不兼容的表,它应该如下所示:
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
https://stackoverflow.com/questions/33616140
复制相似问题