通讯网路问题

来源:互联网 发布:cnki中国期刊数据库 编辑:IT博客网 时间:2020/02/25 14:09

MCM1994B  通讯网络问题

在你的公司里各部门每天都要分享信息,包括前一天的销售统计和当前的生产指南,尽快付出这些信息是十分重要的。

假定一个通讯网络用于从一台计算机向另一台计算机传输数据组(文件),作为例子,考虑如图A-13的图模型。

顶点V1.....表示计算机,边e1.....表示(在有边的顶点表示的计算机之间)要传输的文件,T(ex)表示传输文件ex所需的时间,C(Vv)表示计算机Vv可同时传输的文件的能力(指文件的数量),文件传输必须占用传输该文件的两台计算机所需的全部时间,例如,C(Vv)=1表示计算机Vv一次只能传输一个文件。

我们感兴趣的是以最优方式安排传输,使得传输完所有文件所用的总时间最少,这个最少的总量间称为完工时间(makespan)。为你的公司考虑下面的情况。

情况A

你的公司有28个部门,每个部门有一台计算机,每台计算机在图A-14中用一个顶点表示,每天必须传输27个文件,在图A-14中用边表示,在这个网络中对所有的x和y,T(ex)=1,,C(Vv)=1,找出该网络的一个最优时间表和相应的完工时间,你能向你的主管人员证明,对该网络你求得的完工时间是最小可能的吗?叙述你求解该问题的方法,你的方法适用于一般情形吗?即是否适用于T(ex),C(Vv)及图的结构都任意的情形?

分析:对图A-14来说:每台计算机只能传输一个文件,且所需时间都相等为1;

只能传输一个文件即比如,选V15和V16之间传输文件,就要把与V15和V16相连的边删掉,即可转化为找对集问题

也就是问题就可转化为第一个一分钟要传输那些文件,第二个一分钟要传那些文件,。。。。

只有当前的一份钟传的东西足够多才能花费的时间越少。(贪婪算法)

因此算法步骤为:就是每次要找最大对集,找完之后一份钟后文件传完,就要把这些边删掉,重新再剩下的边中再找最大对集,直到没有边为止。

但是如果是这种情况:


先找最大对集,如图所示:这是需要花费1+1+1+1+1=5,然而我们可以找到4分钟,就是要让对集里面包括度数大的节点,然后把这两个影响因素(1边数,2边和最大度关联)融合在一起,方法:给度数的的点赋权值,比如1.04等等(要求要足够小,比1大就行,太大不行)


情况B

假定你的公司改变了传输要求,你必须在相同的基本网络(见图A-14)上考虑不同类型和大小的文件,传输这些文件所需的时间用表A-8中每条边的表示,对全部y仍有T(ex)=1对新网络找出一个最优时间表及其完工时间,你能证明对新网络求得的完工时间是最小可能的吗?叙述你求解该问题的方法,你的方法适用于一般情形吗?试对任何特有的或出乎意料的结果发表评论。

分析:此时不同的是文件传输时间不一样,即权值不一样,还是贪婪算法,先传输费时间的文件,这时把其他文件传完这个文件还没传完,这是需要在剩下的文件中找带权值的最大对集(要保证还没传完的必须包含在里面)。依次类推即可。

情况C

你的公司正在考虑扩展业务,如果扩展了的话,每天会有一些新的文件(边)要传输,这种扩展还包括计算机系统的升级换代,28个部门中的某些部门将配备每次能传输不止一个文件的新的计算机,所有这些变化都在图A-15和表A-9、A-10中表明,你能找到的最优时间表及其完工时间是什么?你能证明对该网络求得的完工时间是最小可能的吗?叙述你求解该问题的方法,试对任何特有的或出乎意料的结果发表评论。


分析:这个与前面不同的是,每个计算机的传输能力不一样,即一台计算机可以同时传好几个文件,受到人员指派中选辅导班的启发,我们应该这样做,假设vk计算机可同是传k份,就把这个计算机复制k个,转化为一对一问题,然后用前面的方法找带权值的最大对集即可。

    做出答案后可以证明其是不是最优的方法:

举例说明:比如是这个图(只能传一份)
           

根据这个图,可得这3个7  只能传一个,比如最上面的7,只有把这个7传完后才能穿上面的9(可以和别的7一起传),而且3个7分别要传,至少要花费7* 2+9=23分,只要你的算法算出是23分,就一定是最优的,这就是所谓的用结果证明结果。   


0 0
原创粉丝点击