最短路径扩散机制下实时可靠性网络路由选择方法研究

针对网络通信实时性、可靠性的要求,提出一种最短路径扩散机制下实时可靠性网络路由选择方法,依据链路质量对加入网络的节点构建逻辑路径,形成树状结构。将某节点与其它节点之间的可用物理链路看作辅助路径,得到Mesh形网络拓扑结构。分析了最短路径扩散机制,利用最短路径扩散机制对网络中全部节点构建最短路径信息。介绍了网络交通流和交通引力场模型,考虑节点对交通流的引力作用,将传输路径看作影响引力的指标,通过交通引力场实现网络路由选择。实验结果表明,所提方法在保证网络实时可靠性的同时,可减少能耗,降低数据丢包率,提高网络吞吐量。     

最短路径扩散机制下实时可靠性网络路由选择方法

针对网络通信实时性、可靠性的要求,提出一种最短路径扩散机制下实时可靠性网络路由选择方法。依据链路质量对加入网络的节点构建逻辑路径,形成树状结构。将某节点与其他节点之间的可用物理链路看作辅助路径,得到Mesh形网络拓扑结构。分析了最短路径扩散机制,利用最短路径扩散机制对网络中全部节点构建最短路径信息。介绍了网络交通流和交通引力场模型,考虑节点对交通流的引力作用,将传输路径看作影响引力的指标,通过交通引力场实现网络路由选择。实验结果表明,所提方法在保证网络实时可靠性的同时,可减少能耗,降低数据丢包率,提高网络吞吐量。     

一类网络容量扩充问题

给定一个连通网络,找两点之间的最短路,作为两点之间的流量路径。每条路径都有一定的需求,网络中每条边的容量至少为经过该边的所有路径的需求之和,若某条边的容量小于经过该边的所有路径的需求之和,则需要对其容量进行扩充。每种扩充方案的扩充费用是关于扩充容量的函数。本文给出解决该问题的一个多项式时间算法,使得各边容量达到需求,且总的扩充费用最小。     

动态速度和代价约束的最短路径算法

Dijkstra算法是计算有向图中一个节点到其余各个节点最短路径的著名多项式时间算法,在交通规划、地理信息系统等方面有重要的应用。本文改进Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径,即有向图的节点之间除了静态的距离外,还有动态的速度和代价,例如城市交通中的高峰与非高峰时段影响速度/时间,收费与非收费路段影响代价;时间和代价在最短路径中由一个比例因子控制,通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的,实验结果也表明了该算法的有效性。     

最短路径问题的DNA算法

最短路径问题是在一个带权图的两个顶点之间找出一条具有最小权和路径的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间内才能得到解决,本文基于分子生物技术并利用Adleman-Lipton模型给出最短路径问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对个城市的最短路径问题,首先将它视为一个具有顶点和边的图,并将顶点,边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到最短路径问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计以及在操作中巧妙的消除了路径途经城市数目不同的影响,能使我们在合理小的范围内寻找最短路径问题的解,较大地简化了问题的复杂度。     

交通网络最优安全路径选择模型与算法

针对交通网络任意路段均可能发生中断的最小损失路径选择问题,提出交通网络最优安全路径选择模型,并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值,然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中,当最短路径删除后该网络依然连通时,最优安全路径问题转化为最短路径问题,其计算复杂度为O(n2);当最短路径删除后该网络不再连通时,最优安全路径问题转化为最小最大问题,其计算复杂度为O(mn),且仅与网络中节点和边的数量有关.最后,结合交通网络的实际情况对最优安全路径进行了算例分析.     

TSP最短路径的必要条件初探

对于被访问城市数为n的不对称旅行商问题,构造了一个n行和n列的方阵,每一行上的n个元素为同一个被访问城市;每一列上的n个元素为n个互不相同的被访问城市.依次从该方阵的第一列到第k列上各取出一个城市,同一行上不存在两个被取出的城市,这样取出的城市序列就构成了一条长度为k的路径.主要讨论最短路径的性质:如果一条长度为(n-1)的最短路径能被产生,则该路径上的任一长度为k的路径都为最短路径,k=1,2,…,n-2.该性质为旅行商问题算法研究的基础.     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=（V,E;w;s,t）,其中s,t是2个固定顶点,w：E→R^＋是边的长度函数．最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者．对正权重无向图中严格第三短路问题给出一个O（n^4）多项式时间算法．     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=(V,E;w;s,t),其中s,t是2个固定顶点,w:E→R+是边的长度函数.最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者.对正权重无向图中严格第三短路问题给出一个O(n4)多项式时间算法.     

农村社会关系网络中搜索技术研究

针对最短路径 Dijkstra 算法存在占用空间大、效率较低的问题,提出了改进的 Dijkstra 算法,在此基础上,进一步研究了Dijkstra-relation 多路径搜索策略。改进的 Dijkstra 算法首先以现实农村社会关系为基础,由于社会关系具有可变性、复杂性等特征,因此用关系距离表示关系远近,然后采用邻接表存储方式,节省存储空间,使用堆排序提高算法的效率,最后通过关系距离限值和关系路径长度限值对关系路径有效性进行甄别,使得计算的关系路径更符合农村现实情况。Dijkstra-relation 算法通过删除最短路径上的节点,计算起始节点到中间节点的最短路径,然后与中间节点到目标节点的最短路径连接,求解两人之间建立联系的多条路径。实例验证结果表明,Dijkstra-relation 算法缩小了搜索范围,提高了搜索效率,搜索的多条关系路径符合农村社会中人际交往的情况,提高了自主选择性。