计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2013年
4期
305-308
,共4页
制服调换%路圈子图%圈包装%环流%线性规划松弛
製服調換%路圈子圖%圈包裝%環流%線性規劃鬆弛
제복조환%로권자도%권포장%배류%선성규화송이
Uniform Exchange(UE)%path-cycle subgraph%cycle packing%circulation%linear programming relaxation
利用制服型号数有限这一特征,对制服调换(UE)问题和以物易物的制服调换(BUE)问题各给出一个快速的线性时间算法.在常量阶有向图上,将BUE转化为一个顶点容量约束的整值最大环流问题,提出其整数线性规划表示,论证其可行域的整性.证明BUE的最优解必为对应UE的一个最优解子图.实验结果表明,UE和BUE的渐进最优值相同.
利用製服型號數有限這一特徵,對製服調換(UE)問題和以物易物的製服調換(BUE)問題各給齣一箇快速的線性時間算法.在常量階有嚮圖上,將BUE轉化為一箇頂點容量約束的整值最大環流問題,提齣其整數線性規劃錶示,論證其可行域的整性.證明BUE的最優解必為對應UE的一箇最優解子圖.實驗結果錶明,UE和BUE的漸進最優值相同.
이용제복형호수유한저일특정,대제복조환(UE)문제화이물역물적제복조환(BUE)문제각급출일개쾌속적선성시간산법.재상량계유향도상,장BUE전화위일개정점용량약속적정치최대배류문제,제출기정수선성규화표시,론증기가행역적정성.증명BUE적최우해필위대응UE적일개최우해자도.실험결과표명,UE화BUE적점진최우치상동.
