论文部分内容阅读
限制性的k-路问题是指。给定一个无向连通G=(V， E；w)，w：E→R+，求从点集V1={vi1，vi2,…，vim}中仇(m≤k)个点出发的k条路，其中从vis出发的路有ts条，∑ts=k，且这k路必须通过点集V2={vj1，vj2，…，vjk}中的每一点，每一条路必须经过V2中至少一个点.目标：使这k条路的权重之和最小.适当变化条件会出现三种情况；(1)在计算该k条路的权重之和时，重复的边的权重只计算一次，使∑e∈k∪i=1E(Pi)w(e)达到最小，在该情况下，此问题是NP-难的，该文给出了一个启发式算法.(2)求出的k条路为边不交的路，使∑i=1e∈∑E(Pi)w(e)达到最小，其中E(Pi)∩ E(PJ)=0(i≠j)，在该情况下，该文给出了多项式的时该边的最大容量c(c为一个新的函数c:E→R+)使mink∑i=1e∈∑E(Pi)w(e)间算法.(3)重复边按照重复的边数计算，但是经过每条边的路的数目不能超过最小，该文给出了一个多项式时间的算法.