基于模糊规则和BFS算法的行人疏散模型研究

为建立更加真实的行人疏散模型,基于模糊规则和广度优先搜索(BFS)算法,利用元胞自动机,提出1种优化的行人疏散模型。引入动态模糊速度规则,建立移动速度与周边环境的模糊对应关系,从而模拟行人在不同环境下的运动速度;通过设定危险度规则,使用基于双端队列的BFS算法快速计算每个格子距离安全出口的“静态危险度”,并与出口处人群密度的“动态危险度”耦合,使元胞自发地向“总危险度”更低的方向移动;结合动态速度规则建立1种基于排队理论的出口疏散机制。结果表明:所建模型能够再现行人流自组织现象,真实地反应行人不同的移动方式以及疏散的具体过程;模型考虑了出口排队疏散机制对疏散时间的影响,使疏散效率得到提高,为行人疏散模型的建立以及公共场所的设施布局等应急疏散预案提供有效参考。

Research on Knight Covering Based on Breadth First Search Algorithm

This paper introduces the general process of the search algorithm Structure through the knight problem. According to the characteristics of the problem, we detailed discuss the DFS（Depth First Search） algorithm and BFS（Breadth First Search） algorithm, and combine the two algorithms together to solve the knights coverage problem. This article has a good reference for the mixed-use scenarios which requires a variety of search algorithms.

基于ArcGIS管网爆管分析的算法优化与实现

爆管分析在城市管网地理信息系统的建设中具有重要的意义。本文首先分析了ArcGIS网络模型和流向生成,对传统的广度优先算法进行了优化,并在此基础上,完成了上游关闭阀门的搜索和爆管的影响区域分析;然后利用COM技术对爆管分析功能进行封装,实现了该模块的重用。

潮流转移灵敏度以及安全评估指标研究

首先分析潮流转移的原因及伴随的现象。其次讨论潮流转移区域以及区域界定,对传统广度优先遍历(breadth first search,BFS)算法进行改进,提出潮流转移影响区域的界定方法。对安全评估工作的理论基础——3个基本概念(模型量化、平均功率角和潮流转移灵敏度)分别进行定义。提出潮流转移模型及其灵敏度的表达式。提出安全评估的评估方法,建立安全评估的数学模型,最终得到安全评估的综合指标,并阐述了指标的使用。开发潮流转移灵敏度及安全评估程序,利用该程序对真实电网算例进行仿真验证。

城市应急管理GIS模型与算法应用——以广州大学城为例

随着城市建设的快速发展,各类危及国家和人民群众生命财产安全的突发性事故灾害时有发生。因此,为应对城市各种重大突发事件,城市必须建立一种应急机制或综合的应急管理信息系统。管道分析是GIS技术在城市应急管理模型中的具体应用,利用城市应急管理系统对地下网管进行综合管理,可以将管线信息有序的存入计算机管理系统,实现数据的更新和资源共享。本文以广州大学城管道数据为数据研究基础,结合国内外管网数据模型,在先前开发完成的广州大学城可视化平台基础上加入横断面分析、垂距分析和爆管分析三个分析模块,对管网模型进行了算法改进并编程进行了技术实现,这三个功能模块可以直观地让管理员清晰地了解地下管线的走向和它们之间的空间关系,方便管理各种事务,防止和控制突发事件的发生,尽可能地减少灾害的影响范围。这三个功能可以应用于管道设计、铺设、维修等工作,对社会的经济发展和建设起着保障的作用。

广度优先搜索算法在交叉立方体中的应用

给出了互连网络上的广度优先搜索算法，将其应用到交叉立方体上可以得到交叉立方体的广度优先生成树。连通图的广度优先生成树的树高不会超过该图其他同根生成树的高度。利用这一性质，通过分析交叉立方体的广度优先生成树的特征，给出了n维交叉立方体CQ_n的直径为「(n+1)／2」的另外一种证明方法；该算法可以用来求解单源节点最短路径问题。并为讨论新的互连网络拓扑结构的直径和故障直径问题以及单源广播算法提供了一条新的思路。

主机内文档自动搜索技术研究

为降低进行文档搜索时对系统资源的占用,提出了一种实现对主机内文档进行快速高效搜索的方法,采用基于宽度优先非递归搜索算法实现对主机内文档的遍历搜索;采用基于改进的BF算法和改进的KMP算法分别进行文档名和文档关键词匹配;采用降低线程优先级和定时暂停程序的方法控制搜索效率;采用压缩存储的方法对搜索结果进行处理。设计并实现了原型系统,测试结果表明,系统具有较高的准确率和召回率,且对主机内存、CPU、硬盘等资源占用少,降低了在进行文档搜索时对计算机其他进程的影响。

关于AOE网中关键路径求解算法的研究

介绍AOE网中关键路径的相关概念,通过算法描述和实例,探讨基于拓扑排序求解、P矩阵的求解和广度优先搜索遍历(BFS)方法三种算法,求解AOE网中关键路径的实现过程,并进一步从算法的时间复杂度、数据结构形式及实现的容易程度等几方面分析三种求关键路径算法的优劣。

互连网络故障直径的研究

考虑了至多可以删除多少个顶点才能保证互连网络的连通,给出了网络的容错能力。根据Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径。利用广度优先搜索的思想,给出了求任意两个节点之间的n条内部节点互不相交,且在两点间所有路径中是最短的n条路径的算法。该算法为网络故障直径的研究提供了依据。而且,在故障存在但是网络连通的情况下,可以求得网络中任意两节点间的n条最并行路径,提高了网络的容错能力。本文对提出的方法及算法的正确性进行了证明,为研究互连网络的性质提供了新的研究方法。

面向高通量计算机的图算法优化技术

随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构,具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上,BFS算法的优化已取得一系列进展,首先对现有的优化技术进行系统的介绍,并在此基础上提出2种面向高通量计算机的优化手段,通过减少冗余访存和提高缓存局部性,有效提高了算法的访存效率.通过这些优化手段,在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为230的Kronecker图(顶点数为230,边数为234),优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比,单节点具有1.18倍的性能优势.在性能功耗比方面,高通量计算机的结果为181.04 MTEPS W.在2019年6月份的Green Graph500面向大数据集的排行榜上取得第2名的成绩.综上,高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.

基于节点排序的贝叶斯网络结构学习算法

针对K2算法学习贝叶斯网络结构时需要确定节点顺序的问题,提出一种混合贝叶斯网络结构学习算法。在给定数据集的情况下,利用MMPC算法获得网络的初始结构图,应用广度优先搜索的方式对此初始结构图进行搜索,从该图中入度为0的节点出发,按层次依次访问图中的邻接点,获得优化的节点顺序。将该节点顺序作为K2算法的初始节点顺序,再利用K2算法对空间进行搜索,找到全局最优解。实验结果表明,与K2算法和限制性粒子群算法相比,该算法在相同的样本数据集下产生多边、少边和反边情况的概率更低,并且可学习到更准确的贝叶斯网络结构,收敛速度快、求解精度高。

多无人机对组网雷达的协同干扰控制策略研究

本文考虑多架电子战飞机(EWA)对组网雷达系统的协同干扰问题,采用最优化方法建立多EWA协同干扰组网雷达的最优控制模型。求解每架EWA的运动参数,建立多EWA协同干扰控制策略,在组网雷达系统中形成一条或者多条虚拟目标航迹。算法以实现多EWA快速高效工作为目的,即利用最少数量的EWA和最少的协同操作步骤完成对组网雷达的欺骗,在EWA的飞行条件约束以及组网雷达信息下,利用广度优先搜索(BFS)算法和禁忌搜索(TS)算法进行求解。仿真实验分析了所建立模型的合理性,实验结果验证了所提出多EWA协同干扰组网雷达控制策略的可行性和有效性。

大数据环境下基于改进网格单元的DBSCAN算法

近年来,在HDFS上的小文件聚类存储问题引起了广泛关注。针对传统聚类算法DBSCAN在聚类过程中,出现数据密度不均匀时造成聚类效果粗糙及时间开销较大等问题,提出了一种基于经改进网格单元的DBSCAN聚类算法。该算法首先使用网格单元划分及爬山法辨别出局部次优区域来缩小搜索范围,进而再从所选局部次优区域执行宽度优先搜索法,遍历数据点并将其聚类成簇,有效地提高了数据聚类的精确度,显著降低了时间成本。实验结果表明,在数据集较小的情况下,该算法在聚类精度和运行时间上与传统算法接近。当数据集较大时,与传统算法相比,该算法的聚类精度有明显提高,具有更高的时间效率,满足了大数据环境下的小文件处理需求。

基于无线通信的智能火灾疏散系统设计

针对现有的火灾系统无法在陌生复杂情况下实现快速安全疏散的功能,提出了基于广度优先算法的智能火灾疏散系统。该智能火灾疏散系统采用了三级架构,传输基于无线通信技术,利用改进的广度优先搜索算法,实现了楼宇复杂通道智能疏散的功能。针对陌生场所紧急疏散逃生效率低、路线不清晰等问题,采用灯流进行疏散引导,实现智能灯流输出。灯流流向即疏散路径方向,达到快速安全疏散的目的。对设计结构进行3D打印封装、现场测试。测试结果表明,在待机状态下,系统自动进行节点巡检;发生火情时,系统自动计算最佳安全逃生路线,智能规避起火点,并输出相应灯流引导疏散;当地震等非火警紧急情况发生时,可实现一键疏散。

一种高效的最小连通支配集贪心算法

连通支配集(CDS)在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法(GCDS),依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。

ATE开关矩阵最短路径搜索算法

开关矩阵作为信号传递的枢纽,在自动测试设备内部扮演着极其重要的角色。当信号源节点与目标节点之间距离最短时,信号才能最有效地传输。基于开关矩阵的物理模型,结合图论知识,构造了开关矩阵的数学模型。针对通路继电器最少、系统可靠性最高2种情形,把路径最短问题抽象成无权图和有权图的最短路径搜索问题,分别采用广度优先搜索(BFS)算法和Dijkstra算法进行研究,并提出改进型算法。通过具体实例,建立模型并应用改进算法予以实现。改进算法应用于ATE通用适配器的开发研制和自动测试设备软件平台的设计,可实现最佳测试路径的快速自动搜索,具有工程实践价值。