Neural network based algorithm for multi-constrained shortest path problem | |
Dong, Jiyang ; Zhang, Junying ; Chen, Zhong ; Liu, D ; Fei, S ; Hou, ZG ; Zhang, HG ; Sun, CY ; Dong JY(董继扬) | |
2007 | |
关键词 | COMPLEXITY |
英文摘要 | Multi-Constrained Shortest Path (MCSP) selection is a fundamental problem in communication networks. Since the MCSP problem is NP-hard, there have been many efforts to develop efficient approximation algorithms and heuristics. In this paper, a new algorithm is proposed based on vectorial Autowave-Competed Neural Network which has the characteristics of parallelism and simplicity. A nonlinear cost function is defined to measure the autowaves (i.e., paths). The M-paths limited scheme, which allows no more than M autowaves can survive each time in each neuron, is adopted to reduce the computational and space complexity. And the proportional selection scheme is also adopted so that the discarded autowaves can revive with certain probability with respect to their cost functions. Those treatments ensure in theory that the proposed algorithm can find an approximate optimal path subject to multiple constraints with arbitrary accuracy in polynomial-time. Comparing experiment results showed the efficiency of the proposed algorithm. |
语种 | 英语 |
内容类型 | 期刊论文 |
源URL | [http://dspace.xmu.edu.cn/handle/2288/69777] ![]() |
专题 | 物理技术-已发表论文 |
推荐引用方式 GB/T 7714 | Dong, Jiyang,Zhang, Junying,Chen, Zhong,et al. Neural network based algorithm for multi-constrained shortest path problem[J],2007. |
APA | Dong, Jiyang.,Zhang, Junying.,Chen, Zhong.,Liu, D.,Fei, S.,...&董继扬.(2007).Neural network based algorithm for multi-constrained shortest path problem.. |
MLA | Dong, Jiyang,et al."Neural network based algorithm for multi-constrained shortest path problem".(2007). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论