系统管理学报
繫統管理學報
계통관이학보
JOURNAL OF SYSTEMS & MANAGEMENT
2007年
6期
678-684
,共7页
广义最大并行流%全多项式时间近似算法%算法复杂性%lossy网络%获得因子%广义的最短路
廣義最大併行流%全多項式時間近似算法%算法複雜性%lossy網絡%穫得因子%廣義的最短路
엄의최대병행류%전다항식시간근사산법%산법복잡성%lossy망락%획득인자%엄의적최단로
研究了Karakostas G给出的求解最大并行流问题的一个近似算法,将其算法的参数进行了改进,给出了算法的时间复杂性不依赖于物资数k的广义最大并行流的全多项式时间近似算法,该算法只适用于广义的lossy网络.用改进后算法求出的目标函数值更接近于最优值,对该近似算法的近似性和算法的时间复杂性进行了证明.最后,用C语言编程,计算数值例子,通过对比充分验证了改进后算法的正确性和有效性.
研究瞭Karakostas G給齣的求解最大併行流問題的一箇近似算法,將其算法的參數進行瞭改進,給齣瞭算法的時間複雜性不依賴于物資數k的廣義最大併行流的全多項式時間近似算法,該算法隻適用于廣義的lossy網絡.用改進後算法求齣的目標函數值更接近于最優值,對該近似算法的近似性和算法的時間複雜性進行瞭證明.最後,用C語言編程,計算數值例子,通過對比充分驗證瞭改進後算法的正確性和有效性.
연구료Karakostas G급출적구해최대병행류문제적일개근사산법,장기산법적삼수진행료개진,급출료산법적시간복잡성불의뢰우물자수k적엄의최대병행류적전다항식시간근사산법,해산법지괄용우엄의적lossy망락.용개진후산법구출적목표함수치경접근우최우치,대해근사산법적근사성화산법적시간복잡성진행료증명.최후,용C어언편정,계산수치례자,통과대비충분험증료개진후산법적정학성화유효성.