城市公交查询系统的设计与实现

针对含有“公汽、地铁、步行”的复杂公交网络环境,首先对公交问题所提供的数据进行分析,并优化数据的存储结构;其次充分考虑到公交网络客流分配的主要因素一换乘次数、票价、时间,提出了公交网中这三个目标的加权平均最优路径模型及其算法;最后对模型的算法用Matlab软件实现.通过测试,结果显示本系统能快速响应出满足乘客不同需求的公交出行路径。     

An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions

We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(nlog n) time and requires O(nlog n) space, where n is the number of edges of P. The algorithm is based on the O(nlog n) algorithm of Hershberger and Suri for shortest paths in the plane (Hershberger, J., Suri, S. in SIAM J. Comput. 28(6):2215–2256, 1999), and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront” from s along ∂ P. This is effected by generalizing the concept of conforming subdivision of the free space introduced by Hershberger and Suri and by adapting it for the case of a convex polytope in ℝ³, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision. The algorithm constructs a dynamic version of Mount’s data structure (Mount, D.M. in Discrete Comput. Geom. 2:153–174, 1987) that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path can be reported in additional O(k) time, where k is the number of polytope edges crossed by the path. The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n+m)log (n+m)), so that the site closest to a query point can be reported in time O(log (n+m)). Work on this paper was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the U.S.-Israeli Binational Science Foundation, by grant 155/05 from the Israel Science Fund, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. The paper is based on the Ph.D. Thesis of the first author, supervised by the second author. A preliminary version has been presented in Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 30–39, 2006.     

改进Dijkstra算法在嵌入式GIS系统中的应用研究

针对嵌入式GIS系统的特点对经典Dijkstra算法进行优化处理. 分两步以提高算法效率, 第一步采用椭圆限制区域算法来缩小算法的搜索范围; 第二步为每个结点添加属性值、增加前趋表, 以辅助算法快速找到一条最短路径. 最后将此算法应用到嵌入式GIS系统中, 测试结果表明: 在城市道路网络中, 改进的算法大大提高了嵌入式GIS系统的效率.     

DWDM波长路由网络光链路负载均衡的波长路由算法

提出了一种应用于密集波分复用(DWDM)波长路由网络(WRON)中光链路负荷均衡的思想,并将其应用于优化Dijkstra算法的权值,同时将优化Dijkstra算法用于遗传算法求得了在不同的负荷条件下波长下限的网络所需波长数目。并将优化前后的算法分别对美国自然科学基金(NSF)网络的最优波长分配进行数值分析,发现基于负荷均衡思想的优化Dijkstra算法能够对网络的性能有很大提高：当遗传代数为20代时,采用优化Dijkstra算法阻塞率降低了约36％;当波长使用数为7个时,降低网络阻塞率10％。     

基于改进蚁群算法的机器人路径规划

采用MAKLINK图论建立机器人路径规划的空间模型,利用Dijkstra算法减少工作空间的搜索范围,引入免疫算子,将其融合到蚁群算法的每次迭代过程中,提高蚁群算法在全局搜索空间的遍历性和收敛速率,避免陷入局部最优解。     

基于Dijkstra算法的电力光通信网络智能运维设备脱网故障区段定位方法

智能运维设备发生脱网故障后，往往难以定位，为实现脱网故障区段与故障电流分布间映射关系的确定、寻找脱网故障区段与故障电流分布间映射关系的最短路径，设计一种基于Dijkstra算法的电力光通信网络智能运维设备脱网故障区段定位方法。选择数据驱动方法中的LightGBM算法，通过大量样本确定离网故障区段与故障电流分布之间的映射关系。基于Dijkstra算法寻找映射关系的最短路径，实施脱网故障区段搜索。设计电力光通信网络智能运维设备脱网故障区段定位平台，实现脱网故障点即智能运维设备信号丢失的定位与告警。对比实验显示，在SDH环网电路区域中的光缆中断导致的脱网故障区段定位、多路由段的光缆故障下的脱网故障区段定位，以及在环状电力区域中的多路由段的光缆故障下的脱网故障区段定位场景中，该方法的定位结果与实际位置最贴近，定位最准确。