N的最短路径算法.pdf

文档介绍：第z8卷第8期增刊 2007年8月仪器仪表学报 Chinese Journal of ScientificInstrument N的最短路径算法* 杜华,周冬明,赵东风,白云洪,林琳(云南大学信息学院通信工程系昆明650091) 摘要:在脉冲耦合神经网络(pulse-coupled work,PCNN)N(adjustable weight PCNN) 模型,将其成功应用到求解最短路径的问题上,N的求解算法。该模型在求解过程中考虑了某个节点的前驱和可变的权值,不需要使用延时的思想,所以对网络路由、运输等问题具有一定的指导意义。关键词:PCNN;N;最短路径算法 Shortest—path algorithm using adj ustable weight pulse-coupled work Du Hua,Zhou Dongming,Zhao Dongfeng,Bai Yunhong,Lin Lin (Department munications Engineering,Information College,Yunnan University,Kunming 650091,China) Abstract:Proposed Adjustable weight PCNN(N)model based on pulsecoupled work (PCNN),and essfullyapplied it tosolvetheshortest-path problem,moreover,the solvingalgorithm of N was alsopresented thesolving process,it only need toknow theusherandthe variableweight of aneuron,and has no use forthedelayviewpoint andhasdefinitesignificance insolving work route problem andthetransportation problem. Key words:PCNN;N;shortest-path algorithm 1 引言最短路径(shortestpath,SP)问题[1]是指在一个给定网络中寻找出一条从某点出发到特定点的最短线路。 SP问题在实际运用中颇为广泛,例如,网络路由器中的路由选择,运输问题中选择两个城市间最短路程,电路输送问题中的线路选取等等因此,对SP问题的研究在现代生活中有着一定的现实意义。对于SP问题,比较经典的算法是Dijkstra算法[1], 该算法对于求解SP问题具有广泛的指导意义。随着运筹学和组合优化算法的发展,Bellman对有向无环网络运用了动态规划的思想进行求解,这些方法对sP问题的求解做了的很大贡献,然而此类算法都是串行的,在时间计算问题上基本无法满足系统更高的要求。因此,寻求SP 问题的并行算法越来越倍受关注。人工神经网络具有大规模并行处理、容错性、自组织和自适应能力即联想功能等特点,已逐渐成为目前广泛关注的一种并行算法。后来,随着脉冲耦合神经网络(pulse-coupled work,PQ州)的发展,顾晓东等人[z-