【www.zhangdahai.com--其他范文】
杨子兰, 朱娟萍, 李 睿
(1. 丽江文化旅游学院信息学院，丽江 674199; 2. 云南大学数学与统计学院，昆明 650091)
人们对通信网络、物联网、远程医疗等的需求日益增长[1]。面对如此庞大的发展压力，作为现代社会基础设施的通信网络，其网络容量面临严峻的挑战。如何在受限条件的约束下，扩张现有的网络使其满足日益增长的流量需求？这成为人们一直关注的热点问题[2–6]。
本文考虑信号在通信网络中的传输是沿着支撑树形图进行传输的，支撑树形图上的节点表示信号的传输节点。当用户对当前的信号需求急剧增加时，造成信号在弧上传输的压力，于是需对支撑树形图的弧容量进行扩张，使得信息从发出点尽可能快地发送到其他节点。传统意义下，对原有的通信网络进行扩张升级大都采用加线路边的方法[6–8]。然而，通信线路太长不仅会影响通信质量也会增加成本。基于此，通信网络的扩张问题不仅要考虑当前用户对信号的需求量，还要考虑使扩张费用尽可能地少，且信号传输的距离要求在指定的范围内，否则会影响通信质量。
本文将通信网络扩张升级问题抽象为带约束的支撑树形图容量扩张问题(The Capacity Expansion Problem of Spanning Arborescence with Constraints, CEPAC)：给定有向图G= (V,A;w,c,p)，其中V为顶点集，A为弧集，|V| =n且|A| =m。正数w(e)、c(e)、p(e)分别表示弧e ∈A的长度、容量和单位扩张费用。设正数W为长度限制值及正数D为预期容量要求。考虑在图G中找一棵支撑树形图T，对任意的弧e ∈T，假如c(e)＜D，则在弧e上扩张D-c(e)个单位的容量，且要求T的w权重不能超过W。目标函数是使支撑树形图T上的扩张费用尽可能少，其数学规划表达式为
其中T为G中所有支撑树形图的集合。当c(e)＜D时，取d*(e) =D-c(e)，否则取d*(e) = 0。本文的容量扩张问题只讨论弧上的容量扩张，且只涉及有根节点的树形图。对没有根节点的情形，可遍历优化所有顶点为根的情况。
Fulkerson[9]是较早提出带约束的网络容量扩张问题的学者，考虑扩张费用为线性条件下如何合理地分配预算资金使得扩张后的网络容量最大化，并给出了容量扩张理论研究中应用非常广泛的标号算法。Yang 和Zhang[2]考虑了瓶颈容量扩张问题，文中研究了关于支撑树形图的对弧的最大容量扩张问题，给出了其NP-困难性的证明。Taghavi 和Huang[10]提出预算受限下的随机网络容量扩容问题，考虑预算受限下的多阶段随机网络扩容模型，针对需求的不确定性，使用情景树方法，建立带随机信息的混合整数规划模型，并给出启发式的拉格朗日算法。Fragkos 等[11]主要关注离散时间范围内，始点–终点对之间的需求扩容的情况。从实际应用的角度分析某条弧一旦被应用即产生维护费用，故总费用随时间变得越来越高。针对具有容量的模型，Fragkos 等结合局部改进启发式方法，提出了基于弧的拉格朗日松弛方法。针对不具有容量的模型，提出了4 种Benders 分解公式，并阐明如何利用问题结构提高算法性能。
本文提出的CEPAC 问题是一类新的网络扩容模型，可归结为赋两权重的支撑树形图优化问题。Guignard 和Rosenwein[12]较早开始研究这类赋两权重的支撑树形图优化问题，分析资源受限的支撑树形图问题(简记为RMWA)的目标函数和决策变量的特点，将问题按决策变量分解成一个独立的背包问题和一个独立的资源不受约束的拉格朗日松弛对偶模型。基于此分解思想，Fischetti 和Vigo[13]对RMWA 问题提出分枝分割的求解思路。同样基于分解思想，杨子兰等[14]在没有引入拉格朗日乘子的情况下把RMWA 问题划分成无资源约束的最小权重支撑树形图问题和n个独立的背包问题，并设计出一个贪婪分解启发式算法。RMWA 问题可视为CEPAC 问题的一种特殊情况。针对CEPAC 问题，本文由NP-困难的0-1 背包问题归约出CEPAC 问题的一个实例，研究了CEPAC 问题的NP-困难性。从支撑树形图多面体最优面出发构建最优支撑树形图序列，设计了CEPAC 问题的(2,1)-近似的带约束的拟阵交算法。接着，研究CEPAC 问题的特殊情况：最小支撑树形图容量扩张问题(The Capacity Expansion Problem of Minimum Spanning Arborescence, CEPMA)，利用双权重字典序对朱–刘算法进行修改，得到一个强多项式算法。
本文的贡献点包括三个方面。首先，将通信网络扩张升级实际问题抽象成组合最优化问题，提出一种新的带约束的网络扩张模型。其次，基于拟阵交研究支撑树形图多面体的最优面形成特点，设计出求解CEPAC 问题的带约束的拟阵交算法。最后，对特殊的最小支撑树形图容量扩张问题，给出了强多项式时间算法。
设I表示0-1 背包问题的实例，输入为ai,qi(i=1,2,···,N)及正数M，数学模型为
设τ(I)表示CEPAC 问题的一个实例，其构建方法如图1，有向图G= (V,A;w,c,p)，置D= 2 和W=M+2N。对弧ei，取w(ei) =ai+1,c(ei) = 1,p(ei) =qmax-qi。对弧eN+2i-1，取w(eN+2i-1) = 1,c(eN+2i-1) = 2,p(eN+2i-1) =qmax。对弧eN+2i，取w(eN+2i)=1,c(eN+2i)=1,p(eN+2i)=qmax，其中qmax=maxi{qi}。
假设1实例I有最优值Max 和对应最优解Opt0-1={j1,j2,···,jk}的充分必要条件是实例τ(I)有最优值Nqmax-Max 和对应最优解
同时
实例τ(I)的构建是多项式时间的且0-1 背包问题是NP-困难的，故CEPAC 问题是NP-困难的。
2.1 带约束的拟阵交算法分析
给定有向图G= (V,A)和根节点r ∈V，如图2。图3 是以r为根的r-支撑树形图，即对所有v ∈V，都可从根节点r有路到达。设G的无向基础图为G′= (V,E)，其中E为A中的弧去掉方向形成的边集合。置
图2 有向图G
图3 r 为根的不同支撑树形图
F1={S ⊆E(G′)|G(V,S)不含圈}, F2={S ⊆A|S ∩δ-(v)≤1,v ∈V{r}},δ-(v)为进入点v的弧集。那么，M1= (A,F1)为关于G的图拟阵，M2= (A,F2)为G关于入弧的划分拟阵[5]。故任意一棵r-支撑树形图都可以视为拟阵M1和M2的公共独立集。反之，如果拟阵M1和M2的公共独立集的基数为|V|-1，那么，拟阵M1和M2的公共独立集为一棵r-支撑树形图[5]。
于是CEPAC 模型可转述为
为方便起见，记cost*(e) =d*(e)p(e)和cost*(T) = Σe∈Td*(e)p(e)。设T*为CEPAC 问题的最优支撑树形图，记opt=cost*(T*)。引入拉格朗日乘子λ，得CEPAC 问题的松弛问题LR(λ):
对任意的T ∈F1∩F2，定义弧e ∈T的拉格朗日权重cost*(e)λ= cost*(e)+λw(e)。设λ*为最大化LR(λ)的λ值，并记LR=maxλ≥0LR(λ)。
Berger 等[15]提出带预算约束的匹配问题和拟阵交最大化问题，作者巧妙地利用拟阵交独立集的相关性质，以此将受预算约束的拟阵交问题转换为公共独立集进行求解。为解决带约束的最小支撑树问题，Ravi 和Goemans[16]分析了支撑树多面体，并研究了最优多面体之间形成的最优支撑树序列。基于文献[16]的支撑树最优多面体相邻关系，Hassin 和Levin[17]进一步考虑支撑树形图分解成划分拟阵与图拟阵的交。在这些研究基础上，本文借助文献[16]的支撑树Megiddo 参数搜索和文献[15]的拟阵交的Megiddo 参数搜索思路，建立支撑树形图多面体与拟阵交之间的关系[5]，将一棵最优支撑树形图T通过基本变换[18]转换成与T相邻的最优支撑树形图T′。我们希望获得松弛问题LR(λ)的一个最优拉格朗日乘子λ*以及关于拉格朗日权重cost*(e)λ*= cost*(e) +λ*w(e)最优的两棵支撑树形图T，T′∈F1∩F2，且w(T)≤W ≤w(T′)。Megiddo 参数搜索[16,19]思路基于拉格朗日松弛，其优点是可以在不知道λ*的情况下求出关于cost*(e)λ*的最优支撑树形图。对任一的λ，Megiddo 参数搜索基本原理：在关于cost*(e)λ= cost*(e)+λw(e)最优支撑树形图集合中，搜索关于w的最大支撑树形图T′及最小支撑树形图T。如果w(T)＞W，则λ ＞λ*；
如果w(T)＜W，则λ ＜λ*；
其余λ=λ*。Megiddo 参数搜索求得最优λ*对应的T和T′的算法步骤如下。
步骤1对每对弧e和f，计算临界点
及其对应的cost*(e)λef= cost*(e)+λefw(e)。利用字典序(w(e),cost*(e)λef)，求出关于w的最大支撑树形图T′和最小支撑树形图T(具体方法见第3 节算法CEPMA)。如果w(T)＞W，则λef ＞λ*，若
根据λef，则有cost*(f)λ*＞cost*(e)λ*；
如果w(T)＜W，则cost*(f)λ*＜cost*(e)λ*；
否则cost*(f)λ*=cost*(e)λ*。
步骤2通过O(mlogm)次步骤1 的比较，间接将G的弧关于cost*(e)λ*排序。在G的关于cost*(e)λ*最优的树形图集合中，搜索依权重w最大支撑树形图T′和最小支撑树形图T，使得w(T)≤W ≤w(T′)。
引理1[5,18]设T是G的一棵r-树形图，u,v ∈V(T)，且uv/∈A(T)。如果T中不存在v-u路，那么，置T′=T+uv-u′v，则T′仍是一棵r-树形图，其中弧u′v ∈A(T)，我们称该变换为树形图的基本变换。
引理2[5,18]若在有向图G中存在两棵r-树形图T与T′，则T经过有限次的基本变换后可以得到T′。
定理1设T*为CEPAC 问题的最优支撑树形图，对于弧e ∈A(T*)，若f/∈A(T*)为G中与e同头的弧，且在T*上f的头不是尾的后代。如果cost*(e)＞cost*(f)，则w(T*)+w(f)-w(e)＞W成立。
证明 假设该结论不成立，即G中存在与e同头的弧f′/∈A(T*)，使得
cost*(e)＞cost*(f′), 且w(T*)+w(f′)-w(e)≤W.
根据引理1，置T′=T*+f′-e，则w(T′)≤W成立，且
cost*(T′)=cost*(T*)+cost*(f′)-cost*(e)＜cost*(T*)
与题设矛盾。
从拟阵的角度，支撑树形图是给定有向图的图拟阵M1= (A,F1)和划分拟阵M2=(A,F2)的公共可行基或交[5,16]。支撑树形图T和T′对应支撑树形图凸多面体上的两个不同顶点，若T和T′是相邻的，则有一条边连接T和T′这两个顶点。由凸多面体的相邻关系[18]和支撑树形图的基本变换，我们得到如下引理。
引理3在支撑树形图凸多面体上，支撑树形图T与T′相邻的充分必要条件是T与T′相差一条同入头的交换弧(除根节点外)，即存在弧e ∈T和e′∈T′，使得T-e=T′-e′且e和e′同入头，见图4。
图4 相邻的两支撑树形图
设调用Megiddo 参数搜索算法得到两棵支撑树形图T和T′。若有w(T′)=W或w(T)=W成立，即求得原问题的最优解，算法停止。若w(T)＜W ＜w(T′)，置Γ为关于拉格朗日权重cost*(e)λ*最优的支撑树形图所构成的集合，该集合形成一个支撑树形图凸多面体。考虑该凸多面体关于拉格朗日权重cost*(e)λ*的最优面，如果存在两棵最优支撑树形图T和T′，由定理1 和引理3，则存在关于cost*(e)λ*的最优支撑树形图序列T0=T,T1,···,Ti,Ti+1,···,Tk=T′，使得Ti和Ti+1是相邻的即相差一条同头入弧，其中i=0,1,···,k-1。选择某相邻的Ti和Ti+1满足w(Ti)≤W和w(Ti+1)＞W，则有
w(Ti+1)=w(Ti)+w(ei+1)-w(ei)≤w(Ti)+wmax,
其中ei ∈TiTi+1,ei+1∈Ti+1Ti及wmax=maxe∈A w(e)，故有
W ＜w(Ti+1)≤W+wmax.
引理3的具体算法如下。
步骤1搜索图G与Ti的弧有相同头的入弧构成的集合S，对于入弧f ∈S要求：
1) 在Ti中f的尾不是f的头的后代；
2) 记e ∈Ti为与f同头的弧，需满足cost*(f)λ*=cost*(e)λ*且w(f)≤w(e)。
步骤2记f*=arg minf∈S{w(e)-w(f)}，置Ti+1=Ti+f*-e*，其中e*是Ti中与f*同头的入弧。
步骤3如果w(Ti+1)＞W，算法停止，否则转步骤1。
定理2设Γ为关于拉格朗日权重cost*(e)λ*=cost*(e)+λ*w(e) 最小的支撑树形图组成的集合，则存在T ∈Γ，使得cost*(T)≤LR且w(T)≤W+wmax。
证明 对任一T ∈Γ，有
cost*(T)=[cost*(T)+λw(T)-λW]-λ[w(T)-W]≤LR-λ[w(T)-W].
因此cost*(T)≤LR，当且仅当w(T)≥W。
借鉴文献[16]对带约束的最小支撑树的权重分析，对任给的ϵ ＞0，考虑λ=λ*+ϵ或λ=λ*-ϵ，则集合Γ至少包含一棵关于cost*(e)+λw(e)最小的支撑树形图，即存在一棵支撑树形图T≤∈Γ，使得w(T≤)≤W，否则z(λ*+ϵ)＞z(λ*)与λ*为最优相矛盾。同理，也存在一棵支撑树形图T≥∈Γ，使w(T≥)≥W。取Ti=T≤和Ti+1=T≥，由相邻关系Ti和Ti+1存在一条同头入弧的区别。取T=Ti+1，因w(Ti)≤W，即有w(T)≤W+wmax。
2.2 带约束的拟阵交算法及近似度分析
算法1带约束的拟阵交算法
输入：图G=(V,A;w,c,p)，两个正数W和D
输出：支撑树形图Ti+1
步骤1剔除图G中w(e)＞W的弧；
步骤2调用Megiddo 参数搜索算法求得CEPAC 问题的最优拉格朗日乘子λ*对应的支撑树形图T和T′，使得w(T)≤W ≤w(T′)，其中T和T′关于cost*(f)λ*是最优的；
步骤3调用引理3 的算法，依次搜索形成关于cost*(e)λ*最优的支撑树形图序列T0=T,T1,···,Ti,Ti+1,···,Tk=T′，在搜索的同时计算选取的支撑树形图的w-权重，直到某个i ∈{1,2,···,k}，使得w(Ti+1)≥W和w(Ti)≤W成立，输出Ti+1，算法停止。
定理3CEPAC 问题的带约束的拟阵交算法是(2,1)-近似的，其时间复杂度为O(mlog2mlogn+mn)。
证明 算法CEPAC 的步骤1，剔除所有w(e)＞W的弧，所以wmax≤W。由算法可知输出的w(Ti+1)≥W，由定理2 可推出cost*(Ti+1)λ*≤LR ≤opt。而
w(Ti+1)=w(Ti)+w(ei+1)-w(ei)≤w(Ti)+wmax≤2W,
故带约束的拟阵交算法是(2,1)-近似的。
步骤2中Meggido 参数搜索需考虑O(log2m)次最小支撑树形图求得λ*[15–16,18]，而求解关于权重最小的支撑树形图的Tarjan 算法的时间复杂度为O(mlogn)[20]，故时间复杂度共为O(mlog2mlogn)。搜索λ*(实际值未知)对应的支撑树形图序列T0,T1,···,Tk，搜索原理要求Ti和Ti+1是相邻的。此时，只需简单交换T′上具有同头的且cost*(e)λ*权重相同的入弧，故可在|T′T|≤m步内完成。换弧至多需考虑O(n)个节点，故换弧总时间复杂度为O(mn)。于是，带约束的拟阵交算法总时间复杂度为O(mlog2mlogn+mn)。
本节研究带约束的支撑树形图容量扩张问题的特殊形式：最小支撑树形图容量扩张问题。有向图G= (V,A;w,c,p)，其中V为顶点集，A为弧集，|V| =n且|A| =m。三个正数w(e)、c(e)、p(e)分别表示弧e ∈A上的长度、容量和单位扩张费用。设正数D为预期容量，目标是在G中找到一棵支撑树形图T，要求其关于w权重最小且在T上容量扩张的费用尽可能小。其数学规划表述为
如果c(e)＜D，取d*(e)=D-c(e)；
否则，取d*(e)=0。
由于cost*(e) =d*(e)p(e)，且CEPMA 问题首先要求保证所求得的支撑树形图关于w是最小的，然后再考虑支撑树形图的容量扩张费用。于是，对G中的弧e建立双权重(w(e),cost*(e))。结合字典序，对经典的最小支撑树形图朱–刘求解算法[21–23]进行修改如下。
算法2CEPMA
输入：图G=(V,A;w,c,p)，正数D
输出：关于字典序(w,cost*)最小的支撑树形图T
步骤1删除根节点r处的入弧。对所有的节点v ∈V{r}，找到关于字典序(w,cost*)最小的入弧，置这n-1 条入弧的集合为S；
步骤2如果G(V,S)包含圈，转步骤3；
否则，G(V,S)是CEPMA 问题的最优解，算法停止；
步骤3若G(V,S)存在圈C，收缩圈C为虚点t，考虑顶点i(顶点i为圈C外的点)到达顶点j(顶点j为圈C上的点)的弧上相关权重调整如下
其中w(C(j),j)表示C上的顶点进入到顶点j的弧的w权重，且置cost*(i,t)=cost*(i,j)；
步骤4对所有的虚点t，选择关于字典序(w(i,t),cost*(i,t))最小的那条入弧记为et。设ft为S中进入实际点的入弧，置S=S+et-ft，转步骤2。
CEPMA 算法思路以字典序中第一个权重w为主进行破圈，用使w权重的差达到最小的弧来替代圈上的弧。当多条弧的w权重差相同时，接着考虑选择字典序中cost*权重最小的弧，CEPMA 算法的前提是只对w权重进行修改，cost*权重不变。
定理4CEPMA 问题的求解算法CEPMA 是时间复杂度为O(mn)的强多项式时间算法。
证明 算法CEPMA 思想原则是进行破圈处理，而进行破圈的规则是选使w权重的差达到最小的弧，然后再确定弧上的容量扩张费用最小。当多条最小w权重差弧存在时，才考虑选择第二权重cost*最小的弧。算法CEPMA 是在求解最小支撑树形图的朱–刘算法基础上考虑选择字典序中cost*权重最小的弧，朱–刘算法的时间复杂度是O(mn)[21–22]，故CEPMA 算法的时间复杂度也为O(mn)。
本文由通信网络扩张的现实需求出发，抽象出带约束的支撑树形图容量扩张问题的数学模型，证明了CEPAC 问题是NP-困难的。针对CEPAC 问题，利用拟阵交的相关性质以及字典序，设计了一个带约束的拟阵交算法，该(2,1)-近似的算法调用了求解最小支撑树形图容量扩张问题的算法CEPMA。CEPMA 问题是CEPAC 问题的一种特殊情况，算法CEPMA 采用字典序修改朱–刘算法，其运行时间为O(mn)。
猜你喜欢 拉格朗多面体字典 直击多面体的外接球的球心及半径中学生数理化(高中版.高考数学)(2022年2期)2022-04-26整齐的多面体数学大王·低年级(2022年3期)2022-03-17独孤信多面体煤精组印课外生活·趣知识(2021年8期)2021-08-24多面体的外接球与内切球中学课程辅导·高考版(2020年12期)2020-12-23这样的完美叫“自私”杂文选刊(2019年12期)2019-12-06字典的由来小学阅读指南·低年级版(2019年11期)2019-07-01拉格朗日的“自私”意林·少年版(2018年22期)2018-12-05拉格朗日的“自私”新青年(2018年8期)2018-08-18这样的完美叫“自私”幸福·婚姻版(2018年12期)2018-02-22大头熊的字典小天使·一年级语数英综合(2017年11期)2017-12-05本文来源：http://www.zhangdahai.com/shiyongfanwen/qitafanwen/2023/0613/610871.html
