刘　丽，张　安，陈　永，陈光亭

(杭州电子科技大学理学院，浙江 杭州，310018)



一类新型网络构建问题的算法设计与分析

刘丽，张安，陈永，陈光亭

(杭州电子科技大学理学院，浙江 杭州，310018)

摘要：研究了一类新型网络构建问题，使有向网络中子网络的弧在切割成权值为L的分段时所产生的总分段数尽可能小。针对问题，假设有向网络每条弧的权值不小于L，给出子网络结构为有向路或强连通支撑子网络两种情形时的近似算法，并证明算法的最坏情况界分别为和3。

关键词：网络构建；近似算法；最坏情况界；装箱问题

0引言

1近似算法设计与分析

1.1　CDP问题

首先考虑CDP问题，即在有向图D中寻找一条s-t有向路，使构建该有向路所用的资源尽可能少。在算法中调用装箱问题[3]的经典算法——FFD作为子过程。对FFD算法，文献[4]给出了如下性质。

针对CDP问题，设计了算法A1，算法A1的具体描述如下：

1)利用Dijkstra算法[5]在网络D中找到一条总权重最小的s-t有向路Pst，记其弧集为A(Pst)={e1,e2,…,ek}；

3)对全部剩余弧段(权重为w′(ei)，i=1,2,…,k)，调用装箱问题的FFD算法将他们装入大小为L的箱子中，记b2为所用的箱子数，即此阶段所产生的分段数；

4)输出总共所需的分段数OUT=b1+b2。

1.2　CSCSS问题

本小节考虑CSCSS问题，即在有向网络D中找到一个强连通支撑子网络，使得构建该子网络所用的资源尽可能少。采用类似于算法A1的方法，得到算法A2，算法A2的计算步骤如下：

3)对全部剩余弧段(权重为w′(ei)，i=1,2,…,k)，调用装箱问题的FFD算法将他们装入大小为L的箱子中，记b2为所用的箱子数，即此阶段所产生的分段数；……