基于双向广度优先搜索的魔力方块问题求解

将魔力方块问题与八数码问题进行对比分析,通过讨论魔力方块问题是否有解、解的最少步数、状态表示、状态判重、状态转换关系等相关问题,提出一种基于双向广度优先搜索和状态转换表的求解算法。实验结果表明,与有界深度优先搜索、简单广度优先搜索及A*搜索算法相比,该算法效率较高,稳定性较好,可以实现魔力方块问题的实时求解及演示。

基于双向广度优先搜索的配电网可靠性评估

配电网是电力系统与用电客户的连接环节,对配电网进行可靠性评估,可以发现配电网的薄弱环节,为电网的维护提供重要信息。针对配电网负荷点密集、计算量大的特点,文章应用双向广度优先搜索方法进行最小路的搜索。该方法具有搜索快、用时短、准确性高的优点,通过C++实现程序设计,使得整个配电网可靠性评估过程迅速且准确进行。对某配电网实例进行可靠性评估,得到了与传统方法相同的结果,并且速度较快。算例结果表明基于双向广度优先搜索的配电网可靠性评估方法是有效的。

基于双向广度优先法的输电断面搜索方法

为了快速、精准、完整地搜索出受潮流转移影响较大的支路组成的输电断面,采用了基于图论中改进的双向广度优先搜索算法。该方法首先以加权邻接矩阵表示电力网络,然后根据改进的双向广度优先法搜索得到开断节点间前K最短路径,通过计算路径中支路的开断分布因子选取初始输电断面,进一步计算初始输电断面的暂态稳定安全裕度筛选出关键输电断面,以此代替对全网的安全性分析,大大缩减了计算量,为后续过载控制策略争取了时间,对防止连锁过载跳闸意义重大。对IEEE39节点系统的案例仿真分析,验证了该算法的可行性和准确性。

四种最短路径算法实例分析

通过理论分析,结合实际应用,在GIS节点数很大的数字地形图中,从完备性、最优性、时间复杂度、空间复杂度几种性能问题实例分析,较系统地总结出深度优先搜索(DFS)、广度优先搜索(BFS)、双向广度优先搜索(DBFS)、A★算法四种算法代价及优缺点.

基于备选路径集的在线最短耗时公交换乘方法

面向城市公交出行者,在给定出行起讫点及起始时间的情况下,提出一种基于备选路径集的在线最短耗时公交换乘方法:在预处理阶段离线地运用双向广度优先搜索方法得到点对之间的静态备选路径集;结合实时公交到站时间预测数据或发车间隔等静态的公交运营数据,进行最短耗时评估,在线地从中选择耗时最短的路径。将该方法运用于沈阳公交路网案例中(公交到站时间预测数据仿真生成),并嵌入沈阳市公交出行查询系统,结果表明了其实用性。