中国计量学院学报
中國計量學院學報
중국계량학원학보
JOURNAL OF CHINA INSTITUTE OF METROLOGY
2010年
2期
167-170
,共4页
最短路%判定问题%多项式时间变换%NP-完全%动态规划
最短路%判定問題%多項式時間變換%NP-完全%動態規劃
최단로%판정문제%다항식시간변환%NP-완전%동태규화
对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点s,t,找出s和t之间的一条路,使得在满足总费用不超过一个给定正整数的s和t之间所有的路中,该条路的长度最短.通过将背包问题多项式时间变换为该问题的判定问题,证明了该问题是NP-完全的.并给出了求解此问题的一个动态规划算法.最后,我们得到了最优值的一个下界估计.
對一類帶弧費用約束的最短路徑問題進行瞭研究,即對于網絡中兩箇給定的頂點s,t,找齣s和t之間的一條路,使得在滿足總費用不超過一箇給定正整數的s和t之間所有的路中,該條路的長度最短.通過將揹包問題多項式時間變換為該問題的判定問題,證明瞭該問題是NP-完全的.併給齣瞭求解此問題的一箇動態規劃算法.最後,我們得到瞭最優值的一箇下界估計.
대일류대호비용약속적최단로경문제진행료연구,즉대우망락중량개급정적정점s,t,조출s화t지간적일조로,사득재만족총비용불초과일개급정정정수적s화t지간소유적로중,해조로적장도최단.통과장배포문제다항식시간변환위해문제적판정문제,증명료해문제시NP-완전적.병급출료구해차문제적일개동태규화산법.최후,아문득도료최우치적일개하계고계.
