无向赋权图最短通路的矩阵算法

Dijkstra算法是求赋权图最短通路中最著名的算法.但其数学的表达式却非常复杂,而且只求出起点到各点的最短通路的权.通过对赋权图进行矩阵定义以及定义相应的矩阵运算法则,就可以求出任意两点间的最短通路的权.这一算法为求赋权图的最短通路及权的编程提供了算法模型.     

树网络上的连通p-median问题

给定一个连通图G=(V,E),每一个顶点和边都赋予一个非负的权重,传统的p-median问题是要找出V的一个包含p个点的子集H,使得其余各点到H的赋权距离和最小。如果要求由H导出的子图是连通的,则称之为连通p-median问题。该文研究树网络上的连通p-median问题,给出了一个O(pn)的算法,随后把该算法推广到带有禁选点的树网络上。     

用启发式算法求解最短路径问题

提出了一种带有启发信息的邻接表结点存储结构模型,给出了结点间权值计算的具体评判函数,依据评判函数值优化邻接表中节点的相对位置.基于最短路径问题提出了带有启发信息的遗传算法思想,将启发信息加入到了初始种群生成过程中,提出了新的交叉方法.通过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较,结果表明...     

一种实用机器人路径规划方法的改进

针对一种基于蚂蚁觅食行为的移动机器人路径二次优化方法,指出其要求路径点的调整点足够多和容易陷入局部最优点的局限,说明该局限在实现上相对应的要求是传感器精度、机器人惯性和行走机构与地面的摩擦力,最后采用总路程长度作为优化目标函数并增加等分点对原方法改进.     

基于N 条最短路径的成品油管道优化设计

采用了赋权有向图来表示成品油管道工艺方案优化设计问题,若干个泵站位置候选点对应图的顶 点,两顶点间管段的总费用现值对应弧的权值,通过循环调用Dijkstra算法,求解出了前N 条最短路径作为最优和 次优方案,以备多方案比选。该方法既兼顾了工程实际的要求,又可以给出最优、次优工艺方案。实际算例表明该 方法切实可行。所提出的方法可以推广应用到其它油气管道工艺方案优化设计或其它工程应用。     

Mesh网络容错单播路由算法

基于k-Mesh子网连通的概念，提出一个简单的Mesh网络容错单播路由算法．该容错单播路由算法是基于局部信息的，因为路由算法在路由的过程中，只需要知道其相邻结点的信息而无需知道其他结点出错的情况．对于给定的源结点和目的结点，当路由路径扩展到每一个k-Mesh子网中时，该子网均可独立地完成算法的操作而无需考虑算法在其他k-Mesh子网中的操作状态．所以，路由算法是高度分布式的．容错单播路由算法的时间复杂性是最优的．模拟结果表明，路由算法所构造的路由路径长度非常接近于2个结点之间的最优路径长度．     

互连网络故障直径的研究

考虑了至多可以删除多少个顶点才能保证互连网络的连通。给出了网络的容错能力。根据Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径。利用广度优先搜索的思想，给出了求任意两个节点之间的n条内部节点互不相交。且在两点间所有路径中是最短的n条路径的算法。该算法为网络故障直径的研究提供了依据。而且。在故障存在但是网络连通的情况下。可以求得网络中任意两节点间的n条最并行路径。提高了网络的容错能力。本文对提出的方法及算法的正确性进行了证明，为研究互连网络的性质提供了新的研究方法。     

交通诱导系统中道路网络的表达与存储方法

考虑实际道路网络的特殊性以及最短路径算法对路网信息的要求,运用对偶图法的基本思想对前向关联边结构进行了改进,提出了一种能够提高路径优化算法实时性的路网表达方法与数据存储结构,并用Dijkstra和A*最短路径算法进行了验证。结果表明,这种方法在清楚表达转向限制、消除结点权重的同时,由于两个指针数组的引入,使得算法可以迅速而准确地定位相关结点的位置,从而减小了搜索空间,降低了最短路径算法的时间复杂度,提高了最短路径的搜索效率。     

Dijkstra算法与旅游路径优化

基于旅游业快速发展的事实,为满足游客省时、省钱、走最短路程的线路需求,对Dijkstra算法加以改进,即先利用Dijkstra算法依次求出局部最优解,然后整合得到全局最优路径,从而使改进算法更适合线路设计。最终在综合考虑旅游花费、交通时间、游览路程3个因素的前提下,以西安市及周边景点为例,设计出3种自驾车旅游最优路径方案,验证了新算法的可行性。     

复杂环境中移动机器人的一种避障策略

提出了机器人在复杂环境中寻找到达目标点最优轨迹的一种避障策略.首先,从3个方面考虑,提出了机器人的运动函数.第一,机器人运动必须在指定区域内;第二,机器人能够动态避障并到达目标位置;第三,机器人运动路径保证最短.其次,给出了机器人路径优化设置的条件:个体适配值、路径再优化和运动策略突变.最后,通过仿真实验,证明了所提出的方法是可行的.     

基于OPNET的校园网络组建分析

校园网的建设是每个学校的重要组成部分,对于校园网来说,就是确定连接节点的个数,运用设备使分布在不同位置的信息节点连接到一个统一的网络中,使整个校园网中的信息节点相互联通。本文找出影响校园网性能的主要因素和网络＂瓶颈＂,利用仿真软件OPNET搭建实验平台对改进的方案进行了仿真,并分析了实验结果。     

无线传感器和执行器网络可靠高效路由

针对当前的无线传感器与执行器网络（WSAN）技术缺乏实时性能以及工业无线环境的动态性问题,基于Kautz图设计容错、实时、高效、可靠的先验式路由FRER,不需要维持路由表,只利用节点IDs,根据节点IDs的匹配长度快速找到目标节点的最短路径.当节点故障时,不需要进行路径重挑,根据自身ID与目标节点ID的匹配,上一跳节点能够快速找到剩余节点的最短路径.考虑路径的多样性,不局限于Kautz拓扑,利用邻居节点信息拓展网络中路径的多样性.考虑链路故障,基于链路可用性历史信息组合多路径,保证在链路故障情况下网络维持可接受水平的路由路径可用性.实验结果表明,与REFER和Debruijn图相比,FRER在实时性、容错性和可靠性性能上优于两者.     

移动参考节点动态路径最优规划

在利用移动参考节点对无线传感器网络进行时间同步或定位的过程中,参考节点的移动路径规划,直接影响节点同步精度、定位精度和能量损耗。将移动节点的移动路径规划转化为对广播点的选取及广播点间路径规划,对应数学模型为经典的选址问题和旅行商问题。通过建立两者的最优联合数学模型,提出利用贪婪算法寻找最优的广播点并获得最优移动路径的方法。仿真结果表明：该路径能够覆盖整个网络,同时缩短参考节点的移动距离。     

星图上基于循环置换的任意两点之间的最短路径算法

针对路由选择对网络性能起重要作用,提出了星图上任意两点之间的最短路径算法．运用群论的循环置换的性质证明了两点之间的距离公式,给出了两点之间所有最短路径个数的一般代数表达式．     

由基本割集矩阵形成节点关联矩阵的简便方法

在电路综合中,由已知基本割集矩阵构成与之相应的无向线图,是个重要问题。但是,目前电路理论中尚无理想方法使其便于实现。本文提出一种简便方法,旨在使基本割集矩阵转换为关联矩阵,对于节点数不多的不可断连通图行之有效。     

基于表象式语义网络的图匹配算法

提出了一种在表象式语义网络中的查找方法,表象式语义网络问题的求解一般都是通过图匹配实现的,首先根据待求解的问题的要求构造一个带变量节点的语义网络,然后与计算机视觉系统中己存储的语义网络进行图匹配。当语义网络中的询问部分与系统中的语义网络图匹配后,则与询问部分匹配的事实就是问题的解。图匹配问题可以通过构造一个图的附属数据结构来完成,这个附属数据结构也称为相连图(association graph),对于两个图G=(V,A)以及G′=(V′,A′),构造相联图G″=(V″,A″),也就是说,V″是所有可能节点匹配对的集合,A″是所有相容节点匹配的集合。这相当于在相联图中寻求一个最大的基团(clique),其中基团定义为G″的完全连通的一个子图。最大基团满足其节点集合不是任何其他基团节点集的适当子集。     

谱聚类在给水管网分区优化中的应用

利用图划分技术和图论算法实现给水管网分区。根据给水管网分析,确定分区数量,建立权重邻接矩阵并计算图拉普拉斯矩阵及其特征向量,通过多路图划分对隐藏在特征向量中的聚类信息进行数据挖掘,采用遗传算法和K均值方法实现最佳节点聚类。利用PageRank和最短路径算法确定水表和阀门位置,最终实现给水管网优化分区。实际给水管网模型分区实例表明所提方法在给水管网分区的有效性。     

基于多参数节点排序的SDN控制器部署策略

针对已有的软件定义网络（SDN）控制器部署关注基于控制消息路由时延最优的问题,引入节点的介数中心性作为参数,分析了介数中心性对于控制器部署位置选择的重要性,并联合节点的可靠性提出了一种基于多参数节点排序方案（MFRS）的控制器位置部署策略,将节点进行排序并分层,依据节点间的连接关系计算出控制权值,最终确定控制器位置. 仿真结果表明,MFRS的控制消息路由跳数小于基于时延的最短路径算法,且基于MFRS的网络可靠性高于基于时延的最短路径算法.