某运动会设立N个比赛项目,每个运动员可以参加1-3个项目。试问如何安排比赛日程,既可以使,既可以使同一运动员参加的项目不在同一单位时间进行,又使总的竞赛日程最短。(用数据结构的队列解决问题)
问题抽象:若将此问题抽象成数学模型,则归属于“划分子集”问题。N个比赛项目构成一个大小为n的集合,有同一运动员参加的项目则抽象为“冲突”关系。
解决问题:假设某运动会设有9个项目,A = {0, 1, 2, 3, 4, 5, 6, 7, 8},7名运动员报名参加的项目分别为:(1, 4, 8)、(1, 7)、(8, 3)、(1, 0, 5)、(3, 4)、(5, 6, 2)和(6, 4),则构成一个冲突关系的集合R = { (1, 4), (4, 8), (1, 8), (1, 7), (8, 3), (1, 0), (0, 5), (1, 5), (3, 4), (5, 6), (5, 2), (6, 2), (6, 4)}(一对括号中的两个项目不能安排在同一单位时间)。“划分子集”问题即将集合A划分成k个互不相交的子集A1, A2, ... , Ak(k <= n),使同一子集中的元素均无冲突关系。