有向网络上两顶点间最短路径的双向搜索算法

提出了一种求解有向网络上两顶点间最短路径的双向搜索算法，经理论证明和实际应用。

基于改进双向峰-谷搜索算法的煤矸模型电磁波正演模拟

实现放顶煤过程煤矸含量自动识别是综采自动化的重要目标,现有煤矸含量自动识别方法存在准确性、实时性较低等问题。放顶煤过程产生的煤矸混合物是由煤、矸石和空气形成的三相介质,各相介质的电性参数不同,在不同组分的混合三相介质中,电磁波的传播特性也不同。煤和矸石相对介电常数差异明显,通过研究不同含矸率煤矸混合物的电性参数,可为放顶煤工作面含矸率自动识别提供新的思路和方法。为了探究不同含矸率煤矸混合物的电性差异,提出了一种基于分治策略的双向峰-谷搜索算法,基于该算法建立了煤矸多相离散随机介质模型,基于麦克斯韦方程组及其本构关系方程,利用时域有限差分法对所建立的模型进行电磁波正演模拟。分析表明,基于分治策略改进双向峰-谷搜索算法后,煤矸多相离散随机介质模型中的煤、矸石、空气三相之间不仅存在明显的相界面,且各相离散程度更大,不存在聚集现象,因此局部介质也能体现整体的电性参数,能够满足电磁波正演的介质模型需求。正演模拟结果表明:(1)激励信号的频率会影响透射波的幅值,在12 GHz范围内,激励信号频率越高,透射波幅值越大;频率过低会降低信号的鲁棒性,激励频率应高于2 GHz。(2)煤矸混合物的含矸率与介质整体的等效介电常数呈正相关。含矸率越高,电磁波信号的传播损耗越多,接收平面接收到的信号幅值越小,电磁波信号穿透介质所用的时间越长。不同含矸率之间呈现明显的差异性,可以用作综采放顶煤含矸率识别的依据。

改进的双向启发式搜索算法及其在车载导航仪中的应用

介绍单车辆路径规划的有关算法，针对车载导航仪的应用，对双向启发式搜索算法进行了改进和优化，提出了可靠有效的搜索终止条件和搜索切换标准，给出了改进算法的流程。最后给出了四种算法的实际测试和比较结果。结果表明改进的双向启发式搜索算法快速高效。

基于Viterbi-双向搜索的咬尾码最大似然译码算法

传统咬尾码最大似然(ML)译码算法在译码时存在两个问题:复杂度高和消耗存储空间大。针对这两个问题,该文提出了一种基于Viterbi算法和双向搜索算法的最大似然译码算法。新算法利用Viterbi算法得到的幸存路径度量值与最大似然咬尾路径度量值的关系,删除不可能的起始状态及其对应的咬尾格形子图,缩小搜索空间;然后利用双向搜索算法中门限值与最大似然咬尾路径度量值的关系来降低双向搜索算法的复杂度,从而得到一种在咬尾格形图上高效率的最大似然译码算法。新的最大似然译码算法不仅降低了译码复杂度,同时降低了译码器对存储空间的需求。

网络最短路径定界搜索算法

用Dijkstra算法求解大规模网络两顶点间最短路径时,需计算大量与最短路径无关的顶点,效率较低.双向定界搜索算法是首先对网络进行双向搜索,得到一条经任意点的最短路径.一般情况下,这条路径已非常接近、甚至等于最短路径.然后,以此路径的标号(即路径长)作为搜索计算的界,进行双向标号计算,对超过界的顶点不再计算,以提高计算效率.算法分析表明,用该算法可使计算效率提高约一倍.

双层框架可视图下的双向跳点路径规划方法

针对移动机器人在复杂未知半未知环境下路径规划时间过长,难以找到全局最优路径的问题,该文提出了一种基于双层框架可视图的双向跳点搜索路径规划方法。首先,将可视图分为局部层和全局层,移动机器人通过传感器对环境信息进行采集与提取,生成局部可视图,接着采用基于障碍物轮廓边长的过滤方法将过滤后的图更新至全局可视图;其次,在跳点搜索算法的基础上新增一个从目标点开始搜索的路径,将跳点搜索算法优化为双向跳点搜索算法;最后,将优化后的算法结合可视图进行路径规划导航。将所提方法在多种复杂场景下进行验证,仿真实验表明:采用了双层框架可视图的双向跳点搜索算法的路径搜索时间和导航时间均有着不同程度的优化,可高效地在复杂未知环境下搜索全局路径。

基于分层分块数据组织的双向A^＊算法

研究了路网的数据组织方法,采用了C++STL实现道路数据的分层分块存储,设计了道路网络分析中的双向A*算法,试验验证了其正确性。

基于改进燃烧算法的最优路径规划

针对燃烧算法在公交查询系统中求解最优路径问题的不足,以及为了更好地服务于乘客,对燃烧算法中的存储结构进行改进和优化,采用新的搜索思想并设置算法终止判断条件,提出了基于公交站点的双向燃烧搜索算法。仿真结果表明,该算法在时间、空间代价以及准确性方面均具有显著的优越性。

基于物联网的智能交通系统车辆路径规划算法优化研究

本文提出了适用于智能交通系统的基于双向搜索的改进算法。典型的最短路径算法被认为是Dijkstra算法,其时间复杂度是O(n2)。但一个城市的路网地图有很多节点,该算法的时间复杂度高和解决速度慢。为了改变这种情况,我们从算法的设计方面进行了讨论,提出了改进的双向搜索算法。实践证明,改进后的算法能够提高了搜索速度,适用于智能交通系统。

对K则最短路径若干算法的探讨

最短路径问题应用极其普遍,尤其是在一些抢险救灾活动中,它的价值就更显得突出了,而K则最短路径则是在最短路径上的延伸,意思就是在最短路径不适宜时,有多条备选路径可供选择。文中重点介绍了K则最优路径的去边算法、邻近点算法、稀疏矩阵算法和双向搜索四种算法的计算原理,最后结合简单的网络图加以验证。

基于双向搜索的运输路线优化算法

研究提出了基于有向图关联矩阵的双向搜索算法。此算法用于运输路线的优化计算,其基本过程为:首先分析路径和节点的拓扑关系,建立运输路线的有向图,然后简化有向图构建其顶点和边的关联矩阵,在关联矩阵的基础上从起点和终点分别查找出度和入度,通过双向搜索以快速查找出需要的最短路径。

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

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

光伏阵列图像阴影去除方法

为解决阴影对光伏阵列航拍图像识别问题的影响,对光伏阵列图像阴影去除方法进行了研究。首先基于用户输入笔画构造K最邻近(KNN)分类器对像素进行分类,并采用大津法(OTSU)检测出阴影;然后应用双向搜索算法确定每条采样线的位置,并根据采样线长度以及基于密度的聚类算法(DBSCAN)将异常采样线剔除;最后通过阴影比例估计与光照恢复去除阴影。与叠加法和YCbCr通道法进行对比实验,结果表明,该算法阴影去除质量的各项性能指标均优于另外两种算法,且阴影去除后的图像颜色、纹理等信息保留较完整,可得到更加自然的无阴影图像。

嵌入式导航系统中路径分析的优化

由于嵌入式计算机受到硬件资源的限制,特别是芯片速度的限制,若在车载导航系统中采用通用算法进行路径分析,则会使得分析很低效,耗时很长,尤其对大跨度,更加难以忍受。针对该问题,提出了3个优化路经分析的方法,即分层分析方法、经验数据方法和优化搜索算法,并给出了双向搜索算法和使用启发信息的方法。通过实验证实了这几种方法能有效地提高路径分析速度,大大提高嵌入式导航产品的实用性。

浮动车数据挖掘及其在路径规划中的应用

公交车路径规划的传统方法主要依靠人力调查,在这期间花费了大量的人力和物力,且不适应城市快速发展导致的路网频繁变化。针对这种情况,根据收集到的巨量出租车GPS数据,提出一种夜间公交车路径规划方法。在提取有效轨迹数据的基础上,找出聚集区确定候选车站集,设定规则把复杂的候选车站集简化为有效公交车路线集,选取最理想的一条。实验结果表明,双向相关性启发式搜索算法得到的路径综合考虑候选车站间的相关性,是在规定时间内载客量最多的路径。

Layered heuristic algorithm for multiple restriction routes

A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.

部队铁路输送路径选择算法研究

根据部队铁路输送要求和铁路路网特点,设计了基于辅助信息的双向A*路径搜索算法,采用二次读入边数据方法表示路网,利用前向关联边存储结构存储路网,应用经验知识限制算法的搜索区域,通过使用常量系数β提高了启发函数的信息性。实验结果表明,算法的改进是有效和实用的。