用神经网络求解时间依赖网络最短路径问题的新算法(英文)  

A New Algorithm for the Shortest Paths Computation by Neural Networks on Time-dependent Networks

作　　者：贺红[1] 朱大铭[2] 马绍汉[2] 

机构地区：[1]山东理工大学计算机系,淄博255049 [2]山东大学计算机系,济南250100

出　　处：《复旦学报（自然科学版）》2004年第5期714-716,共3页Journal of Fudan University：Natural Science

基　　金：ProjectsupportedbytheNationalNaturalScienceFoundationofChina (6 98730 2 7)

摘　　要：时间依赖的网络与传统的网络模型相比更具有现实意义,具有广泛的应用领域.用实例证明了著名的Dijkstra算法在时间依赖的网络上不能有效地求解最短路径问题,给出了时间依赖的网络的定义和模型,给出一种实用反馈式神经网络来求解时间依赖的网络的最短路径问题.并用模拟实验验证了它在不同的网络更新时间区间上收敛速度的稳定性.结果是神经网络求解非NP 难解类优化问题的一种新尝试.Time-dependent networks are more practical or immediate significance compared with traditional networks models. There are instances to prove the famous Dijkstra's algorithm cannot be effectively used to solve the shortest path problems. A new kind of neural networks for continuously computing the shortest path on a time-dependent network is presented and the stability of the network is proved. This makes a new study on solving the optimization, but not NP-hard problems by neural networks.

关 键 词：时间依赖 神经网络 新算法 网络最短路径 最短路径问题 更新时间 DIJKSTRA算法 求解 收敛速度 优化问题 

分 类 号：N941.5[自然科学总论—系统科学] TP393[自动化与计算机技术—计算机应用技术]