传感器网络定向扩散机制中梯度生成算法的研究

如何生成优化的梯度是传感器网络定向扩散中的一个关键问题,本文在分析一种基本梯度生成算法的问题基础之上,利用兴趣包的转发次数对其进行改进,设计了一种分布式的最短路径梯度生成算法.该算法极大的降低了邻居节点间建立"平行梯度"和"逆向梯度"的概率,可构建从源节点到sink节点的多条最短路径.仿真表明,改进的算法可建立更为有效的梯度,从而使得定向扩散中数据报文沿着更短的路径传输,无线传感器网络的能量利用率更高.     

基于能见度图的元胞疏散最短路径模型研究

近年来发生的火灾多在人员密集场所,当突发事件发生时,人员疏散往往特别困难,因此,规划行人在大型公众聚集建筑物中的疏散路径非常重要。基于能见度图建构的元胞疏散最短路径模型可直接用于实际的紧急疏散指示路径的规划,避免设置大量逃生指示装置致使工程成本过高及视觉不美观,并且也解决了有限制逃生指示装置数量当作限制条件的最大涵盖面积的求解复杂、空间大的问题。     

A Fast Method for Shortest-Path Cover Identification in Large Complex Networks

Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring. However, the existing methods are time-consuming for even moderate-scale networks. In this paper, we present a method for fast shortest-path cover identification in both exact and approximate scenarios based on the relationship between the identification and the shortest distance queries. The effectiveness of the proposed method is validated through synthetic and real-world networks. The experimental results show that our method is 10⁵ times faster than the existing methods and can solve the shortest-path cover identification in a few seconds for large-scale networks with millions of nodes and edges.     

堆场集装箱翻箱的PCNN优化控制算法

集装箱的堆存状态与理想发箱顺序很难保持一致, 翻箱操作是不可避免的. 为降低堆场的翻箱率, 提高作业效率, 在获得集装箱的取箱顺序前提下, 将每取一个集装箱所产生的可能状态视为一个状态结点, 所需的翻箱次数加一个基数作为状态结点间的连接权, 把翻箱优化问题转化为最短路径求解问题. 脉冲耦合神经网络(Pulse-coupled neural network, PCNN)具有独特的自动波并行传播的特性, 适用于求解大规模实时问题, 能一次求出源点到其他所有目标点的最短路径, 从而获得最优的翻箱方案. 其所需要的计算量仅正比于最短路径的长度, 与路径图的复杂程度及路径图中的通路总数无关. 这为建立集装箱的智能控制系统奠定了坚实的理论基础.     

一种基于最短路径介数的重要节点发现算法

网络中重要节点的发现是研究网络特性的重要方面之一,在复杂网络、系统科学、社会网分析和互联网搜索等领域中具有广泛的应用价值。为提高全网范围内重要节点发现的效率和有效性,提出了一种基于最短路径介数及节点中心接近度的重要节点发现算法,通过最短路径介数的方法确定全网内的重要节点,利用中心接近度分析重要节点的重要性。测试结果表明,与同类的系统比较起来,该方法具有比较好的性能。     

A*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.     

基于数据库的Dijkstra算法的改进与实现

数据库作为处理大量数据的主要手段,已经被广泛应用于生活的各个领域,经典的D ijkstra算法对求解最短路问题有很好的指导作用.本文讨论了如何在数据库存储方式下进行D i-jkstra算法改进的必要性及其实现过程,以发挥该算法在现代生活中的作用.     

一种新的粘连字符图像分割方法

针对监控画面采样图像中数字的自动识别问题,提出一种新的粘连字符图像分割方法。该方法以预处理后二值图像的连通状况来判定字符粘连的存在,并对粘连字符图像采用上下轮廓极值法确定候选粘连分割点,以双向最短路径确定合适的图像分割线路。仿真实验表明,该方法能有效解决粘连字符图像的分割问题。     

有回路无根多刚体系统图论描述的优化问题

在求解多刚体系统中任意刚体的绝对角速度等运动量时，需要对指定刚体到零刚体的路径上所有刚体的某一物理量作求和运算。某一刚体到零刚体的路径长度直接影响着该刚体运动学分析计算量的大小。对有回路的无根多刚体系统，寻找最优的派生树系统，恰当选择与零刚体直接相连的刚体，可以使零刚体到所有刚体的路径长度总和为最小，最大限度减小动力分析的计算量。首次就这一优化问题使用图论方法进行了分析，提出了解决办法。结合一个简单实例，阐述了对于有回路无根多刚体系统图论描述的优化处理流程。     

A Heuristic for Dijkstra''s Algorithm with Many Targets and Its Use in Weighted Matching Algorithms

Abstract. We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node s and a target set T is specified and the goal is to compute a shortest path from s to a node in T . Our interest in the shortest path problem with many targets stems from its use in weighted bipartite matching algorithms. A weighted bipartite matching in a graph with n nodes on each side reduces to n SSMTSP problems, where the number of targets varies between n and 1 . The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a heuristic that leads to a significant improvement in running time for the weighted matching problem; in our experiments a speed-up by up to a factor of 12 was achieved. We also present a partial analysis that gives some theoretical support for our experimental findings.