调度优化问题将N个用户数成对分布在n2个房间上

2024-03-29 15:01:16 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个计划问题要解决,但不确定如何进一步解决它。 我们有26名参与者,我们必须在13个虚拟房间中进行1对1的分配 会议。这只适用于10节课

我应该能够设置限制,就像人A不应该和人B说话一样。 但如果不可能,这可以放松

因此,我们的目标是制定如下时间表:

  • 输入=26个电子邮件地址
  • 限制=a无法与b/C对话无法与D对话
  • 输出=10 x 13个会话,1对1

第1课时

  • 房间1->;约翰-马克
  • 其他房间
  • 13号房间->;大卫-巴特

第二课时

  • 1号房间约翰->;巴特
  • 其他房间
  • 大卫马克13号房间

这总共需要10次会议

最好的方法是什么? 我主要需要一些帮助来解决这个问题

相关的问题是这个


Tags: 方法gt目标电子邮件地址create时间表对话
1条回答
网友
1楼 · 发布于 2024-03-29 15:01:16

这里有一个算法来制定这种计划:https://nrich.maths.org/1443

下面是Python算法的一个示例(适用于偶数和奇数人):

def roundRobin(people):
    count     = len(people)
    even      = 1-(count&1)
    poly      = people[even:]
    for _ in range(count-even):
        rooms  = [(people[0],poly[0])]*even
        rooms += [(poly[i],poly[count-i-even]) for i in range(1,(count+1)//2)]
        yield rooms
        poly = poly[1:]+poly[:1]

偶数人(6)

for session,meetings in enumerate(roundRobin(["A","B","C","D","E","F"]),1):
    print(session,meetings)
# 1 [('A', 'B'), ('C', 'F'), ('D', 'E')]
# 2 [('A', 'C'), ('D', 'B'), ('E', 'F')]
# 3 [('A', 'D'), ('E', 'C'), ('F', 'B')]
# 4 [('A', 'E'), ('F', 'D'), ('B', 'C')]
# 5 [('A', 'F'), ('B', 'E'), ('C', 'D')]

单数(7)

for session,meetings in enumerate(roundRobin(["A","B","C","D","E","F","G"]),1):
    print(session,meetings)
# 1 [('B', 'G'), ('C', 'F'), ('D', 'E')] ("A" sits out)
# 2 [('C', 'A'), ('D', 'G'), ('E', 'F')] ("B" sits out)
# 3 [('D', 'B'), ('E', 'A'), ('F', 'G')] ("C" sits out)
# 4 [('E', 'C'), ('F', 'B'), ('G', 'A')] ("D" sits out)
# 5 [('F', 'D'), ('G', 'C'), ('A', 'B')] ("E" sits out)
# 6 [('G', 'E'), ('A', 'D'), ('B', 'C')] ("F" sits out)
# 7 [('A', 'F'), ('B', 'E'), ('C', 'D')] ("G" sits out)

26人

for session,meetings in enumerate(roundRobin(list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")),1):
    print(session,", ".join(f"{a}-{b}" for a,b in meetings))
# 1 A-B, C-Z, D-Y, E-X, F-W, G-V, H-U, I-T, J-S, K-R, L-Q, M-P, N-O
# 2 A-C, D-B, E-Z, F-Y, G-X, H-W, I-V, J-U, K-T, L-S, M-R, N-Q, O-P
# 3 A-D, E-C, F-B, G-Z, H-Y, I-X, J-W, K-V, L-U, M-T, N-S, O-R, P-Q
# 4 A-E, F-D, G-C, H-B, I-Z, J-Y, K-X, L-W, M-V, N-U, O-T, P-S, Q-R
# 5 A-F, G-E, H-D, I-C, J-B, K-Z, L-Y, M-X, N-W, O-V, P-U, Q-T, R-S
# 6 A-G, H-F, I-E, J-D, K-C, L-B, M-Z, N-Y, O-X, P-W, Q-V, R-U, S-T
# 7 A-H, I-G, J-F, K-E, L-D, M-C, N-B, O-Z, P-Y, Q-X, R-W, S-V, T-U
# 8 A-I, J-H, K-G, L-F, M-E, N-D, O-C, P-B, Q-Z, R-Y, S-X, T-W, U-V
# 9 A-J, K-I, L-H, M-G, N-F, O-E, P-D, Q-C, R-B, S-Z, T-Y, U-X, V-W
# 10 A-K, L-J, M-I, N-H, O-G, P-F, Q-E, R-D, S-C, T-B, U-Z, V-Y, W-X
# 11 A-L, M-K, N-J, O-I, P-H, Q-G, R-F, S-E, T-D, U-C, V-B, W-Z, X-Y
# 12 A-M, N-L, O-K, P-J, Q-I, R-H, S-G, T-F, U-E, V-D, W-C, X-B, Y-Z
# 13 A-N, O-M, P-L, Q-K, R-J, S-I, T-H, U-G, V-F, W-E, X-D, Y-C, Z-B
# 14 A-O, P-N, Q-M, R-L, S-K, T-J, U-I, V-H, W-G, X-F, Y-E, Z-D, B-C
# 15 A-P, Q-O, R-N, S-M, T-L, U-K, V-J, W-I, X-H, Y-G, Z-F, B-E, C-D
# 16 A-Q, R-P, S-O, T-N, U-M, V-L, W-K, X-J, Y-I, Z-H, B-G, C-F, D-E
# 17 A-R, S-Q, T-P, U-O, V-N, W-M, X-L, Y-K, Z-J, B-I, C-H, D-G, E-F
# 18 A-S, T-R, U-Q, V-P, W-O, X-N, Y-M, Z-L, B-K, C-J, D-I, E-H, F-G
# 19 A-T, U-S, V-R, W-Q, X-P, Y-O, Z-N, B-M, C-L, D-K, E-J, F-I, G-H
# 20 A-U, V-T, W-S, X-R, Y-Q, Z-P, B-O, C-N, D-M, E-L, F-K, G-J, H-I
# 21 A-V, W-U, X-T, Y-S, Z-R, B-Q, C-P, D-O, E-N, F-M, G-L, H-K, I-J
# 22 A-W, X-V, Y-U, Z-T, B-S, C-R, D-Q, E-P, F-O, G-N, H-M, I-L, J-K
# 23 A-X, Y-W, Z-V, B-U, C-T, D-S, E-R, F-Q, G-P, H-O, I-N, J-M, K-L
# 24 A-Y, Z-X, B-W, C-V, D-U, E-T, F-S, G-R, H-Q, I-P, J-O, K-N, L-M
# 25 A-Z, B-Y, C-X, D-W, E-V, F-U, G-T, H-S, I-R, J-Q, K-P, L-O, M-N   

如果您只有10个会话,您可以过滤掉该函数的部分输出,并只获取所需的会话数:

schedule = [ r for r in roundRobin(list("ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
             if  not {"A","B"} in map(set,r)
             and not {"C","D"} in map(set,r)]

for session,meetings in enumerate(schedule[:10],1):
    print(session,", ".join(f"{a}-{b}" for a,b in meetings))

# 1 A-C, D-B, E-Z, F-Y, G-X, H-W, I-V, J-U, K-T, L-S, M-R, N-Q, O-P
# 2 A-D, E-C, F-B, G-Z, H-Y, I-X, J-W, K-V, L-U, M-T, N-S, O-R, P-Q
# 3 A-E, F-D, G-C, H-B, I-Z, J-Y, K-X, L-W, M-V, N-U, O-T, P-S, Q-R
# 4 A-F, G-E, H-D, I-C, J-B, K-Z, L-Y, M-X, N-W, O-V, P-U, Q-T, R-S
# 5 A-G, H-F, I-E, J-D, K-C, L-B, M-Z, N-Y, O-X, P-W, Q-V, R-U, S-T
# 6 A-H, I-G, J-F, K-E, L-D, M-C, N-B, O-Z, P-Y, Q-X, R-W, S-V, T-U
# 7 A-I, J-H, K-G, L-F, M-E, N-D, O-C, P-B, Q-Z, R-Y, S-X, T-W, U-V
# 8 A-J, K-I, L-H, M-G, N-F, O-E, P-D, Q-C, R-B, S-Z, T-Y, U-X, V-W
# 9 A-K, L-J, M-I, N-H, O-G, P-F, Q-E, R-D, S-C, T-B, U-Z, V-Y, W-X
# 10 A-L, M-K, N-J, O-I, P-H, Q-G, R-F, S-E, T-D, U-C, V-B, W-Z, X-Y

相关问题 更多 >