点击次数：

论文类型：期刊论文

发表时间：2011-05-15

发表刊物：计算机科学

收录刊物：PKU、ISTIC、CSCD

卷号：38

期号：5

页面范围：93-95,101

ISSN号：1002-137X

关键字：时间依赖;中国邮路问题;模拟退火;遗传算法

摘要：中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用.近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义.首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析.