Python解决数学建模问题：赛程安排

五支足球队在同一场地上进行足球赛。进行单循环比赛&＃xff0c;也就是说这五支球队的每两支球队在这次比赛中都要结对比赛一次。共进行十场比赛&＃xff0c;在连续的十天中每天比赛一场。问&＃xff1a;如何安排这次比赛的赛程对各队来说都是公平的&＃xff1f;

公平定义&＃xff1a;

各队在其相邻比赛的最小的间隔场次达到最大的可能。

数学问题&＃xff1a;

在所有赛程最小间隔场次中求最大。

考虑&＃xff1a;

n 支球队的单循环赛的一个赛程。记最小的间隔场次为 r 。
于是&＃xff0c;在这 r 场比赛前后的 2 场比赛中出现的 3 个队不参
与这 r 场比赛&＃xff0c;而且有 2r 个不同的球队参加这 r 场比赛&＃xff0c;
所以 2r ≤ n - 3 。
最大的可能就是 r &＃61; [ ( n - 3 ) / 2 ] 。

思路&＃xff1a;

首先明确下面提及的概念&＃xff0c;队组&＃xff1a;即两个队伍搭配成一组&＃xff0c;如[1&＃xff0c;2]即1、2这两队组成一组。

一、定义节点和链表&＃xff0c;及链表对应的初始化、获得头节点、遍历、加入元素、删除元素这些方法&＃xff0c;对于每一个方法的详细介绍将在代码中体现。

class SingleNode(object):def __init__(self, item):# item存放数据元素&＃xff0c;后面将会用来存放比赛的队组self.item &＃61; item# next是下一个节点的标识self.next &＃61; Noneclass SingleLinkList(object):# 初始化链表def __init__(self):self.__head &＃61; Nonedef is_empty(self):return self.__head &＃61;&＃61; None# 获得该链表的头节点def get_first(self):return self.__head# 遍历链表&＃xff0c;即按顺序打印出链表节点的内容def travel(self):cur &＃61; self.__headi&＃61;1while cur !&＃61; None:print("第{}场&＃xff1a;{}".format(i,cur.item))i&＃43;&＃61;1cur &＃61; cur.next# 向链表中增加节点&＃xff0c;这里采用的是在链表的尾部加入&＃xff0c;采用这种加入方式是和我们后面具体的算法有关def append(self, item):node &＃61; SingleNode(item)if self.is_empty():self.__head &＃61; nodeelse:cur &＃61; self.__headwhile cur.next !&＃61; None:cur &＃61; cur.nextcur.next &＃61; node# 删掉节点&＃xff0c;根据item的内容进行删除&＃xff0c;因为我们后面比赛中的队组并不会重复&＃xff0c;所以这里不考虑item在链表中有多个对应节点的情况def remove(self, item):cur &＃61; self.__headpre &＃61; Nonewhile cur !&＃61; None:if cur.item &＃61;&＃61; item:if not pre:self.__head &＃61; cur.nextelse:pre.next &＃61; cur.nextbreakelse:pre &＃61; curcur &＃61; cur.next


二、具体代码实现。这里的代码实现的结果是打印出一种公平的赛程安排。因为不考虑A,B,C,D,E这5队的顺序&＃xff0c;故不妨设这5支队伍为0&＃xff0c;1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;且集合{A&＃xff0c;B&＃xff0c;C&＃xff0c;D&＃xff0c;E}与集合{0&＃xff0c;1&＃xff0c;2&＃xff0c;3&＃xff0c;4}相等&＃xff08;用集合相等来表达的原因就是在于顺序可以随意交换&＃xff09;。

假定初始赛程顺序即为随机&＃xff0c;那么已经求出各队相邻比赛场次的最小间隔为 r &＃xff0c;那么满足这一条件的赛程必然满足对于任意场次[i&＃xff0c;j]其后的 r 场的参赛队伍内均无 i 和 j 这两队&＃xff0c;后面这一情况当然是一个充分条件。

那么为了满足其必要性&＃xff0c;我们从第一场依次进行检查&＃xff0c;若第一场[0, 1]的后r场内存在 0 或 1 这两支队伍参加比赛&＃xff0c;那么就将其参加比赛的队组调整到最后一场&＃xff0c;以保证第一场后的 r 场均满足其后的 r 场比赛内 0 和 1 均为参赛&＃xff0c;那么再对第二场的后 r 场进行同样检查。注意这里的第二场是经过调整后的顺序里的第二场。

以此类推检查&＃xff0c;即可满足对于任意场次[i&＃xff0c;j]其后的 r 场的参赛队伍内均无 i 和 j 这两队&＃xff0c;同时也由此可以推出对于任意场次[i&＃xff0c;j]其前的 r 场的参赛队伍内均无 i 和 j 这两队&＃xff0c;那么这样的赛程即为公平的。

当然&＃xff0c;这里的初始赛程可以随意给出&＃xff0c;最后的赛程结果也会相应的变化&＃xff0c;另外&＃xff0c;这里的0,1,2,3,4并未指明是哪一支队伍&＃xff0c;故也可以随意替换&＃xff0c;但无论如何&＃xff0c;最终打印出来的结果均满足“公平”这一关键条件。

这里可以调节队伍数量 n 的值即可计算出结果&＃xff0c;这里将 n 取为66&＃xff0c;可得到66支队伍的公平赛程安排&＃xff0c;且由于初始安排的随机性&＃xff0c;每一次运行可以得到不同且公平的赛程安排。

from itertools import permutations
import numpy as np
# n表示队伍数量
n &＃61; 66
# N表示比赛场数
N &＃61; n*(n-1)//2
# 确定最小间隔r
r &＃61; (n-3)//2
# code用来存放比赛的二队组
code &＃61; []# 将队组存入code
for i in range(n):for j in range(i&＃43;1, n):code.append([i, j])
# 打乱code的顺序&＃xff0c;一方面是验证代码的正确性&＃xff0c;另一方面也是通过随机顺序尽量减少代码循环执行的次数
np.random.shuffle(code)
# 将code以节点的形式加入到链表llist中
llist &＃61; SingleLinkList()
for i in range(N):llist.append(code[i])
# chosen表示当前被检查的队组
# choosing表示当前正在和chosen对应的队组进行比较的后r场中的队组
chosen &＃61; llist.get_first()
choosing &＃61; SingleNode(1)
num &＃61; N-r
for j in range(num):k &＃61; 0choosing &＃61; chosen.next# 下面这一个while进行的是对chosen的后r场进行检查的循环while k < r and not choosing:choosing &＃61; choosing.nextk &＃43;&＃61; 1# 下面这一个while是对choosing及其后不满足条件的队组进行调整的过程while choosing.item[0] in chosen.item or choosing.item[1] in chosen.item:change &＃61; choosing.itemchoosing &＃61; choosing.nextllist.remove(change)llist.append(change)if choosing &＃61;&＃61; None:breakchosen &＃61; chosen.next
# 打印结果
print("最小间隔为&＃xff1a;{}".format(r))
print(" ")
print("赛程安排如下&＃xff1a;")
print(" ")
llist.travel()


附一张我运行的结果图&＃xff1a;

用这种想法解决问题的起源&＃xff1a;

我上课的时候学习的是另一种方法&＃xff0c;好处是可以将所有的“公平的”赛程安排算出来&＃xff0c;但是它的局限性是运行的时间太长&＃xff0c;且因为考虑了五支队伍的差别&＃xff0c;重复计算了多种赛程&＃xff0c;比如他既考虑了&＃xff08;A,B,C,D,E&＃xff09;对应的所有公平赛程安排&＃xff0c;也考虑了&＃xff08;B,A,C,D,E&＃xff09;的所有公平赛程安排&＃xff0c;其实会发现这两种安排中会存在许多相同的公平赛程安排。

所以我就尝试用别的方法来减少运行时间&＃xff0c;最后得到的就是上面这种方法。大家也可以看到这种方法结果上面的问题的好处是可以较快地运行出结果&＃xff0c;这种方法先通过设置初始赛程顺序解决队伍差别问题&＃xff0c;运用数据结构的知识来进行调整顺序得到结果。

但是这种方法局限性在于因最后的运行结果与初始赛程顺序&＃xff08;随机产生&＃xff09;和调整方法相关&＃xff0c;只要调整成功便不再继续调整&＃xff0c;所以运行结果唯一&＃xff0c;没有办法呈现出所以的赛程安排&＃xff08;想想其实可能再调整会有其他结果或者把调整方法改一下也会出现其他结果&＃xff0c;但是这样我就兼顾不到我的速度了&＃xff09;。

如果大家有可以兼顾速度和结果数量的思路&＃xff0c;欢迎一起讨论&＃xff01;