首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >寻找最优时间表的算法

寻找最优时间表的算法
EN

Stack Overflow用户
提问于 2015-11-09 18:54:13
回答 2查看 172关注 0票数 1

我正在搜索一种解决以下问题的算法或一般方法:

学生A,.,M为各模块的笔试题名。铭文见下表。如果每个学生每天都能做一次考试,那么至少需要多少天才能安排这次考试?

代码语言:javascript
运行
复制
          |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| |

我该怎么解决这个问题?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2015-11-09 19:01:05

用图形着色。

为每个模块设置一个节点,每当学生有模块i和j时,节点i和j之间就有一个边。当模块不能在同一天出现时,节点之间存在边缘,因此着色给出了一个有效的调度。最小的着色给出最短的时间表。

作为实际解决实例的建议(例如,图着色的算法),对于这个大小,我会采取一种简单的相当蛮力的方法,有点像这样:

代码语言:javascript
运行
复制
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)

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

票数 1
EN

Stack Overflow用户

发布于 2015-11-09 19:55:45

一旦您有了一个不兼容的表,它应该如下所示:

代码语言:javascript
运行
复制
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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/33616140

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档