论文摘要
中国邮路问题是图论经典问题之一,在软件测试、邮件投递等诸多领域中都被广泛应用。时间依赖中国邮路问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中,比中国邮路问题更具优势,具有重要的应用和研究价值。本文介绍了在传统静态网络中,中国邮路问题(Chinese Postman Problem简记CPP)的分类、研究现状、以及应用领域;然后分析了传统中国邮路问题的局限和在时间依赖网络环境下的中国邮路问题相对于传统中国邮路问题的优势,以及时间依赖网络中中国邮路问题的研究现状和当前遇到的困难以及研究意义;为后面研究打下了基础。在这篇文章中,有以下内容:(1)给出传统方法并不适于时间依赖网络环境的根本原因:网络的时间依赖特性导致网络各个边权值的不固定。我们给出传统方法并不适用于时变网络(即时间依赖网络)条件的病态实例,以便对传统方法不适于时变网络环境的根本原因有更深地了解。(2)给出时间依赖中国邮路问题的特性和分支限界最优化方法。我们用定理和推论的形式给出适合求解时变无向、有向中国邮路问题的特性,并且对这些特性进行了证明,确保了它们的正确性,并以此为基础构造问题的剪枝条件,设计了相应的分支限界最优化方法;(3)对于FIFO的时间依赖网络增加了一些特殊性质,并提高了算法的效率。针对FIFO(first in first out)这一类特殊的时变网络,我们给出相应的特性以及基于此的FIFO剪枝条件,从而得到更高效的分支限界最优化方法。(4)对算法进行了测试和分析。我们先构造该问题的解空间树,对问题的规模有了初步的了解,同时通过一个实例简单地演示了该算法的执行过程,并对该问题和算法进行了分析;最后,给出了算法的测试结果,并在实验的基础上对该算法进行更深一部的分析。本文首次利用分支限界方法,求解了时间依赖网络中国邮路问题的精确解。引入了时间因素,使问题的复杂性大大增加。根据实验结果我们可知算法对于小规模的时间依赖有向、无向中国邮路问题非常有效。