python 回溯法 子集树模板 系列 —— 6、排课问题-阿里云开发者社区

开发者社区> 吞吞吐吐的> 正文

python 回溯法 子集树模板 系列 —— 6、排课问题

简介:
+关注继续查看

问题

某乡村小学有六个年级,每个年级有一个班,共六个班。

周一到周五,每天上6节课,共计30节课。

开设的课程

一年级:语(9)数(9)书(2)体(2)美(2)音(2)德(2)班(1)安(1)
二年级:语(9)数(9)书(2)体(2)美(2)音(2)德(2)班(1)安(1)
三年级:语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1)
四年级:语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1)
五年级:语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1)
六年级:语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1)

要求
  • 各门课课时必须相符
  • 周一最后一节课班会,周五最后一节课安全教育是固定的。
  • 上午只能排语、数、英
  • 全校只有两位音乐老师
  • 三年级的数学不能排在周五上午第三节(三年级数学潘老师家里有事)

分析

将每一个(时间空间)点对,作为一个元素。这些元素都具有各自的[状态1,状态2,状态3,状态4,状态5,状态6,状态7,状态8,状态9]共9个状态

时间空间) --> 状态

709432-20170530183715274-1975358002.jpg

一种状态对应一个课程。

对每一个元素,遍历相应的9种状态。

解的长度是固定的,30 * 6 的二维数组

套用子集树模板即可。

本问题只需要解决存在性。也就是说,只要找到一个符合要求的解就ok了。

此问题的本质就是,各(时,空)点对的取各自状态搭配的问题。

代码


'''排课问题'''

# 作者:hhh5460 
# 写于:2017年5月30日22时33分
# 声明:此算法的版权归本人所有


m = 30  # 一周课时数(时间)
n = 6   # 全校班级数(空间)
o = 30 * 6  # 元素个数,即(时, 空)点对的个数

# 6个班开始的课程(状态空间)
a = [['语','数','书','体','美','音','德','班','安'], # 一年级
     ['语','数','书','体','美','音','德','班','安'], # 二年级
     ['语','数','英','体','美','音','德','班','安'], # 三年级
     ['语','数','英','体','美','音','德','班','安'], # 四年级
     ['语','数','英','体','美','音','德','班','安'], # 五年级
     ['语','数','英','体','美','音','德','班','安']] # 六年级

# 课时数
b = [[9,9,2,2,2,2,2,1,1],
     [9,9,2,2,2,2,2,1,1],
     [8,8,4,2,2,2,2,1,1],
     [8,8,4,2,2,2,2,1,1],
     [8,8,4,2,2,2,2,1,1],
     [8,8,4,2,2,2,2,1,1]]

x = [[0 for _ in range(n)] for _ in range(m)] # 一个解,m*n 的二维数组


is_found = False  # 结束所有递归标志!!!!!

# 冲突检测
def conflict(t, s):
    '''只考虑刚刚排的x[t][s]'''
    
    global m,n,o,a,b,x
    
    # 一、各门课课时数必须相符(纵向看)
    # 1.前面已经排的课时不能超
    if [r[s] for r in x[:t+1]].count(x[t][s]) > b[s][a[s].index(x[t][s])]: # 黑科技,不要眼花!
        return True
    # 2.后面剩的课时不能不够
    if [r[s] for r in x[:t+1]].count(x[t][s]) + (m-t-1) < b[s][a[s].index(x[t][s])]:
        return True
    
    # 二、周一最后一节课班会,周五最后一节课安全教育是固定的。
    # 1.周一最后一节课班会
    if x[t][s] == '班' and t != 5:
        return True
    # 2.周五最后一节课安全教育
    if x[t][s] == '安' and t != 29:
        return True
    
    # 三、上午只能排语、数、英
    if t % 6 in [0,1,2] and x[t][s] not in ['语','数','英']:
        return True
        
    # 四、只有两个音乐老师(横向看)
    # 前面已经排的班级不能有3个及以上的班级同时上音乐课
    if x[t][s] == '音' and x[t][:s+1].count('音') >= 3: 
        return True
    
    # 五、三年级的数学不能排在周五上午第三节(三年级数学潘老师家里有事)
    if x[t][s] == '数' and t==5*n+3-1:
        return True
    
    return False # 无冲突
    
    
# 套用子集树模板
def paike(t, s): # 到达(t,s)时空点对的位置
    global m,n,o,a,b,x, is_found
    
    if is_found: return # 结束所有递归
    
    if t == m:  # 超出最尾的元素
        #print(x)
        show(x) # 美化版
        is_found = True # 只需找一个
    else:
        for i in a[s]: # 遍历第s个班级的对应的所有状态,不同的班级状态不同
            x[t][s] = i
            if not conflict(t, s): # 剪枝
                ns = [s + 1, 0][s + 1 == n] # 行扫描方式
                nt = [t, t + 1][s + 1 == n]
                paike(nt, ns) # 去往(nt, ns)时空点对
                
# 可视化一个解x
def show(x):
    import pprint
    
    pprint.pprint(x[:6])    # 全校的周一课表
    pprint.pprint(x[6:12])  # 全校的周二课表
    pprint.pprint(x[12:18]) # 全校的周三课表
    pprint.pprint(x[18:24]) # 全校的周四课表
    pprint.pprint(x[24:])   # 全校的周五课表


# 测试
paike(0, 0) # 从时空点对(0,0)开始

效果图

正在运行中... ... 稍后奉上。

补:现在时间2017年6月1日7时40分,程序已运行34+时,还没有结果,囧!

之所以这么慢,其原因可能是递归太多了!

好吧,那只能等我以后将递归版本改为迭代版本,再运行看其结果如何了。

本文转自罗兵博客园博客,原文链接:http://www.cnblogs.com/hhh5460/p/6921040.html如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9497 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13186 0
python 回溯法 子集树模板 系列 —— 4、数字组合问题
问题 找出从自然数1、2、3、...、n中任取r个数的所有组合。 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集。
786 0
python 回溯法 子集树模板 系列 —— 1、8 皇后问题
问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0、1、2、...、7列,我们认为每一行的皇后有8种状态。
776 0
python 回溯法 子集树模板 系列 —— 5、取物搭配问题
问题 有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子、一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析 换个角度看,现有头、身、腿三个元素,每个元素都有各自的几种状态。 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状态 从头开始,自上而下,遍历每个元素的所有状态。
639 0
python 回溯法 子集树模板 系列 —— 9、旅行商问题(TSP)
问题 旅行商问题(Traveling Salesman Problem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初始城市,问他应选择什么样的路线才能使所走的总费用最短? 分析 此问题可描述如下:G=(V,E)是带权的有向图,找到包含V中每个结点一个有向环,亦即一条周游路线,使得这个有向环上所有边成本之和最小。
979 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
6895 0
4852
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载