Pheromone based alternative route planning

In this work, we propose an improved alternative route calculation based on alternative figures, which is suitable for practical environments. The improvement is based on the fact that the main traffic route is the road network skeleton in a city. Our approach using nodes may generate a higher possibility of overlapping. We employ a bidirectional Dijkstra algorithm to search the route. To measure the quality of an Alternative Figures (AG), three quotas are proposed. The experiment results indicate that the improved algorithm proposed in this paper is more effective than others.     

基于Dijkstra算法的藏语分词研究

介绍了迪杰斯特拉(Dijkstra)算法的定义、思想和步骤。将一个藏语句子构成一个"线性"图,通过图中的算法实现藏语句子的分词操作。将典型图的非线性结构变成特殊的线性结构,并且通过辅助结点将图特殊化,最后再还原。实践证明,使用本方法能巧妙地使用Dijkstra算法来实现分词操作。     

一种Dijkstra优化算法的研究与实现

最短路径计算是地理信息系统应用中的重要功能之一,经典的最短路径算法是D ijkstra算法,但该算法由于结构过于复杂导致计算效率较低,无法满足实际应用需求。从实际应用需求出发,针对D ijkstra算法的不足,在拓扑存储结构、拓扑关系数据结构以及拓扑网中节点存储顺序三方面对算法进行优化,通过分析与实际应用表明提出的D ijkstra改进算法不仅结构简单易于实现,而且算法效率高,能够满足实际应用需求。     

边缘计算中云边任务下发策略研究

目前边缘计算的相关研究大部分着眼于如何将设备端数据卸载至边缘端进行处理,而未考虑云中心如何高效率、低延时地将不同任务下发至边缘节点的问题.针对该问题,文中提出了一种边缘计算架构模型,通过对任务进行统一建模,使用改进的Dijkstra算法得到任务下发最优路径,减少所需计算节点数量和提升计算性能,使其能在最短的时间内下发到...     

多阶段群体满意决策最优算法

针对多阶段群体满意决策问题,应用图论知识提出一种求解多阶段群体满意策略问题的最优算法.定义权ω为决策者对决策的总评价值,给出距离d和群体满意策略等概念.考虑实际情况中决策者的能力和认知的不同,赋予决策者变化的决策权重.将多阶段群体满意策略问题转换成在一个带有权向量的多部有向图中找权最大的路的问题.最后给出计算实例.     

Distributed Dijkstra sparse placement routing algorithm for translucent optical networks

In this paper we study translucent optical networks as an alternative to fully transparent and fully opaque optical networks. In the former networks, a technique called sparse placement is used to overcome the lightpath blocking caused by the signal quality degradation, using much less regenerators, which must strategically be placed, in contrast to a fully opaque network. In this paper we propose a sparse placement algorithm based on two requirements. The first one is signal regeneration necessary to re-amplify, reshape, and retime the optical signals after some predefined transparent distance in order to successfully receive the signals at the destination node. The other is load balance of the traffic in the network aimed at efficient usage of the network capacity resources. We apply a distributed Dijkstra routing algorithm which dynamically changes weights of links during the process of locating regeneration capable nodes. We compare the performance of the proposed algorithm with commonly used sparse placement algorithms through simulation experiments. The benefits are such that load balancing of the network traffic is fully utilized, and with technological development it will be sufficient to equip up to 30% of nodes in the network with electronic regenerations in order to have the same performance as in an opaque network.

Graph‐theoretical identification of dissociation pathways on free energy landscapes of biomolecular interaction

Biomolecular association and dissociation reactions take place on complicated interaction free energy landscapes that are still very hard to characterize computationally. For large enough distances, though, it often suffices to consider the six relative translational and rotational degrees of freedom of the two particles treated as rigid bodies. Here, we computed the six‐dimensional free energy surface of a dimer of water‐soluble alpha‐helices by scanning these six degrees of freedom in about one million grid points. In each point, the relative free energy difference was computed as the sum of the polar and nonpolar solvation free energies of the helix dimer and of the intermolecular coulombic interaction energy. The Dijkstra graph algorithm was then applied to search for the lowest cost dissociation pathways based on a weighted, directed graph, where the vertices represent the grid points, the edges connect the grid points and their neighbors, and the weights are the reaction costs between adjacent pairs of grid points. As an example, the configuration of the bound state was chosen as the source node, and the eight corners of the translational cube were chosen as the destination nodes. With the strong electrostatic interaction of the two helices giving rise to a clearly funnel‐shaped energy landscape, the eight lowest‐energy cost pathways coming from different orientations converge into a well‐defined pathway for association. We believe that the methodology presented here will prove useful for identifying low‐energy association and dissociation pathways in future studies of complicated free energy landscapes for biomolecular interaction. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2010     

基于CPM原理和Dijkstra算法的SPM网络计划模型及性质

CPM(关键路线法)网络计划适用于分析工序间存在严格紧前关系(任意工序只能在它的所有紧前工序都结束时才能开始)的进度计划.针对工序间不存在严格紧前关系(任意工序只要其紧前工序中的一个结束它就可以开始)的进度计划,以CPM原理和Dijkstra算法为基础,提出SPM(最短路线法)网络计划以及拟机动时间概念,根据不同的建模原理,建立了两个SPM网络计划模型,并给出了其建立方法以及各模型拟机动时间的求法,分析了每个模型的性质,最后通过算例对其中的一类模型进行了验证.     

不可恢复道路堵塞路径选择问题及其算法

针对不可恢复道路堵塞的路径选择问题，分析了堵塞发生的不同起始时间对通过被堵塞边的费用(时间)产生的影响，这种影响引起的后效性使得这个问题不适合用动态规划中逆序推算方法求解。本设计了一种算法(MDA)，对经典的Dijkstra算法中的权值计算进行了修正，证明了算法的复杂性为O(n^2)，并用该算法对模型进行了求解。最后通过一个算例分析，对算法进行了验证。     

路径搜索策略研究

针对城市道路网车辆导航系统中经典Dijkstra最短路径搜索算法中存在的计算效率问题,研究基于启发式策略和双向搜索策略的双向启发式优化搜索算法,并探讨路网的分层搜索策略.采用启发信息减少搜索范围、双向搜索分解搜索空间,从而提高了算法的执行效率.实际路网仿真结果表明:相比经典Dijkstra算法,启发式策略搜索效率可提升70%~80%,双向搜索策略在不损失搜索精度下进一步提高搜索效率5%~10%,而分层搜索策略可以极大提高大规模路网车辆导航长距离下路径搜索效率.