| 满足路径约束的最优路算法 |
| |
| 引用本文： | 吴传信,倪明放. 满足路径约束的最优路算法[J]. 运筹与管理, 2004, 13(4): 41-44 |
| |
| 作者姓名： | 吴传信 倪明放 |
| |
| 作者单位： | 中国人民解放军理工大学,通信工程学院,江苏,南京,210007 |
| |
| 摘 要： | 满足路径约束的最优路问题已被证明是NP-hard问题。本针对源点到宿点满足两个QoS(服务质量)度量的路由问题，给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的，表明算法是有效的。
|
| 关 键 词： | 网络优化 服务质量 整数规划 启发式算法 |
| 文章编号： | 1007-3221(2004)04-0041-04 |
| 修稿时间： | 2003-10-21 |
Path-Constrained Path-Optimization Routing |
| |
| WU Chuan-xin,NI Ming-fang. Path-Constrained Path-Optimization Routing[J]. Operations Research and Management Science, 2004, 13(4): 41-44 |
| |
| Authors: | WU Chuan-xin NI Ming-fang |
| |
| Abstract: | The problem of path-constrained path-optimization routing is proved to be NP-hard one that cannot be exactly solved in polynomial time. In this paper we describe a heuristic algorithm for a source to a destination routing problem satisfying two QoS (Quality of service)metrics which is defined as follows. Given a directed graph with two weights, cost and delay, on each link, we find the cheapest path such that the total delay of the path is no more than a given threshold. Our algorithm is polynomial, which demonstrates its good efficiency. |
| |
| Keywords: | network optimization QoS integer programming heuristic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
