文档介绍：分类号密级 UDC 注 1 学位论文 K最短路径算法及其应用研究(题名和副题名) 邱钊( 作者姓名) 指导教师刘贵松( 副) 教授电子科技大学成都(姓名、职称、单位名称) 申请学位级别硕士学科专业计算机软件与理论提交论文日期 2014 . 03. 2 6 论文答辩日期 2014 . 0 5 . 20 学位授予单位和日期电子科技大学 2014 年 6 月答辩委员会主席评阅人注 1 :注明《国际十进分类法 UDC 》的类号。 K SHORTEST PATHS PRO BLEM ALGORITHM AND ITS APPLICATION RESEARCH A Master Dissertation Submitted to University of Electronic Science and Technology of China Major: Computer Software and Theory Author: Qiu Zhao Advis or: Professor Guisong Liu School : School puter Science & Engineering 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名: 日期: 年月日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘, 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后应遵守此规定) 签名: 导师签名: 日期: 年月日摘要摘要经典的网络最短路径( Shortest Path , SP )问题解决静态、确定网络中单源最短路径或所有顶点对间的最短路径问题,这种狭义的 SP 方法具有很大的应用局限性。 K 最短路径问题(KSP) 作为 SP 问题的扩展,在实际优化决策中期望得到一个按最优、次优、再次优等顺序排列的决策集合,其在物流、序列比对、网络和文本处理等领域有着非常广泛的应用。因此,快速的 KSP 算法研究无疑更适应实际问题的解决且意义重大。目前,广泛的应用需求推动了 KSP 问题的研究,并使其再次成为近年来国际上的研究热点,但相比解决经典 SP 问题的算法, KS P 研究的突出成果并不多见。本文针对 K 最短路径问题算法,结合已有研究成果做了较为深入的研究,取得如下成果: 1、提出了基于启发式搜索的无约束图中 Single -pair KSP 快速算法:启发式搜索基于每一个状态空间中搜索的位置进行评估,进而得到最好的位置,再从当前最好位置进行搜索直到目标节点。这种策略可以避免大量无谓的搜索路径,提高算法效率。本文运用启发式搜索策略,并使用 on -the -fly search 技术解决 K 最短路径问题,提出一种在 K 比较小的时候的高效率算法。实验证明,该算法在当 K 很小的时候比现有的算法效率高。 2、研究脉冲耦合神经网络模型改进及其在 KSP 问题当中的应用:脉冲耦合神经网络是一种基于猫的视觉皮层建模提出的神经网络模型,具有强大的计算和模拟能力。本文提出了一种改进的脉冲耦合神经网络模型,并对模型参数调整做了详细探讨。结合 single -pair KSP 和 single -source KSP 问题研究提出了相应的实现算法。同时,结合当前常用的地图路径搜索应用进行了对比仿真。实验表明,由于 PCNN 的并行计算特征,使得 KSP 问题的计算速度大大提高。 3、提出了一种基于波传递思想的 KSP 算法:考虑到水流动的自然特性与路径之间的关系,当波传递的速度一定时,其传递时间与其经过的路径长度成正比。由于波传递与具体节点的无关性,可将该思想用于解决针对从一个节点到其他所有节点的 K 最短路径问题,即 single -source KSP 问题。关键词: 启发式算法, K 最短路径, 神经网络, 优化问题 I ABSTRACT ABSTRACT The c work shortest path (Shortest Path, SP) problem is aims to determine the shortest path between two nodes or from one