NBA常规赛赛程安排建模和算法初探
发布时间:2019-11-03 01:27:50
发布时间:2019-11-03 01:27:50
NBA常规赛赛程安排建模和算法初探
一、 NBA赛制的问题描述
NBA(National Basketball Association)是美国国家职业篮球比赛。它是全世界篮球爱好者们最钟爱的一项赛事,姚明、易建联加盟NBA以后,中国球迷更加热爱这项运动,我就是火箭队的忠实球迷。
NBA目前共有30支球队,分为两个联盟,即东部联盟和西部联盟。每个联盟各有三个赛区,共六个赛区。每个赛区有五支球队,即5支球队 Х 6个赛区 = 30支球队。
NBA比赛分为常规赛、季后赛和总决赛。每个球队在常规赛里都要参加82场比赛,一般是从每年的10月底到第二年的4月中旬,历时165天。常规赛结束后,两个联盟分别选出排在前八名的8支球队参加季后赛。在季后赛里,东部赛区的冠军和西部赛区的冠军进行总决赛,最后决出NBA冠军。
如何安排NBA比赛的赛程,使对各支球队都尽量公平呢。一方面,要使得各支球队能够在一定的比赛周期内,每两场比赛中间间隔的休整时间比较均等;另一方面,赛程安排中尽量不要出现在某些天比赛场次过多的情况,以防运动员因为消耗体力太大,影响比赛结果。
我一直对NBA比赛非常感兴趣,因为这些比赛非常好看。所以我对NBA的赛制规则非常了解,也一直在猜测NBA联盟委员会是以什么原则安排比赛赛程的。这篇论文总结了我在NBA赛程安排方面做的一些探讨研究。本论文只描述常规赛的赛制和赛程安排。
在常规赛里,NBA的30支球队,每只球队要参加82场比赛,因为每场比赛有两支球队对抗,所以共有(82 Х 30)÷ 2 = 1230场比赛。
每支球队都要与其余的29支球队进行82场比赛,具体规则是这样的:
1、 每支球队要与同一个赛区的另外4支球队各比赛4场,两场主场,两场客场。所以与同一个赛区的球队共有4 Х 4 = 16场比赛。
2、 每支球队要与不同联盟的另外15支球队各比赛2场,一场主场,一场客场。所以与不同联盟的球队共有 2 Х 15 = 30场比赛。
3、 每支球队要与同一联盟不同赛区的另外10支球队中的6支各比赛4场,两场主场,两场客场;10支球队中的4支各比赛3场,两场主场,一场客场,或一场主场,两场客场。所以与同一联盟不同赛区的球队共有 (4 Х 6)+(3 Х 4) = 36场比赛。
对于要与同一联盟不同赛区的另外10支球队中的4支各比赛3场的情况,比赛规则是:设同一联盟的三个赛区分别为P,Q,R,P赛区的第1支球队与
1) Q赛区的第2支球队和第4支球队进行3场比赛
2) R赛区的第3支球队和第5支球队进行3场比赛
二、 NBA赛程安排的问题与假设
为了让赛程安排尽可能公平,在建立NBA赛程安排的模型和算法时,希望能满足以下条件:
1. 每支球队不能一天比赛两场
2. 每支球队的两场比赛之间尽可能地间隔一天
3. 赛程安排尽可能对每支球队公平,即各球队比赛平均间隔的天数尽可能接近
NBA赛程安排的假设:
1. 由于每一支球队都有自己的球场,所以安排比赛不需要考虑球场问题。即30支球队可以在同一天比赛,也可以说一天最多可以安排15场比赛。
2. 因为不考虑球场,所以主场和客场比赛是对等的,在赛程安排中也不需要考虑主客场问题。
另外,因为每支球队要在165天里比赛82场,所以平均每两天至少要比赛一场。
三、 建立模型和算法的准备
根据NBA赛制的描述,30支球队分别表示为:
设东、西两个联盟分别表示为E(Eastern)和W(Western);
东部赛区E的三个赛区分别表示为:Ea,Eb,Ec。
西部赛区W的三个赛区分别表示为:Wa,Wb,Wc。
东部赛区E的三个赛区的15支球队分别表示为:
Ea1,Ea2,Ea3,Ea4,Ea5
Eb1,Eb2,Eb3,Eb4,Eb5
Ec1,Ec2,Ec3,Ec4,Ec5
西部赛区W的三个赛区的15支球队分别表示为:
Wa1,Wa2,Wa3,Wa4,Wa5
Wb1,Wb2,Wb3,Wb4,Wb5
Wc1,Wc2,Wc3,Wc4,Wc5
赛制规则1定义为规则A,即每支球队与同赛区的球队进行16场比赛。
赛制规则2定义为规则B,即每支球队与不同联盟的球队进行30场比赛。
赛制规则3定义为规则C,即每支球队与同联盟不同赛区的球队进行36场比赛。
第i支球队用Ti(Team)表示,用于表示赛程安排的比赛次序。
两支球队比赛的场数用(数字)表示。
例如:规则A,T1支球队与Ea赛区的其余4支球队各比赛(4)场;
规则B,T1与Wa、Wb、Wc赛区的15支球队各比赛(2)场;
规则C,T1与Eb、Ec赛区的10支球队各比赛(3)场或(4)场。
赛程安排的比赛时间用数字表示,即date = i,其中i=1,2,…,165。表示比赛安排在第i天。
四、 建立NBA赛程安排的模型和算法
在建立NBA赛程安排模型中,设计了以下三个原则:
原则一、在确定球队和球队之间的比赛次序时,原则是联盟之间互相交叉,同时赛区之间互相交叉,因为这样球队与球队之间比赛的次序比较均等。
图1是基于这个原则的一种安排次序,Ti就是第i次安排的球队。
东部赛区:
Ea Eb Ec
Ea1 T1 | Eb1 T3 | Ec1 T5 | ||
Ea2 T7 | Eb2 T9 | Ec2 T11 | ||
Ea3 T13 | Eb3 T15 | Ec3 T17 | ||
Ea4 T19 | Eb4 T21 | Ec4 T23 | ||
Ea5 T25 | Eb5 T27 | Ec5 T29 | ||
--------------------------------------------------------------------------------------------------------------------------
西部赛区:
Wa Wb Wc
Wa1 T2 | Wb1 T4 | Wc1 T6 | ||
Wa2 T8 | Wb2 T10 | Wc2 T12 | ||
Wa3 T14 | Wb3 T16 | Wc3 T18 | ||
Wa4 T20 | Wb4 T22 | Wc4 T24 | ||
Wa5 T26 | Wb5 T28 | Wc5 T30 | ||
图1. 球队之间的比赛次序
因此,第1次安排的球队T1(Ea1)与其余29支球队比赛;第2次安排的球队T2(Wa1)与其余28支球队比赛;第3次安排的球队T3(Eb1)与其余27支球队比赛;…;第i次安排的球队Ti(…)与其余30 – i支球队比赛;…;第29次安排的球队T29(Ec5)与剩下1支球队比赛;第30次安排的球队T30(Wc5)与0支球队比赛。所以,按照T1、T2、…、T30的比赛的次序,共需要安排435个球队和球队之间的比赛(∑i,i=1,2,…,29)。
在这种比赛次序下,每两支球队比赛的场数由规则A、规则B、规则C决定。
原则二、在原则一给出的比赛次序中,按照交叉的原则安排比赛时间。即Ti次序的球队,要同(30 – i)支球队比赛。当i为奇数时,时间安排从前到后;当i为偶数时,时间安排从后到前。这样可以使得一支球队一天比赛两场的可能性比较小,并且一支球队两场比赛间隔一天的可能性比较大。图2是在一种比赛次序下的比赛时间的安排。
图表中的数字为比赛时间date,即第i天(i=1,2,...,165)比赛。
T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 | T10 | …… | T25 | T26 | T27 | T28 | T29 | T30 | |
T1 | X | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 47 | 49 | 51 | 53 | 55 | 57 | |
T2 | 0 | X | 56 | 54 | 52 | 50 | 48 | 46 | 44 | 42 | 12 | 10 | 8 | 6 | 4 | 2 | |
T3 | 0 | 0 | X | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 53 | 55 | 57 | 59 | 61 | 63 | |
: : | |||||||||||||||||
T29 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | X | 85 | |
T30 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | X | |
图2. 比赛时间安排
因为不考虑主客场,T1对T2的比赛就是T2对T1的比赛,这里都设为0。
原则三、两支球队之间有多场比赛,有的球队之间需要比赛4场(按照规则A或规则C),有的需要比赛2场(按照规则B),有的需要比赛3场(按照规则C)。不同场之间的时间安排原则是:
比赛4场的,时间安排间隔为40天;
比赛2场的,时间安排间隔为80天;
比赛3场的,时间安排间隔为50天;
这样可以使相同球队的几场比赛间隔天数尽可能大,比赛会比较好看。因为比赛周期是165天,所以按照150或160的2、3、4倍数关系选择上面的间隔天数。
NBA赛程安排算法:
第一步:先按照原则一,以联盟和赛区为单位,设定出球队和球队比赛安排的次序Ti;
第二步:再按照原则二,在第一步设置的比赛次序中安排比赛时间date。
第三步:再按照原则三,对两支球队的多场比赛,安排比赛时间date。
第四步:对以上安排的比赛时间date进行判断:
If(要比赛的两支球队中的任何一支球队在同一天已经有比赛了)
Then { 这场比赛就向后顺移时间,即:date <= 日期+1
If(date > 165天) then date <= 1 }
五、 模型和算法的分析
上面给出的算法的第四步判断一定能满足赛程安排的第一个条件,即每支球队不可能一天比赛两场。理论上,一定有至少一种赛程安排。因为没有场地的限制,一天最多可以比赛15场,所以,很多球队如果没有间隔地每天连续比赛,就可以安排。但这种安排不太好。
我给出的原则和算法就是希望尽可能满足赛程安排的第二个条件,即每支球队的两场比赛之间尽可能地间隔一天。在算法的第二步就是先按照隔一天一场比赛的情况安排,算法的第三步是按照同一球队的场与场之间尽可能间隔的远的情况安排的。如果判断出安排的比赛有冲突,就按照连续每天比赛的情况安排。
赛程安排的第三个条件没有考虑,即赛程安排尽可能对每支球队公平,各球队比赛平均间隔的天数尽可能接近。待以后进一步完善。
另外,NBA比赛的排名也有很多规则,要考虑很多因素。我希望能在以后补充这部分模型和算法。
我们国家也有CBA篮球比赛,目前共有18个球队,但我们的赛区分配没有NBA那么复杂,可以简化这个模型,建立CBA赛程安排。
六、 参考文献
【1】 韩中庚.数学建模竞赛—获奖论文精选与点评.北京:科学出版社,2007.
【2】 姜启源等.《数学模型(第三版)》习题参考解答.北京:高等教育出版社,2003.
【3】 NBA英文网. http://www.nba.com/schedule.
【4】 全国大学生数模竞赛网. http://mcm.edu.cn/.
附1. 美国30支球队名单
东部联盟:
东南区 中区 大西洋区
迈阿密热队 底特律活塞队 波士顿凯尔特人队
奥兰多魔术队 印第安纳步行者队 费城76人队
亚特兰大老鹰队 克里夫兰骑士队 纽约尼克斯队
华盛顿奇才队 芝加哥公牛队 新泽西网队
夏洛特山猫队 密尔沃基雄鹿队 多伦多猛龙队
-------------------------------------------------------------------------------------------------------
西部联盟:
西南区 西北区 太平洋区
圣安东尼奥马刺队 明尼苏达森林狼队 萨克拉门托国王队
孟菲斯灰熊队 丹佛掘金队 菲尼克斯太阳队
达拉斯小牛队 尤他爵士队 洛杉矶湖人队
休斯顿火箭队 波特兰开拓者队 洛杉矶快船队
新奥尔良黄蜂队 俄克拉荷马雷霆队 金州勇士队
附2. 2009-2010赛季,2009年11月赛程安排
01日 类型 客队 比分 主队
07:00 常规赛 篮网 VS 奇才
07:30 常规赛 山猫 VS 骑士
07:30 常规赛 76人 VS 尼克斯
08:30 常规赛 开拓者 VS 火箭
08:30 常规赛 活塞 VS 雄鹿
08:30 常规赛 国王 VS 马刺
10:30 常规赛 小牛 VS 快船
02日 类型 客队 比分 主队
02:00 常规赛 魔术 VS 猛龙
07:00 常规赛 黄蜂 VS 凯尔特人
07:00 常规赛 公牛 VS 热火
08:00 常规赛 开拓者 VS 雷霆
09:00 常规赛 灰熊 VS 掘金
09:00 常规赛 森林狼 VS 太阳
10:30 常规赛 老鹰 VS 湖人
03日 类型 客队 比分 主队
08:00 常规赛 篮网 VS 山猫
08:30 常规赛 黄蜂 VS 尼克斯
10:00 常规赛 火箭 VS 爵士
11:00 常规赛 灰熊 VS 国王
11:30 常规赛 森林狼 VS 快船
04日 类型 客队 比分 主队
08:00 常规赛 凯尔特人 VS 76人
08:00 常规赛 掘金 VS 步行者
08:00 常规赛 奇才 VS 骑士
08:30 常规赛 魔术 VS 活塞
08:30 常规赛 太阳 VS 热火
09:00 常规赛 雄鹿 VS 公牛
09:00 常规赛 湖人 VS 雷霆
09:30 常规赛 爵士 VS 小牛
11:00 常规赛 老鹰 VS 开拓者
05日 类型 客队 比分 主队
08:00 常规赛 太阳 VS 魔术
08:00 常规赛 热火 VS 奇才
08:00 常规赛 活塞 VS 猛龙
08:30 常规赛 掘金 VS 篮网
08:30 常规赛 步行者 VS 尼克斯
09:00 常规赛 凯尔特人 VS 森林狼
09:30 常规赛 快船 VS 火箭
10:30 常规赛 小牛 VS 黄蜂
11:00 常规赛 老鹰 VS 国王
11:30 常规赛 灰熊 VS 勇士
06日 类型 客队 比分 主队
09:00 常规赛 公牛 VS 骑士
11:30 常规赛 马刺 VS 爵士
07日 类型 客队 比分 主队
08:00 常规赛 老鹰 VS 山猫
08:00 常规赛 篮网 VS 76人
08:00 常规赛 活塞 VS 魔术
08:00 常规赛 奇才 VS 步行者
08:30 常规赛 太阳 VS 凯尔特人
08:30 常规赛 掘金 VS 热火
09:00 常规赛 骑士 VS 尼克斯
09:00 常规赛 雄鹿 VS 森林狼
09:00 常规赛 猛龙 VS 黄蜂
09:30 常规赛 雷霆 VS 火箭
11:30 常规赛 快船 VS 勇士
11:30 常规赛 灰熊 VS 湖人
11:30 常规赛 马刺 VS 开拓者
08日 类型 客队 比分 主队
08:00 常规赛 掘金 VS 老鹰
08:30 常规赛 凯尔特人 VS 篮网
09:00 常规赛 山猫 VS 公牛
09:30 常规赛 猛龙 VS 小牛
09:30 常规赛 尼克斯 VS 雄鹿
10:00 常规赛 国王 VS 爵士
11:30 常规赛 灰熊 VS 快船
09日 类型 客队 比分 主队
02:00 常规赛 太阳 VS 奇才
02:00 常规赛 76人 VS 活塞
08:00 常规赛 魔术 VS 雷霆
10:00 常规赛 森林狼 VS 开拓者
10:30 常规赛 黄蜂 VS 湖人
11:00 常规赛 勇士 VS 国王
10日 类型 客队 比分 主队
08:00 常规赛 太阳 VS 76人
08:30 常规赛 爵士 VS 尼克斯
10:30 常规赛 猛龙 VS 马刺
11:30 常规赛 森林狼 VS 勇士
11:30 常规赛 黄蜂 VS 快船
11日 类型 客队 比分 主队
08:00 常规赛 魔术 VS 山猫
08:30 常规赛 奇才 VS 热火
09:00 常规赛 掘金 VS 公牛
09:00 常规赛 开拓者 VS 灰熊
09:30 常规赛 火箭 VS 小牛
11:00 常规赛 雷霆 VS 国王
12日 类型 客队 比分 主队
08:00 常规赛 勇士 VS 步行者
08:00 常规赛 公牛 VS 猛龙
08:30 常规赛 老鹰 VS 尼克斯
08:30 常规赛 76人 VS 篮网
08:30 常规赛 山猫 VS 活塞
08:30 常规赛 爵士 VS 凯尔特人
09:00 常规赛 掘金 VS 雄鹿
09:00 常规赛 开拓者 VS 森林狼
09:00 常规赛 骑士 VS 魔术
09:30 常规赛 小牛 VS 马刺
09:30 常规赛 灰熊 VS 火箭
11:30 常规赛 雷霆 VS 快船
11:30 常规赛 黄蜂 VS 太阳
13日 类型 客队 比分 主队
09:00 常规赛 骑士 VS 热火
11:30 常规赛 太阳 VS 湖人
14日 类型 客队 比分 主队
08:00 常规赛 篮网 VS 魔术
08:00 常规赛 爵士 VS 76人
08:30 常规赛 勇士 VS 尼克斯
09:00 常规赛 老鹰 VS 凯尔特人
09:00 常规赛 开拓者 VS 黄蜂
09:00 常规赛 小牛 VS 森林狼
11:00 常规赛 火箭 VS 国王
11:30 常规赛 湖人 VS 掘金
11:30 常规赛 猛龙 VS 快船
15日 类型 客队 比分 主队
08:00 常规赛 开拓者 VS 山猫
08:00 常规赛 活塞 VS 奇才
08:00 常规赛 凯尔特人 VS 步行者
08:00 常规赛 黄蜂 VS 老鹰
08:30 常规赛 爵士 VS 骑士
08:30 常规赛 篮网 VS 热火
09:00 常规赛 森林狼 VS 灰熊
09:00 常规赛 76人 VS 公牛
09:30 常规赛 勇士 VS 雄鹿
09:30 常规赛 雷霆 VS 马刺
16日 类型 客队 比分 主队
07:00 常规赛 小牛 VS 活塞
08:00 常规赛 快船 VS 雷霆
09:00 常规赛 猛龙 VS 太阳
10:30 常规赛 火箭 VS 湖人
17日 类型 客队 比分 主队
08:00 常规赛 开拓者 VS 老鹰
08:00 常规赛 山猫 VS 魔术
09:00 常规赛 小牛 VS 雄鹿
18日 类型 客队 比分 主队
08:00 常规赛 勇士 VS 骑士
08:30 常规赛 雷霆 VS 热火
08:30 常规赛 步行者 VS 篮网
09:00 常规赛 快船 VS 黄蜂
09:30 常规赛 太阳 VS 火箭
10:00 常规赛 猛龙 VS 掘金
11:00 常规赛 公牛 VS 国王
11:30 常规赛 活塞 VS 湖人
19日 类型 客队 比分 主队
08:00 常规赛 骑士 VS 奇才
08:00 常规赛 山猫 VS 76人
08:00 常规赛 雷霆 VS 魔术
08:00 常规赛 尼克斯 VS 步行者
08:00 常规赛 热火 VS 老鹰
08:30 常规赛 勇士 VS 凯尔特人
09:00 常规赛 篮网 VS 雄鹿
09:00 常规赛 火箭 VS 森林狼
09:00 常规赛 快船 VS 灰熊
10:00 常规赛 猛龙 VS 爵士
10:30 常规赛 马刺 VS 小牛
11:00 常规赛 活塞 VS 开拓者
20日 类型 客队 比分 主队
09:00 常规赛 太阳 VS 黄蜂
09:30 常规赛 爵士 VS 马刺
11:30 常规赛 公牛 VS 湖人
21日 类型 客队 比分 主队
08:00 常规赛 热火 VS 猛龙
08:00 常规赛 灰熊 VS 76人
08:00 常规赛 骑士 VS 步行者
08:30 常规赛 火箭 VS 老鹰
09:00 常规赛 魔术 VS 凯尔特人
09:00 常规赛 奇才 VS 雷霆
09:30 常规赛 国王 VS 小牛
09:30 常规赛 山猫 VS 雄鹿
11:30 常规赛 掘金 VS 快船
11:30 常规赛 开拓者 VS 勇士
22日 类型 客队 比分 主队
02:00 常规赛 尼克斯 VS 篮网
08:30 常规赛 76人 VS 骑士
09:00 常规赛 老鹰 VS 黄蜂
09:00 常规赛 雄鹿 VS 灰熊
09:30 常规赛 奇才 VS 马刺
09:30 常规赛 国王 VS 火箭
10:00 常规赛 公牛 VS 掘金
10:00 常规赛 活塞 VS 爵士
11:00 常规赛 森林狼 VS 开拓者
23日 类型 客队 比分 主队
01:30 常规赛 魔术 VS 猛龙
02:00 常规赛 凯尔特人 VS 尼克斯
06:00 常规赛 步行者 VS 山猫
07:00 常规赛 黄蜂 VS 热火
09:00 常规赛 活塞 VS 太阳
10:30 常规赛 雷霆 VS 湖人
24日 类型 客队 比分 主队
09:00 常规赛 国王 VS 灰熊
09:30 常规赛 雄鹿 VS 马刺
11:00 常规赛 公牛 VS 开拓者
11:30 常规赛 森林狼 VS 快船
25日 类型 客队 比分 主队
08:00 常规赛 步行者 VS 猛龙
08:00 常规赛 76人 VS 奇才
09:30 常规赛 勇士 VS 小牛
10:00 常规赛 篮网 VS 掘金
10:00 常规赛 雷霆 VS 爵士
11:30 常规赛 尼克斯 VS 湖人
26日 类型 客队 比分 主队
08:00 常规赛 猛龙 VS 山猫
08:00 常规赛 快船 VS 步行者
08:30 常规赛 76人 VS 凯尔特人
08:30 常规赛 热火 VS 魔术
09:00 常规赛 雄鹿 VS 黄蜂
09:00 常规赛 骑士 VS 活塞
09:00 常规赛 掘金 VS 森林狼
09:30 常规赛 勇士 VS 马刺
09:30 常规赛 小牛 VS 火箭
10:00 常规赛 灰熊 VS 太阳
11:00 常规赛 篮网 VS 开拓者
11:00 常规赛 尼克斯 VS 国王
27日 类型 客队 比分 主队
09:00 常规赛 魔术 VS 老鹰
11:30 常规赛 公牛 VS 爵士
28日 类型 客队 比分 主队
08:00 常规赛 骑士 VS 山猫
08:00 常规赛 老鹰 VS 76人
08:00 常规赛 奇才 VS 热火
08:30 常规赛 猛龙 VS 凯尔特人
09:00 常规赛 快船 VS 活塞
09:00 常规赛 小牛 VS 步行者
09:00 常规赛 雄鹿 VS 雷霆
09:30 常规赛 马刺 VS 火箭
10:00 常规赛 尼克斯 VS 掘金
10:30 常规赛 太阳 VS 森林狼
11:00 常规赛 灰熊 VS 开拓者
11:00 常规赛 篮网 VS 国王
29日 类型 客队 比分 主队
08:30 常规赛 小牛 VS 骑士
09:30 常规赛 山猫 VS 奇才
10:00 常规赛 开拓者 VS 爵士
10:00 常规赛 魔术 VS 雄鹿
11:30 常规赛 湖人 VS 勇士
30日 类型 客队 比分 主队
02:00 常规赛 老鹰 VS 活塞
04:30 常规赛 灰熊 VS 快船
04:30 常规赛 太阳 VS 猛龙
07:00 常规赛 魔术 VS 尼克斯
07:00 常规赛 凯尔特人 VS 热火
08:00 常规赛 76人 VS 马刺
08:00 常规赛 火箭 VS 雷霆
09:00 常规赛 森林狼 VS 掘金
10:30 常规赛 篮网 VS 湖人
11:00 常规赛 黄蜂 VS 国王