计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2011年
2期
110-113
,共4页
谭国真%孙景昊%肖宏业%吕凯
譚國真%孫景昊%肖宏業%呂凱
담국진%손경호%초굉업%려개
时变网络%中国邮路问题%分支限界%先进先出
時變網絡%中國郵路問題%分支限界%先進先齣
시변망락%중국유로문제%분지한계%선진선출
时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型.当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难.首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds& Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确.
時間依賴網絡相比傳統網絡模型有更廣汎的應用領域,比如公交網絡和通信網絡都可以抽象成為時間依賴的網絡模型.噹模型中弧的訪問代價為時間依賴的變量時,中國郵路問題的求解將變得非常睏難.首先分析瞭傳統的中國郵路問題求解算法,如奇偶圖上作業法和Edmonds& Johnson算法,以及不能有效求解時間依賴中國郵路問題的根本原因;其次給齣瞭一般時變無嚮中國郵路問題的特性,併在此基礎上設計瞭該問題的分支限界最優化算法;然後針對FIFO(First In First Out)這一類特殊時變網絡,設計瞭新的剪枝條件,從而得到瞭更有效求解FIFO網絡的時變無嚮中國郵路問題的分支限界最優化算法;最後對算法進行瞭實驗,算法實驗結果正確.
시간의뢰망락상비전통망락모형유경엄범적응용영역,비여공교망락화통신망락도가이추상성위시간의뢰적망락모형.당모형중호적방문대개위시간의뢰적변량시,중국유로문제적구해장변득비상곤난.수선분석료전통적중국유로문제구해산법,여기우도상작업법화Edmonds& Johnson산법,이급불능유효구해시간의뢰중국유로문제적근본원인;기차급출료일반시변무향중국유로문제적특성,병재차기출상설계료해문제적분지한계최우화산법;연후침대FIFO(First In First Out)저일류특수시변망락,설계료신적전지조건,종이득도료경유효구해FIFO망락적시변무향중국유로문제적분지한계최우화산법;최후대산법진행료실험,산법실험결과정학.
