点击次数：

论文类型：期刊论文

发表时间：2011-02-15

发表刊物：计算机科学

收录刊物：PKU、ISTIC、CSCD

卷号：38

期号：2

页面范围：110-113

ISSN号：1002-137X

关键字：时变网络;中国邮路问题;分支限界;先进先出

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