| 一种多约束最优路径宽度优先松弛算法* |
| |
| 引用本文： | 钱进,陈立家,贺贵明.一种多约束最优路径宽度优先松弛算法*[J].计算机应用研究,2007,24(1):90-93. |
| |
| 作者姓名： | 钱进 陈立家 贺贵明 |
| |
| 作者单位： | （1.武汉大学 计算机学院, 湖北 武汉 430079；2.武汉大学 电子信息学院, 湖北 武汉 430079) |
| |
| 基金项目： | 国家自然科学基金资助项目(90204008) |
| |
| 摘 要： | 在分析单播QoS路由问题的基础上,提出了宽度优先松弛算法BFRA，其核心思想是基于改进的宽度优先搜索策略,采用特殊的松弛算法分别前向（从源节点）和后向（从目标节点）搜索网络拓扑。前向搜索预先计算路径的综合度量、约束等参数,收集路径信息;后向搜索则采用Costmeasurement策略对路径进行选择和筛选,不断搜索到新的可行路径,并选取最优路径。讨论了在路径振荡时BFRA选取次优路径,为其他QoS流的接入预留了资源。理论分析表明BFRA保存的状态信息较少,时间复杂度为线性，仿真结果表明,BFRA发现最优路径的成功率较高。
|
| 关 键 词： | 多约束 花费 前向搜索 后向搜索 松弛 路径振荡 |
Breadth First Relax Algorithm for Multi Constrained Optimal Path |
| |
| QIAN Jin,CHEN Li ji,HE Gui ming.Breadth First Relax Algorithm for Multi Constrained Optimal Path[J].Application Research of Computers,2007,24(1):90-93. |
| |
| Authors: | QIAN Jin CHEN Li ji HE Gui ming |
| |
| Affiliation: | (1.College of Computer, Wuhan University, Wuhan Hubei 430079, China;2.College of Electronic Information, Wuhan University, Wuhan Hubei 430079, China) |
| |
| Abstract: | |
| |
| Keywords: | Multi Constrained Cost Forward Search Backward Search Relax Path Surge |
|
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
