基于图论分区与改进BFS算法搜索安全约束集的防联锁过载控制策略 被引量：21

1

作者 李刚 王增平 +1 位作者 任建文 闫利伟 《电工技术学报》 EI CSCD 北大核心 2012年第11期219-229,共11页

当采取紧急控制措施消除过载时,要避免系统中出现新的过载。本文引入安全约束集(SCS)的概念;提出了一种基于图论分区与改进广度优先搜索(BFS)算法求SCS的方法。首先基于改进的Dijkstra算法将电网分区,形成广义电网拓扑图(GGT);然后采用... 当采取紧急控制措施消除过载时,要避免系统中出现新的过载。本文引入安全约束集(SCS)的概念;提出了一种基于图论分区与改进广度优先搜索(BFS)算法求SCS的方法。首先基于改进的Dijkstra算法将电网分区,形成广义电网拓扑图(GGT);然后采用改进的BFS算法快速搜索广义控制点(GCN)附近区域的广义节点(GN),由这些GN内的支路和接近热极限的支路组成SCS,扩展了正常支路约束集的范围。给出了结合SCS的控制点的选取方法和控制量的确定方法。提出了基于决策中心-区域终端(DC-RT)模式的防联锁过载控制策略。将每个GN作为一个RT,当发生过载时,各RT并行计算保证SCS内支路不过载的最大安全控制量,节省了计算时间,提高了控制速度。最后采用CEPRI 36节点系统仿真验证了该控制策略的有效性。 展开更多

关键词 安全约束集 广义电网拓扑图 广义节点 迪杰斯特拉 广度优先搜索 大停电联 锁过载

下载PDF 职称材料

一种SRIO网络负载均衡最短路径路由算法 被引量：12

2

作者 李嘉伟 张激 +1 位作者 赵俊才 丁如艺 《计算机工程》 CAS CSCD 北大核心 2020年第3期214-221,228,共9页

在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓... 在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息,以路由跳数定义路由的成本,根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载,采用负载均衡算法从K最短路径中进行选路,建立SRIO网络最短路径约束的负载均衡路由。实验结果表明,与深度遍历路由算法、最小跳数算法相比,该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现,能够有效提升SRIO路由网络的稳定性。 展开更多

关键词 负载均衡 动态规划 串行高速输入-输出 广度优先搜索 K最短路径

下载PDF 职称材料

面向高通量计算机的图算法优化技术 被引量：10

3

作者 张承龙 曹华伟 +4 位作者 王国波 郝沁汾 张洋 叶笑春 范东睿 《计算机研究与发展》 EI CSCD 北大核心 2020年第6期1152-1163,共12页

随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核... 随着互联网技术的蓬勃发展,图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法,也是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名的成绩.综上,高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用. 展开更多

关键词 宽度优先搜索 高通量 Graph500 图算法 超算

下载PDF 职称材料

基于节点排序的贝叶斯网络结构学习算法 被引量：7

4

作者 姚洁 朱响斌 +2 位作者 宋新方 李广龙 邱慧玲 《计算机工程》 CAS CSCD 北大核心 2017年第5期317-321,共5页

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

关键词 贝叶斯网络 结构学习 MMPC算法 K2算法 广度优先搜索

下载PDF 职称材料

基于GIS的多水源环状管网爆管分析的算法 被引量：6

5

作者 王杉杉 骆旭佳 +1 位作者 高飞 胡小华 《水科学与工程技术》 2010年第4期43-46,共4页

对复杂多变的城市地下供水管网进行网络建模分析,在此基础上结合计算机和GIS技术,研究了爆管事故发生后如何快速准确地制定最佳的关阀方案,以便指导抢修工作的顺利开展。这种结合实际管网现状,建立和分析网络逻辑模型,以事故点出发,按... 对复杂多变的城市地下供水管网进行网络建模分析,在此基础上结合计算机和GIS技术,研究了爆管事故发生后如何快速准确地制定最佳的关阀方案,以便指导抢修工作的顺利开展。这种结合实际管网现状,建立和分析网络逻辑模型,以事故点出发,按照一定的法则,寻求优化方法,并制定最优化实施方案的算法,也可推广到其他管道、线路管理系统中。 展开更多

关键词 地理信息系统 广序遍历 爆管分析 多水源 优化

下载PDF 职称材料

基于最优子网的虚拟网络映射算法 被引量：5

6

作者 朱国晖 康潇轩 雷兰洁 《计算机工程》 CAS CSCD 北大核心 2019年第10期8-12,共5页

针对在虚拟网络映射过程中物理资源碎片化导致嵌入请求被拒绝,从而降低物理资源利用率的问题,提出一种基于最优子网的虚拟网络映射算法,通过优化的重边匹配算法,合并符合约束条件的虚拟节点,同时粗化网络拓扑,运用广度优先搜索算法创建... 针对在虚拟网络映射过程中物理资源碎片化导致嵌入请求被拒绝,从而降低物理资源利用率的问题,提出一种基于最优子网的虚拟网络映射算法,通过优化的重边匹配算法,合并符合约束条件的虚拟节点,同时粗化网络拓扑,运用广度优先搜索算法创建候选物理子网集合,将粗化后的虚拟网络请求映射至最优子网。仿真结果表明,该算法能够减小链路映射跳数,提升虚拟网络请求接受率和收益开销比。 展开更多

关键词 虚拟网络映射 资源碎片化 最优子网 重边匹配 网络拓扑粗化 广度优先搜索

下载PDF 职称材料

基于BFS的DAIS DA客户端数据浏览算法

7

作者 冯浩 吴健 《计算机工程与应用》 CSCD 北大核心 2009年第12期246-248,共3页

在工业生产自动化领域推广应用OMGDAIS新标准的过程中,碰到的一个基本但标准文档本身又未加阐述的问题是:如何从兼容DA标准的服务程序浏览数据。针对此问题,在简要介绍标准数据模型及其API的基础上,利用广度优先搜索思想,给出了解决方法... 在工业生产自动化领域推广应用OMGDAIS新标准的过程中,碰到的一个基本但标准文档本身又未加阐述的问题是:如何从兼容DA标准的服务程序浏览数据。针对此问题,在简要介绍标准数据模型及其API的基础上,利用广度优先搜索思想,给出了解决方法,详细描述了相应算法,并分析了算法的复杂度。算法的实现程序访问一个兼容标准的电力数据交换服务,成功获取了预期数据,表明算法是可行且完全通用的。 展开更多

关键词 工业系统数据获取标准中的数据存取 广度优先搜索 数据浏览 IEC 61970

下载PDF 职称材料

潮流转移灵敏度以及安全评估指标研究 被引量：21

8

作者 闫常友 周孝信 +2 位作者 康建东 田芳 严剑峰 《中国电机工程学报》 EI CSCD 北大核心 2010年第19期7-13,共7页

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

关键词 潮流转移 潮流转移灵敏度 安全评估指标 改进广度优先遍历算法 潮流转移区域界定 模型量化 平均功率角

下载PDF 职称材料

基于ArcGIS管网爆管分析的算法优化与实现 被引量：18

9

作者 刘建川 李永树 蔡国林 《测绘科学》 CSCD 北大核心 2008年第1期215-217,共3页

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

关键词 ARCGIS 爆管分析 网络模型 广度优先算法 COM

下载PDF 职称材料

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

10

作者 陈颖彪 陈健飞 苏琪信 《地球信息科学》 CSCD 北大核心 2009年第1期62-69,共8页

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

关键词 城市应急管理 横断面分析 垂距分析 爆管分析 广度优先算法

下载PDF 职称材料

一种启发式舰船电力网络拓扑分析方法 被引量：8

11

作者 黄靖 张晓锋 蒋心怡 《电力系统及其自动化学报》 CSCD 北大核心 2008年第2期110-116,共7页

快速有效地跟踪网络拓扑对于实现舰船配电管理自动化至关重要。针对传统拓扑分析方法效率低、耗时多的缺点,提出将广度优先和启发式搜索技术相结合的舰船电力网络拓扑快速跟踪新方法。该方法基于面向对象技术构造了符合舰船电力网络特... 快速有效地跟踪网络拓扑对于实现舰船配电管理自动化至关重要。针对传统拓扑分析方法效率低、耗时多的缺点,提出将广度优先和启发式搜索技术相结合的舰船电力网络拓扑快速跟踪新方法。该方法基于面向对象技术构造了符合舰船电力网络特点的拓扑模型,利用节点和支路模型的双向关联关系描述电网拓扑结构。基于广度优先搜索对初始网络进行遍历,实现了支路类型识别和网络静态分区,并在此基础上,针对不同类支路状态变化,采用启发式规则更新局部网络拓扑,从而实现了电网拓扑的快速跟踪。对典型舰船电力网络的拓扑分析结果表明,该方法具有较好的实时性,相对于传统方法有效率更高。 展开更多

关键词 舰船电力系统 网络拓扑 广度优先搜索 启发式搜索

下载PDF 职称材料

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

12

作者 何嘉 奚峥皓 +2 位作者 阚秀 王汉东 沈颉 《传感器与微系统》 CSCD 北大核心 2021年第7期48-51,59,共5页

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

关键词 组网雷达 协同干扰 最优化模型 广度优先搜索(bfs)算法 禁忌搜索(TS)算法

下载PDF 职称材料

BFS算法与众核处理器的适应性研究 被引量：7

13

作者 叶楠 郝子宇 +1 位作者 郑方 谢向辉 《计算机研究与发展》 EI CSCD 北大核心 2015年第5期1187-1197,共11页

以图计算为代表的数据密集型应用获得越来越广泛的关注,而传统的高性能计算机处理这类应用的效率较低.面向未来高性能计算机体系结构要有效支持数据密集型计算,深入研究以广度优先搜索(breadth-first search,BFS)算法为代表的图计算的... 以图计算为代表的数据密集型应用获得越来越广泛的关注,而传统的高性能计算机处理这类应用的效率较低.面向未来高性能计算机体系结构要有效支持数据密集型计算,深入研究以广度优先搜索(breadth-first search,BFS)算法为代表的图计算的典型特征,设计实现轻量级启发式切换BFS算法,该算法通过基本搜索方式的自动切换,避免冗余内存访问,提高搜索效率;针对BFS算法的离散随机数据访问特征以及众核处理器执行机制,建立面向BFS算法的众核处理器体系结构分析模型;全面、深入研究了BFS算法在典型众核处理器上的运行特征和性能变化趋势.测试结果表明:Cache命中率、内存带宽、流水线利用效率等相关参数均处于较低水平,无法完全满足BFS算法的需求,因此需要能够支持大量离散随机访问和简单执行机制的新型众核处理器体系结构. 展开更多

关键词 广度优先搜索算法 众核处理器 体系结构 分析模型 协同研究

下载PDF 职称材料

基于模糊规则和BFS算法的行人疏散模型研究 被引量：5

14

作者 翟龙真 冯绍红 +1 位作者 文哲 王迪 《中国安全生产科学技术》 CAS CSCD 北大核心 2021年第3期5-11,共7页

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

关键词 行人疏散模型 模糊规则 广度优先搜索算法(bfs) 元胞自动机

下载PDF 职称材料

一种基于广度优先搜索的社区发现方法 被引量：5

15

作者 陈东明 徐晓伟 《东北大学学报（自然科学版）》 EI CAS CSCD 北大核心 2010年第3期346-349,共4页

由于当前的算法不能很好地将网络的联通性和单个节点的属性综合考虑,分析了凝聚和分裂层次聚类经典算法的局限性,从而给出边的载荷、边的权重、连接度门限、图形分割等定义.综合考虑网络的拓扑结构和边的权重关系,提出了基于广度优先搜... 由于当前的算法不能很好地将网络的联通性和单个节点的属性综合考虑,分析了凝聚和分裂层次聚类经典算法的局限性,从而给出边的载荷、边的权重、连接度门限、图形分割等定义.综合考虑网络的拓扑结构和边的权重关系,提出了基于广度优先搜索的社会网络社区发现算法SoNetCD.算法通过删除社区之间的边而得到社区结构,它对社区之间的边判断准确,对社区内部的边误删率低.运用经典数据集进行实验的结果表明,该算法具有比经典GN算法更好的结果. 展开更多

关键词 社会网络 社区发现 广度优先搜索 聚类 模块化

下载PDF 职称材料

模型驱动的全景图技术在电网运行驾驶舱中的应用 被引量：4

16

作者 何伊妮 曹伟 +2 位作者 顾礼斌 唐羿轩 李勇刚 《电气自动化》 2018年第4期36-39,共4页

电力系统运行驾驶舱是一体化电网运行智能系统的顶层应用和人机交互入口,通过运行服务总线获取基础资源平台的数据和应用支持,采用态势感知(Situation Awareness,SA)和任务导向技术,提供全面反映电网关键运行状态、预测和控制关键运行... 电力系统运行驾驶舱是一体化电网运行智能系统的顶层应用和人机交互入口,通过运行服务总线获取基础资源平台的数据和应用支持,采用态势感知(Situation Awareness,SA)和任务导向技术,提供全面反映电网关键运行状态、预测和控制关键运行风险的"一站式"解决方案。目前驾驶舱中的决策视图是事先构造,不能动态生成,但电网运行决策具有主题的广泛性和视图的不确定性,驾驶舱静态预制显然无法更好地满足决策需要。利用广度优先方法,实现对大规模电网模型的分层抽象计算,形成规格化的空间点线模型,借助自动布局与布线技术,自动生成电网多侧面全景视图以及与应用相对应的主题视图,融合了电网的宏观与微观决策视野,较好地满足了电力系统运行驾驶舱的需求。 展开更多

关键词 电力系统运行驾驶舱(POC) CIM模型 广度优先搜索法(bfs) 模型抽象与压缩 自动成图

下载PDF 职称材料

基于无线通信的智能火灾疏散系统设计 被引量：4

17

作者 窦杰 周琪璋 +3 位作者 宋道榜 陈镇生 张海龙 曹鹏飞 《无线电工程》 2018年第5期347-351,共5页

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

关键词 无线通信 三级架构 智能疏散 广度优先搜索算法(bfs)

下载PDF 职称材料

大数据环境下基于改进网格单元的DBSCAN算法 被引量：4

18

作者 杨旭辉 张帆 胡涛 《信息工程大学学报》 2021年第3期351-358,共8页

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

关键词 聚类 密度 网格单元 爬山法 宽度优先搜索

下载PDF 职称材料

基于广度优先搜索的局部社区发现算法 被引量：4

19

作者 王豫中 范磊 李建华 《计算机工程》 CAS CSCD 北大核心 2015年第10期37-41,共5页

局部社区发现是网络拓扑研究中的热点,从起始节点的最大结合性节点出发,提出一个基于给定节点的局部社区发现算法。对整个社区进行广度优先搜索(BFS),从起始节点开始找到最大结合性节点,基于节点相似度(共同好友数目)并且利用BFS进行社... 局部社区发现是网络拓扑研究中的热点,从起始节点的最大结合性节点出发,提出一个基于给定节点的局部社区发现算法。对整个社区进行广度优先搜索(BFS),从起始节点开始找到最大结合性节点,基于节点相似度(共同好友数目)并且利用BFS进行社区发现,对所发现的社区进行剪枝策略,从而得到起始节点所在的局部社团。实验结果证明,该算法在不降低精度的前提下,时间复杂度为O(kd3)。 展开更多

关键词 最大结合性 共同好友数 节点相似度 广度优先搜索 局部社区发现

下载PDF 职称材料

基于双向广度优先搜索的魔力方块问题求解 被引量：3

20

作者 王桂平 张帅 《计算机工程》 CAS CSCD 北大核心 2011年第20期219-222,共4页

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

关键词 魔力方块问题 状态判重 状态转换表 双向广度优先搜索 八数码问题

下载PDF 职称材料