点带约束成本的最短路问题

《点带约束成本的最短路问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、高校应用数学学报A辑Appl.Math.J.ChineseUniv.Ser.A2000,15(1):93～96点带约束成本的最短路问题李帮义何勇姚恩瑜(浙江大学应用数学系,杭州310027)摘要本文提出了点带约束成本的最短路问题.证明了该问题是NP-完全的,并利用动态规划给出了一个伪多项式算法.对所有顶点约束成本相同的情况,2给出了一个时间复杂性为O(mn)的算法.对最小点成本最短路问题,给出了一个2时间复杂性为O(n)的算法.关键词最短路问题,计算复杂性,算法.分类号(中图)O224;(1991MR)68Q25.§1引言最短路问题(简称SP)是网络中的一个经典问题,

2、其各种变形问题普遍受到重视和研[1～3]究.关于弧带约束成本的问题,出现了一系列的研究成果,但关于顶点带约束成本的问题未引起足够的重视,而实际上许多问题是顶点带约束成本的,如运输网络中,节点处货物的装卸和转运,检查站的收费等.定义1设G=〈V,A,L〉是个有向网络,
V
=n,
A
=m.
〈vi,vj〉∈A,给它赋一个非负参数lij,称作长度.
vi∈V,给它赋一个正参数ai,称作点成本,不妨设为有理数.定义2设P是一条路,记P=v1v2⋯vrvr+1,定义P的长度L(P)=l12+l23⋯+lr(r+1).定义P上的点成本为C(P)=a1+a2+⋯ar.定义3点带

3、约束成本的SP问题(P1):求给定的两顶点间一条最短路P,满足C(P)≤C.这里C是一个正有理数.定义4最小点成本最短路问题(P2)是在最短路中求最小点成本者,即求:min{C(P):P是v1→vn的最短路}.本文讨论上述定义的(P1),(P2)问题.对(P1)将证明是NP-完全的,但不是强NP-完全的.对(P2)将证明是多项式时间可解的.收稿:1998-11-03.修回:1999-03-15.国家自然科学基金(19701028)和国家重点基础研究专项经费资助.94高校应用数学学报A辑第15卷第1期§2主要结果首先证明问题(P1)是NP-完全的.证明中用到如下定义的奇

4、偶划分问题(P3):2m例给定正整数集A={a1,a2,⋯,a2m},∑ai=2B.问:是否存在S1A,S2A,S1∩i=1S2=,而且∑ai=B,∑ai=B,
S1∩{a2k-1,a2k}
=1,
S2∩{a2k-1,a2k}
=1,1≤k≤m?i∈Si∈S12[4]引理1划分问题(P3)是NP-完全的.定理1顶点带约束成本的问题(P1)是NP-完全的.证问题(P1)的判定形式为:给定问题(P1)的实例,及两个上界B1,B2,问:是否存在一条给定两顶点v1→vn的路P,使L(P)≤B1,C(P)≤B2?下面证明划分问题(P3)可以多项式变换到问题(P1)的判定形

5、式.2m设有前者的一个实例A={a1,a2,⋯,a2m},∑ai=2B.构造一个如图1所示的有向网络i=1G.其中每个顶点的成本c(v0)=c(v2m+1)=0,c(vi)=ai(1≤i≤2m).若顶点vi,vj有弧〈vivj〉相连,则其长度为B-(c(vi)+c(vj))/2,0≤i,j≤2m+1.定义B1=mB,B2=B.v1v3v5v2m-3v2m-1v0v2m+1v2v4v6v2m-2v2m图1显然上述构造可在多项式时间内完成.下面证明:划分问题(P3)有解充分必要条件是网络G中存在一条v0→v2m+1的路P,使C(P)≤B2,L(P)≤B1.设划分问题有解,

6、S1={ai1,ai2,⋯,aim},则G中找到一条v0→v2m+1的路P:v0→vi1→vi2mm→⋯→vim→v2m+1,满足C(P)=∑aij=B=B2,L(P)=(m+1)B-∑aij=mB=B1.j=1j=1因而该路是所求的解.反过来,设网络G中存在一条v0→v2m+1的路P.由网络的特征知,该路必经过每一顶点子集{v2k-1,v2k}中恰一个点,k=1,2,⋯,m.故不妨设P形如v0→vi1→vi2mmm→⋯→vim→v2m+1,使∑aij≤B2=B.因L(P)=(m+1)B-∑aij≤B1=mB,故∑aij=j=1j=1j=1B.为此定义S1={ai1,

7、ai2,ai3,⋯,aim},S2=A-S1.则
S1∩{a2k-1,a2k}
=1,
S2∩{a2k-1,a2k}
=1.故S1,S2即为(P3)的一个解.推论1(P1)不存在多项式算法,除非P=NP.下面寻求解决(P1)的伪多项式算法.定义5d(j,C)=min{L(P):P是v1→vj的一条路,C(P)≤C}.由定义,d(j,C)是C的非增函数,当C充分大时即为v1→vj最短路长度.这里C为正整李帮义等:点带约束成本的最短路问题95数.引理2d(1,C)=0,d(j,0)=∞,(j≠1),d(j,C)=min{d(j,C-1),min{d(i,