K则最短路径算法效率与精度评估

精度和效率是决定最短路径算法实用价值的重要依据。对于K则最短路径问题,各种理论严密算法和有损算法的实用性分析是目前研究的薄弱环节。理论严密算法的实际运行效率比较及其有损算法的精度损耗与效率提高幅度的定量化一直未得到深入研究。针对这一问题,在对K则最短路径算法进行系统分类的基础上,分析了各种经典的理论严密算法和精度有损算法的特征与时间复杂度,结合实际城市路网数据对各种K则最短路径算法的运行效率和精度进行了测试和比较。结果显示,与有损算法相比,理论严密的K则最短路径算法普遍缺乏实用性,只有多重标号算法适合于某些要求精度无损的应用;而一些有损K则最短路径算法以较小的精度损失换取了较大幅度的效率提高,尤以双向搜索算法最具应用推广价值。

超大型油轮降噪设计主传递路径族灵敏度方法

针对振动噪声传递路径降噪设计是提高船舶声学性能的有效措施之一。目标舱室振动噪声传递路径并不唯一,其中多条主要路径传递了大部分振动与噪声能量。利用作者提出的基于声振熵概念及图论中K则最短路径理论的声振熵赋权图法,能够快速识别船舶舱室噪声主要传递路径族。在此基础上,计算噪声主传递路径族上声学设计参数变化对目标舱室声压影响的灵敏度,调整有关声学设计措施,此即降噪设计主传递路径族灵敏度方法。提出适用于大型船舶噪声主传递路径分析及主传递路径族灵敏度的降噪设计通用流程,通过超大型油轮降噪声学设计实例,说明了该方法的有效性。

电力系统连锁故障快速风险评估模型研究

为了提高电力系统连锁故障风险评估的快速性,解决现有模型难以实现在线应用的问题,提出了一种基于危险支路集的快速评估模型。该模型利用双向搜索算法搜索出开断支路两端点间的前K则最短路径,以确定支路开断后潮流转移的范围;综合考虑支路潮流增量、潮流越限程度两方面因素定义了危险支路判据,以便在前K则最短路径的基础上快速识别易引起连锁故障的支路,确定下一步安全分析的对象。通过上述两步骤缩小了每一故障环节的安全分析范围,提高了整体的风险评估速度。IEEE 39节点系统的仿真实例证明该模型具有较快的风险评估速度以及较高的评估精度,易于实现在线应用。

基于车牌识别数据的机动车出行轨迹提取算法

为了提取城市路网上所有运行车辆的出行轨迹,系统科学地再现所有车辆的运行场景,进而为分析城市交通需求的结构和时空分布特性提供数据支撑,提出基于车牌识别数据的机动车出行轨迹提取算法.通过车牌及时间戳排序提取出行链;利用相邻节点间的速度,结合交叉口邻接矩阵完成行链的分离;基于K则最短路径算法(KSP算法)及灰色关联法(GRA算法),对出行轨迹进行补全重构.对贵阳市南明区的实际车牌识别数据进行算法测试.结果表明,提出的基于车牌识别数据的机动车出行轨迹提取算法在测试区域的综合准确率大于92%.

面向矿井突水避险的双向搜索多最优路径算法

为节省煤矿水灾状况下的逃生时间,提高应急救援效率,在传统的Dijkstra算法基础上提出一种基于双向搜索的K则最短路径算法.首先综合考虑煤矿特殊巷道分布,提出井巷长度当量权值,然后利用灰色理论模型预测特定时间段内每条巷道的人流量,进而根据人流量对行走速度的影响关系式得到每条巷道的通行时间值,最终通过双方搜索策略改进算法,实现事故点到逃生井口的多条最佳逃生路线.根据井下巷道拓扑结构提取构建一个无向带权网络图,在MATLAB环境下利用上述优化算法进行仿真验证.结果显示,该改进算法具有更好的准确率和实用性.