| 时间依赖无向中国邮路问题的分支限界算法 |
| |
| 引用本文： | 谭国真,孙景昊,肖宏业,吕凯.时间依赖无向中国邮路问题的分支限界算法[J].计算机科学,2011,38(2):110-113. |
| |
| 作者姓名： | 谭国真 孙景昊 肖宏业 吕凯 |
| |
| 作者单位： | 大连理工大学计算机科学与技术学院,大连,116023 |
| |
| 基金项目： | 本文受国家973项目(2005CB321904)，国家自然科学基金项目(60873256)资助。 |
| |
| 摘 要： | 时间依赖网络相比传统网络模型有更广泛的应用领域，比如会交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时，中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法，如奇偶图上作业法和Edmonds& Johnson算法，以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性，并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络，设计了新的剪枝条件，从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验，算法实验结果正确。
|
| 关 键 词： | 时变网络，中国邮路问题，分支限界，先进先出 |
Branch-bound Algorithm for Undirected Time-depended Chinese Postman Problem |
| |
| TAN Guo-zhen,SUN Jing-hao,XIAO Hong-ye,LU Kai.Branch-bound Algorithm for Undirected Time-depended Chinese Postman Problem[J].Computer Science,2011,38(2):110-113. |
| |
| Authors: | TAN Guo-zhen SUN Jing-hao XIAO Hong-ye LU Kai |
| |
| Affiliation: | (School of Computer Science and Technology,Dalian University Technology,Dalian 116023,China) |
| |
| Abstract: | |
| |
| Keywords: | Time-dependent network Chinese postman problem Branch and bound FIFO |
| 本文献已被 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
