最短路由算法在SDH复用段环网业务配置中的应用

对SDH业务路径选择等关键技术进行深入分析,总结出一种基于最短路由的环网业务配置算法。该算法在最短路由相同的情况下考虑分节点奇偶数讨论的优化方案。再通过枚举的方式进一步验证了此按节点奇偶数讨论的最短路由算法的可靠性和稳定性。     

基于手机探测定位救灾系统的设计与研究

设计与研究了一种基于手机探测定位的救灾系统。针对探测问题,该系统中的探测模块采用手机探测信号的办法间接地进行受灾区的生命探测,并生成探测报告。针对救援问题,搜救模块分析处理探测报告,使用三角形质心定位算法进行目标定位,同时使用Floyd算法计算搜救的最短路径。本设计的系统使用手机探测定位技术,比直接生命探测法更为有效,成本更低。同时采用了定位与最短搜救路径结合的方式,使得搜救更为迅速而有效。     

结点有拥塞的动态最短路径问题的算法研究

最短路径问题在交通运输领域以及网络路由选择方向都有着重要的应用.本文在有必经结点且所经结点无序的最短路径算法的基础上,研究结点有拥塞且拥塞程度是动态变化的最短路径问题.对于这种情况的研究,在交通运输领域的高速公路以及局域网络上的路由选择都有着重要的应用.文中对结点的权值,即拥塞程度的预测采用了Kalman滤波方法,并用改进了的Dijkstra算法求解结点间的最短路径.相关实验结果及分析表明,该方案可以有效地解决结点有拥塞且拥塞动态变化的最短路径问题.     

基于蚁群算法的集成电路无网格布线

蚁群算法[1]作为一种较新的进化类方法,目前已经在若干领域取得了成功的应用,诸如：旅行商问题、二次分配问题、通讯网络中的路由问题以及负载平衡问题、大规模集成电路设计等。本文提出了一种基于蚁群算法的集成电路无网格布线算法。对于给定的布线平面,该算法首先由障碍图形和各个线网的端点生成一个包含最短路径的访问点阵,建立初始信息索矩阵,然后利用蚁群算法所特有的路径寻优功能来找到当前布线路径上的最短路径。同时本文在路径搜索过程中引入了引力的概念,使得蚁群在引力的作用下以较快的速度找到目标端点。     

基于"矩阵乘法"的网络最短路径算法

 网络最短路径问题可以作为许多实际应用问题的模型,但传统的求解算法其迭代过程复杂.本文描述了基于矩阵乘法的最短路算法,其时间复杂度与Dijkstra算法相同.在给定的一个网络图中,在不改变网络图中的最短路的条件下,删除"多余"的结点或边,可以达到简化网络图和提高求解速度的目的,从而降低计算复杂性.最后,研究了该方法在最短路径问题和旅行商问题中的应用.实例表明,这种算法与传统的动态规划技术相比,具有运算简便、易于理解的优点.     

基于深度优先搜索的分层网络最短路径算法

大规模网络分层后进行数据预处理是其搜索最短路径的加速方法,现有的分层网络数据预处理存在以下问题：随着网络规模越来越大,数据预处理计算量也越来越大;预处理完的数据需要大量储存空间。针对上述问题提出一种基于深度优先搜索的分层网络最短路径搜索算法,该算法将每簇网络抽象成“一个高级节点”组成高级网络,在高级网络上利用深度优先搜索去掉冗余的簇完成数据预处理后,再利用Dijkstra算法搜索最短路径。采用该算法在大规模树形分层通信网络上进行最短路径搜索实验,结果表明该算法比基于关键点数据预处理的最短路径算法平均搜索时间稍长,但在数据预处理时间和存储空间上大大降低。     

一种借助RAM存储器完成PDIUSBD12总线枚举调试的方法

USB设备端开发必须首先完成USB总线枚举的调试,只有完成了总线枚举,才有可能借助调试软件观察USB总线数据传输情况.而USB设备总线枚举过程的调试有着较大的工作量,初次进行USB调试的调试者一般需要借助于一些USB分析仪的帮助.但是USB分析仪普遍价格昂贵,对于普通的调试者来说是很不合适的.本文介绍了一种在没有USB分析仪的情况下,利用系统已有的RAM存储器,对USB设备控制器PDIUSBD12的总线枚举调试过程进行监控的方法.该方法对硬件要求低,不仅节省成本,而且操作简便,有较高的调试效率.     

基于层弧容量比求解网络最大流

针对最短增广链算法一开始选取增广路径的随意性,给出了一种在单源、单汇网络中通过层弧容量比来求解网络最大流的新算法。该改进算法的思想是运用宽度优先搜索的方法,在改进的分层剩余网络中找到与汇点相邻接且容量最大的弧(称为关键弧),再选择含有关键弧的最短增广路径,根据制定的规则,从而有序地进行流值增广,直至没有可增广的路径终止。在BA无标度网络中进行实验,发现新算法的效率略高于最短增广链算法,且能把关键弧的容量更加合理地分配给上一层弧,提高了最大流的流值。     

k最短可靠路径及其优化问题

k最短路径在边失效模型中,存在一个等长路径的选择问题,基于可靠性的选择是有效的解决方案。这里提出了一种k最短路径限制下的可靠性模型来度量k最短路径,进一步把等长路径的选择问题转化为一个可靠性优化问题,即选择使得可靠性最大的k最短路径。最终通过设计近似算法有效地解决了优化问题,实例证明了该算法的有效性。     

基于最短路径分割算法的SDH环网通路组织优化

针对SDH双向复用段保护环通路组织设计中存在的通路资源利用不充分及网络负载不平衡问题,本文提出一种基于最短路径分割的通路组织安排算法,该算法结合最短路径算法和平衡加载算法的优点,较好地满足了工程设计在经济性、安全性等方面的要求.本文最后实例中将该算法应用于SDH环网通路组织优化设计中,优化效果明显.