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个状态。

（时间，空间） --> 状态

一种状态对应一个课程。

对每一个元素，遍历相应的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)开始