《队列的应用_运动会》由会员分享，可在线阅读，更多相关《队列的应用_运动会（4页珍藏版）》请在金锄头文库上搜索。
1、四、队列的应用实例四、队列的应用实例划分子集问题划分子集问题在安排运动会比赛日程时，需要考虑如何安排比赛项目，才能使同一运动员参加的不 同项目不在同一时间内进行，同时又使比赛总的日程最短，即同时可进行的比赛项目尽可 能的多。这个问题就是，将可在同一时间内比赛的哪几个项目分在一个时间内，也就是作 为一个子集，且子集内的元素尽可能的多，为解决这一类问题可以运用队列结构实现。一般而言，已知集合 A=a1,a2,an，ai表示项目编号，并已知此集合上的关系 R=（ai,aj），ai，aj属于 A 集合(ij)，其中(ai，aj)表示 ai与 aj之间是否存在冲突关系。现 要求划分成不相交的子集 Al，
2、A2，Ak(kn)，使任何子集上的元素均无冲突关系，同时 要求划分子集的个数尽可能少。下面，如运动会共设 9 个比赛项目，规定每个运动员最多可以参加三个项目，则A=1，2，3，4，5，6，7，8，9R=(2，8)，(4，9)，(2，9)，(2，1)，(2，5)，(2，6)，(5，9)，(5，6)，(4，5)，(5，7)， (6，7)，(3，7)，(3，6)表示冲突的项目。则最终可得出的可行子集划分为：Al=1，3，4，8 A2=2，7 A3=5 A4=6，9下面处理中用的数组是从下标 1 开始的，注意与前面数组处理时以 0 开始是不同 的。计算机实现时，设置一个冲突关系矩阵，由一个二维数组 R
3、1：n，1：n表示，若第 i 与第 j 元素有冲突，则 Rij=1。否则 Rij=0。对应于上述例子的关系矩阵如图 3-18。 12 3 4 5 6 7 8 9 1 0 1 0 0 0 0 0 0 0 2 1 0 0 0 1 1 0 1 1 3 0 0 0 0 0 1 1 0 0 40 0 0 0 1 0 0 0 1 50 1 0 1 0 1 1 0 1 60 1 1 0 1 0 1 0 0 70 0 1 0 1 1 0 0 0 80 1 0 0 0 0 0 0 0 90 1 0 1 1 0 0 0 0图 3-18 集合元素的关系矩阵 Rnn 另设置一个循环队列 Q11：n)，存放集合 A 的
4、元素，即项目编号；数组 S1：n用于存放每 个元素所属的子集编号，即 Si中的值为对应的 i 项目的子集编号，如第 3 个项目为 A1 子 集的元素，则 S3=1，第 5 个项目为 A3 子集的元素，则 S5=3，S 数组的最终结果应为：123456789S 121134214为实现这一过程，还要设置一个工作数组 TEMP1：n，其 TEMPi值是第 i 个项目是否与当前子集中的其它项目相冲突的标志。如冲突，则 TEMPi非零，否则为 0。TEMP 的 形成过程是用刚刚进入当前子集的项目编号 i 作为行号，并将 Rik(k=i+1：n)的值累加进 入 TEMPK中去，也就是与进入当前子集的项目
5、编号 i 相冲突的项目在 TEMP 数组设置为 非零。这一过程一直进行到形成一个子集。当然，每形成一个新子集时，第一出队的元素 可直接进入子集，不必用 TEMP 的状态来判断是否有冲突，而以后能否进入当前了集需一 边形成 TEMP 状态，一边根据 TEMP 状态判断决定能否进入当前子集，即 TEMPj为非零 时，则项目编号为 j 的元素不能进入当前子集中。TEMP 数组形成中，S 数组元素对应于 TEMP 数组元素值为 0 的位置，就以该子集编号填人。例如，第一个 TEMP 数组形成后的 状态，以此状态值填人 S 数组后的 S 数组状态，如图 3-19。123456789Tem p 01001
6、1101123456789S 1111以上给出的是 S 数组及 TEPM 数组形成后的状态，它们的形成过程要依赖于队列数组 Q。而队列数组的变化过程是：首先，Q 队列数组的初态为项目编号；然后，每次形成一 个子集时，要将队列中的所有元素出队一次，凡是属于当前子集的项目编号不再进队，不 属于当前子集的就再次进队，作为下一子集形成前队列的初始状态，每次将当前初始队列 中的所有元素全部出队完，就形成了一个子集，即出队后没再进队的项目。如此进行下去， 直到队列中无元素可再出队为止。出队时，初态队列中第一个出队的元素不需要判断，直 接作为所形成子集的第一元素，即第一出队元素直接形成 S 数组对应位置的值；而以后出 队的元素是否属于该子集，就要根据形成的 TEMP 状态值来决定。其过程的算法思想是：采用循环筛选的方法，先将第一个元素进入子集，凡与已进入该子集的元素无冲突的 元素划归一子集，再将余下的元素重新找出互不冲突的划归第二子集，以此类推，直到所 有的元素都划归进入某一子集。 下面给出 Q 队列数组及 S 结果数组每次形成一个子集的状态，如图 3-20。
