Hits:

Indexed by:期刊论文

Date of Publication:2011-02-15

Journal:计算机科学

Included Journals:PKU、ISTIC、CSCD

Volume:38

Issue:2

Page Number:110-113

ISSN No.:1002-137X

Key Words:时变网络;中国邮路问题;分支限界;先进先出

Abstract:时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型.当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难.首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds& Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确.