• / 4
  • 下载费用:10 金币  

队列的应用_运动会.doc

关 键 词:
队列的应用_运动会.doc
资源描述:
四、队列的应用实例划分子集问题在安排运动会比赛日程时,需要考虑如何安排比赛项目,才能使同一运动员参加的不同项目不在同一时间内进行,同时又使比赛总的日程最短,即同时可进行的比赛项目尽可能的多。这个问题就是,将可在同一时间内比赛的哪几个项目分在一个时间内,也就是作为一个子集,且子集内的元素尽可能的多,为解决这一类问题可以运用队列结构实现。一般而言,已知集合 A={a1,a2,……an},a i 表示项目编号,并已知此集合上的关系R={(a i,aj)},a i, aj 属于 A 集合(ij),其中(a i,a j)表示 ai 与 aj 之间是否存在冲突关系。现要求划分成不相交的子集 Al,A 2,…,A k(kn),使任何子集上的元素均无冲突关系,同时要求划分子集的个数尽可能少。下面,如运动会共设 9 个比赛项目,规定每个运动员最多可以参加三个项目,则A={1,2,3,4,5,6,7,8,9}R={(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[1:n,1:n]表示,若第 i与第 j 元素有冲突,则 R[i][j]=1。否则 R[i][j]=0。对应于上述例子的关系矩阵如图 3-18。1 2 3 4 5 6 7 8 91 0 1 0 0 0 0 0 0 02 1 0 0 0 1 1 0 1 13 0 0 0 0 0 1 1 0 04 0 0 0 0 1 0 0 0 15 0 1 0 1 0 1 1 0 16 0 1 1 0 1 0 1 0 07 0 0 1 0 1 1 0 0 08 0 1 0 0 0 0 0 0 09 0 1 0 1 1 0 0 0 0图 3-18 集合元素的关系矩阵 R[n][n] 另设置一个循环队列 Q11:n),存放集合 A 的元素,即项目编号;数组 S[1:n]用于存放每个元素所属的子集编号,即 S[i]中的值为对应的 i 项目的子集编号,如第 3 个项目为 A1 子集的元素,则 S[3]=1,第 5 个项目为 A3 子集的元素,则 S[5]=3,S 数组的最终结果应为:1 2 3 4 5 6 7 8 9S 1 2 1 1 3 4 2 1 4为实现这一过程,还要设置一个工作数组 TEMP[1:n],其 TEMP[i]值是第 i 个项目是否与当前子集中的其它项目相冲突的标志。如冲突,则 TEMP[i]非零,否则为 0。TEMP 的形成过程是用刚刚进入当前子集的项目编号 i 作为行号,并将 R[i][k](k=i+1:n)的值累加进入 TEMP[K]中去,也就是与进入当前子集的项目编号 i 相冲突的项目在 TEMP 数组设置为非零。这一过程一直进行到形成一个子集。当然,每形成一个新子集时,第一出队的元素可直接进入子集,不必用 TEMP 的状态来判断是否有冲突,而以后能否进入当前了集需一边形成 TEMP 状态,一边根据 TEMP 状态判断决定能否进入当前子集,即 TEMP[j]为非零时,则项目编号为 j 的元素不能进入当前子集中。 TEMP 数组形成中,S 数组元素对应于TEMP 数组元素值为 0 的位置,就以该子集编号填人。例如,第一个 TEMP 数组形成后的状态,以此状态值填人 S 数组后的 S 数组状态,如图 3-19。1 2 3 4 5 6 7 8 9Temp 0 1 0 0 1 1 1 0 11 2 3 4 5 6 7 8 9S 1 1 1 1以上给出的是 S 数组及 TEPM 数组形成后的状态,它们的形成过程要依赖于队列数组Q。而队列数组的变化过程是:首先, Q 队列数组的初态为项目编号;然后,每次形成一个子集时,要将队列中的所有元素出队一次,凡是属于当前子集的项目编号不再进队,不属于当前子集的就再次进队,作为下一子集形成前队列的初始状态,每次将当前初始队列中的所有元素全部出队完,就形成了一个子集,即出队后没再进队的项目。如此进行下去,直到队列中无元素可再出队为止。出队时,初态队列中第一个出队的元素不需要判断,直接作为所形成子集的第一元素,即第一出队元素直接形成 S 数组对应位置的值;而以后出队的元素是否属于该子集,就要根据形成的 TEMP 状态值来决定。其过程的算法思想是:采用循环筛选的方法,先将第一个元素进入子集,凡与已进入该子集的元素无冲突的元素划归一子集,再将余下的元素重新找出互不冲突的划归第二子集,以此类推,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:队列的应用_运动会.doc
链接地址:https://www.weizhuannet.com/p-9503307.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开