题名 图广度优先遍历算法的形式化推导与机械验证方法
1
作者
余楚凌 曹中雄 王唱唱 王昌晶
机构
江西师范大学计算机信息工程学院 江西师范大学数字产业学院 江西师范大学管理科学与工程研究中心
出处
《江西师范大学学报(自然科学版)》
北大核心
2024年第5期472-478,共7页
基金
江西省教育厅科学技术研究重点课题(GJJ220302,GJJ210307,GJJ2200303,GJJ220304)资助项目.
文摘
针对图广度优先遍历问题,该文提出了一种形式化推导与机械验证方法.首先,描述求解问题的形式化规约,使用分划递推得到统一的循环不变式并开发相应的Apla抽象程序;然后,在Isabelle中描述算法相关的数据类型、定义与基本函数,根据算法程序正确性证明的验证条件证明了抽象算法正确性;最后,通过Apla→C++自动生成器生成可执行代码,验证了该方法的有效性.
关键词
图广度优先遍历 形式化推导 定理证明 循环不变式
Keywords
graph breadth-first traversal formal derivation theorem proving loop invariant
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
题名 基于广度优先遍历的关键路线生成树算法
被引量：1
2
作者
付冬梅 练丁榑
机构
北京科技大学自动化学院
出处
《计算机科学与应用》
2012年第2期51-56,共6页
基金
北京市教育委员会重点学科共建项目资助(xk100080537)。
文摘
关键路线的确定对于运用关键路线法进行项目管理具有十分重要的意义。本文首先定义了项目管理图模型,然后在此基础上提出了一种基于广度优先遍历的关键路线生成树算法,最后通过对项目管理图模型的研究,实现了对算法的优化。仿真结果表明,该算法能够生成一棵保留根节点到任意节点最大路径信息的树,通过生成的树能够方便地确定关键路线。
关键词
项目管理图模型 生成树 关键路线 广度优先遍历
分类号
F2
[经济管理—国民经济]
题名 基于蜂群和广度优先遍历的PPI网络聚类
被引量：4
3
作者
田建芳 雷秀娟
机构
陕西师范大学计算机科学学院
出处
《模式识别与人工智能》
EI
CSCD
北大核心
2012年第3期481-490,共10页
基金
国家自然科学基金项目(No.61100164) 陕西省自然科学基础研究计划项目(No.2010JQ8034) 中央高校基本科研业务费专项项目(No.GK200902016)资助
文摘
蛋白质交互作用(PPI)网络聚类算法是研究和揭示蛋白质功能的主要方法之一.由于PPI网络的特性,传统算法不能有效聚类.文中提出一种基于蜂群和广度优先遍历的聚类算法.为避免噪声点对实验结果的干扰,在预处理阶段利用距离-密度算法确定聚类个数,剔除噪声点.然后利用结点网络综合特征值确定初始聚类中心,利用广度优先遍历搜索算法进行聚类.再采用改进的蜂群算法自动寻找最优合并阈值.最后用正确率和查全率对该算法进行性能评价并对算法中一些重要参数进行仿真分析,仿真结果表明该聚类算法有效提高PPI网络的聚类效果.
关键词
蛋白质交互作用(PPI)网络 聚类 蜂群算法 广度优先遍历 (BFT)
Keywords
Protein-Protein Interaction （PPI） Network, Clustering, Artificial Bee Colony Algorithm,Breadth First Traverse （BFT）
分类号
TP311.13
[自动化与计算机技术—计算机软件与理论]
Q51
[生物学—生物化学]
题名 普通树非递归遍历算法的实现
被引量：1
4
作者
高红军
机构
辽宁广播电视大学丹东分校
出处
《信息技术》
2011年第3期122-124,共3页
文摘
根据普通树与其对应二叉树表示法在遍历序列上的特点,利用堆栈实现普通树深度优先遍历的非递归算法,利用队列实现普通树广度优先遍历的非递归算法。同时给出对普通树从输入到输出及三种遍历算法实现的完整的C++语言程序。
关键词
树 树的二叉树表示法 深度优先 遍历 广度优先遍历
Keywords
tree binary-tree representation of tree depth-first traverse breadth first traverse
分类号
TP311.12
[自动化与计算机技术—计算机软件与理论]
题名 2D-Delaunay三角网格的数据结构与遍历
被引量：13
5
作者
高晓沨
机构
清华大学数学系
出处
《天津理工大学学报》
2006年第2期66-69,共4页
文摘
本文总结了二维Delaunay三角网格的Bowyer-W atson自动生成算法及其实现步骤,提出了一种类的结构、函数范例(采用V isual C++6.0编写程序),并讨论了遍历三角网格各种方法的优劣性,给出实验数据对比;最后得出结论,用广度优先的遍历方法创建网格是生成三角网格一种相对便利有效率的方法;另外,讨论了初始点加入顺序对程序运行时间的影响.
关键词
Delaunay三角网格 类结构 自动生成 广度优先遍历
Keywords
delaunay triangulation class structure automatic generation width first traversal
分类号
TP391
[自动化与计算机技术—计算机应用技术]
题名 加权Petri网的字符串序列相似性度量
6
作者
胡迎城 邢玛丽 吴元清
机构
广东工业大学自动化学院
出处
《广东工业大学学报》
CAS
2024年第1期110-118,共9页
基金
国际重点研发计划项目(2019YFB1705904)。
文摘
由于现有的流程相似性度量方法大多只关注流程的单一维度,缺乏对流程信息的综合考虑,使得流程检索的准确率还有待提高。在综合考虑结构信息和行为信息下,提出了一种高效率、多维度的加权Petri网的字符串序列的相似性度量方法。该方法首先将事件日志信息加权至Petri网,然后使用广度优先遍历将加权Petri网模型转换为字符串序列,再将该序列分为一个带权重的紧邻变迁对集和一个结构序列并分别计算相似度值,最后加权得到流程之间的相似度值。实验结果表明,该度量方法准确率达到99.51%。另外,该方法在时间复杂度上也有着不错的优势。
关键词
广度优先遍历 流程 相似性 PETRI网 序列
Keywords
breadth-first traversal process similarity Petri net sequence
分类号
TP301
[自动化与计算机技术—计算机系统结构]
题名 具有数据保护功能的排水管网自动简化技术
7
作者
王芳
机构
武汉市规划研究院(武汉市交通发展战略研究院)
出处
《市政技术》
2024年第4期237-244,共8页
文摘
在城市排水管网水力建模过程中,管网简化是提高模拟效率的必要措施。针对目前管网简化技术存在自动化程度低和破坏原始管网数据等问题,设计了一种具有数据保护功能的排水管网自动简化技术。通过引入管网要素的简化状态标识,并为其扩充适当的简化特征字段用以描述简化后节点、管段和汇水子面积的拓扑关系。以广度优先遍历为基础进行枝状管裁剪和同属性串联管段合并,从而实现在保护原始数据情况下自动完成管网简化。通过实际案例对该方法的可行性进行了验证,结果表明简化前后管网的水力模拟结果相差较小且模拟耗时压缩为原始管网模型的5.5%左右。
关键词
GIS 排水管网 管网简化 数据保护 广度优先遍历
Keywords
GIS drainage network network simplification data protection breadth-first traversal
分类号
TU992
[建筑科学—市政工程]
题名 潮流转移灵敏度以及安全评估指标研究
被引量：22
8
作者
闫常友 周孝信 康建东 田芳 严剑峰
机构
中国电力科学研究院
出处
《中国电机工程学报》
EI
CSCD
北大核心
2010年第19期7-13,共7页
文摘
首先分析潮流转移的原因及伴随的现象。其次讨论潮流转移区域以及区域界定,对传统广度优先遍历(breadth first search,BFS)算法进行改进,提出潮流转移影响区域的界定方法。对安全评估工作的理论基础——3个基本概念(模型量化、平均功率角和潮流转移灵敏度)分别进行定义。提出潮流转移模型及其灵敏度的表达式。提出安全评估的评估方法,建立安全评估的数学模型,最终得到安全评估的综合指标,并阐述了指标的使用。开发潮流转移灵敏度及安全评估程序,利用该程序对真实电网算例进行仿真验证。
关键词
潮流转移 潮流转移灵敏度 安全评估指标 改进广度优先遍历 算法 潮流转移区域界定 模型量化 平均功率角
Keywords
flow transferring flow transferring sensitivity index on security analysis improved breadth first search （BFS） algorithm confining the flow transferring region quantifying the model average power angle
分类号
TM74
[电气工程—电力系统及自动化]
题名 基于GIS的管网爆管分析算法优化与实现
被引量：15
9
作者
王方雄 崔羽
机构
辽宁师范大学自然地理与空间信息科学辽宁省重点实验室 辽宁师范大学海洋经济与可持续发展研究中心 辽宁师范大学城市与环境学院
出处
《武汉理工大学学报（交通科学与工程版）》
2012年第3期575-578,共4页
基金
教育部人文社会科学研究一般项目(批准号:11YJC630202) 辽宁省教育厅创新团队项目(批准号:WT2010031)资助
文摘
爆管分析是城市地下管网管理中的一个重要管网分析功能,当前的多数管网系统所采用的爆管分析算法、管网数据模型及实现技术难以提供最优的爆管分析方案.文中采用Geodatabase网络模型将管网数据建模为几何网络和逻辑网络,在管网数据模型中明确表达网络流向,并一体化集成存储管网数据,并利用ArcEngine的网络访问接口扩展优化传统爆管分析算法——广度优先遍历算法,实现了支持环状管网的爆管分析功能,此优化方案已成功地应用于大连石化矿区管网综合管理系统.
关键词
管网 爆管分析 广度优先遍历 算法ARCENGINE Geodatabase网络模型
Keywords
pipe network pipe burst analysis breadth-first search algorithm ArcEngine Geodata- base network model
分类号
TU990.3
[建筑科学—市政工程]
题名 网络层与链路层综合拓扑发现算法及其实现
被引量：6
10
作者
孙克辉 陈艳山 程巍 张志强
机构
中南大学物理科学与技术学院 深圳市中联通电子有限公司
出处
《计算机工程与应用》
CSCD
2012年第4期107-110,共4页
基金
中南大学研究生创新基金项目资助(No.2009ssxt138)
文摘
为了实现对网络的有效管理与监控,采用层次化模型,提出了一种基于广度优先遍历的探索式拓扑发现算法。该算法将底层的设备发现与顶层的拓扑关系分析分离开来,在顶层利用图的相关理论,实现了网络层拓扑与物理网络拓扑的完整发现。与现有方法相比,该算法解决了网络层拓扑与数据链路层拓扑发现相互独立的问题,增强了其实用性。算法在中联通综合网络管理平台中的成功应用表明了其有效性。
关键词
网络管理 拓扑发现 广度优先遍历 简单网络管理协议(SNMP) 互联网控制消息协议(ICMP)
Keywords
network management topology discovery breadth-first search Simple Network Management Protocol （SNMP） Internet Control Message Protocol（ICMP）
分类号
TP393
[自动化与计算机技术—计算机应用技术]
题名 计算机技术在金属包装材料抗腐蚀性能分析中的应用
被引量：1
11
作者
李红梅 韩逢庆 纪纲 杨武
机构
重庆工学院信息系
出处
《包装工程》
CAS
CSCD
北大核心
2002年第1期19-21,共3页
文摘
在分析金属包装材料的抗腐蚀性能中引入计算机技术 ,建立包装材料表面的腐蚀特征及分布情况的数学模型 ,给出了计算包装材料表面的腐蚀特征参数的算法。利用该方法得出的腐蚀指标准确可靠 ,避免人工目测方式的误差和缺陷 ,为金属包装的选材提供依据。
关键词
金属腐蚀 特征参数 广度优先遍历 计算机技术 包装材料 抗腐蚀性能 特征识别
Keywords
Metal packaging material Erode Feature parameter Breadth first search
分类号
TB484.4
[一般工业技术—包装工程]
TG171
[金属学及工艺—金属表面处理]
题名 一种字符孔洞数的求法
被引量：2
12
作者
周明元 曹中华
机构
宜春学院现代教育技术中心 江西师范大学软件学院
出处
《计算机与现代化》
2005年第9期5-7,共3页
文摘
提出一种新的求字符孔洞数目算法。根据字符图像形状特征,把要识别的字符图像用有向图表示,对有向图进行广度优先遍历而得出字符孔洞个数,用于字符识别。
关键词
字符识别 孔洞数 有向图 广度优先遍历
Keywords
character recognition hole number digraph breadth-first tmversal
分类号
TP391
[自动化与计算机技术—计算机应用技术]
题名 公交线路中最优路线的查询算法设计
被引量：1
13
作者
王朝晖 杨洁
机构
江苏省测绘工程院
出处
《现代测绘》
2005年第S1期153-156,共4页
文摘
在一个公共交通网络中寻找两个结点间的一条最佳路径,使之换车次数最少。利用GIS地理分析的特性,设计了合乎乘客心理的最优路线查询算法。本算法是基于广度优先搜索提出公交路线最短路径选择的算法。该算法对图的搜索方法提出了一个新的思路,经模拟试验,算法简单合理,运算速度快,容易在计算机上实现。
关键词
广度优先遍历 最优路线 数据库 地理信息系统
分类号
U491.17
[交通运输工程—交通运输规划与管理]
题名 应用图论分析阻波器拆除对高频保护通道影响
14
作者
王志强 刘文霞
机构
华北电力大学电力系统保护与动态安全监控教育部重点实验室
出处
《电力系统自动化》
EI
CSCD
北大核心
2006年第24期57-61,共5页
文摘
随着光纤通信的发展,电力线载波通信已逐渐成为电力系统通信的辅助手段,很多高压输电线路上的载波通道被光纤通信取代,线路上闲置的阻波器增加了电能的损耗。在分析高频载波通道结构和频率分配方式的基础上,应用图论理论进行了图形建模,采用改进的广度优先遍历(BFS)算法搜索受卸载阻波器影响的同频使用通道间的最短路径,通过对最短路径中同频通道串音防卫度核算,给出了阻波器卸载的决策。文中改进了核算方法,使核算指标更实用化,并以实例说明了该方法的正确性。
关键词
电力线载波 高频保护 跨越衰耗 串音防卫度 广度优先遍历
Keywords
power line carrier high frequency protection crossover attenuation signal to crosstalk ratio breadth first traverse
分类号
TM77
[电气工程—电力系统及自动化]
题名 一种新型网格资源调度算法的研究
15
作者
罗光春 李炯
机构
电子科技大学信息中心
出处
《核动力工程》
EI
CAS
CSCD
北大核心
2007年第3期121-124,共4页
基金
电子科技大学青年博士平台基金支助(05BS01601)
文摘
网格的一个重要功能就是多个虚拟机构间共享资源。网格资源调度是其中关键问题之一。本文提出一种新型的网格资源调度算法——最小跳数算法,首先通过广度搜索遍历找到资源,并同时生成跳数场,再根据跳数调度资源。通过算法仿真证明,最小跳数算法大大提高了资源调度的效率。
关键词
最小跳数算法 网格资源管理 广度优先遍历 仿真实现
Keywords
Minimal hop algorithm, Grid resources Scheduling, Breadth first search, Simulation implement
分类号
TP393
[自动化与计算机技术—计算机应用技术]
题名 基于支持向量机的复合地基承载力预测方法研究
被引量：1
16
作者
麻王斌 张文杰
机构
中水珠江规划勘测设计有限公司 广州市市政工程安全质量监督站
出处
《人民珠江》
2010年第5期14-16,共3页
文摘
提出一种基于支持向量机的复合地基承载力预测方法。该方法从复合地基试验结果中提取特征参数,组成反映复合地基竖向承载力的特征向量,并利用一种改进的支持向量机的非线性映射特性和学习能力,建立特征向量和复合地基承载力之间的非线性隐式方程,用以预测复合地基承载力。实例研究表明基于支持向量机的复合地基承载力预测方法预测结果较为准确,具有一定的实用价值。
关键词
复合地基承载力 支持向量机 预测 广度优先遍历 算法
分类号
TU473.11
[建筑科学—结构工程]
题名 新的二部图判定算法
17
作者
王青松
机构
辽宁大学信息学院
出处
《计算机应用》
CSCD
北大核心
2009年第B06期181-183,共3页
文摘
二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂,需要指数级的时间代价。利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接。给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题。
关键词
二部图 二部图判定 广度优先遍历
Keywords
bipartite graph bipartite graph decision breadth first search
分类号
TP391.41
[自动化与计算机技术—计算机应用技术]
题名 基于数字化技术的明代官式建筑快速建模研究
18
作者
马瑞
机构
安徽电子信息职业技术学院信息工程学院
出处
《蚌埠学院学报》
2023年第2期60-67,共8页
基金
安徽省高校省级自然科学研究项目(KJ2018A0779)。
文摘
提出了一种借助少量考古信息的明代官式建筑的快速建模方法,首先依据明代官式建筑的营造法式总结出明代官式建筑的营造规则,分析考古参数对建筑型制等级规则、构件参数、构件属性约束及营造规则的影响;根据用户设置的参数构造以所有建筑构件为节点的参数强连通图,使用广度优先遍历算法遍历图中的全部节点并进行节点间的规则判断,得到符合规则的有向无环图拓扑序列,实现明代官式建筑的快速智能重建;最后以安徽省凤阳县明中都皇城遗址为例进行建模。该方法无需用户具备明代官式建筑领域知识,就能够快速、高效地重建出理想的明代官式建筑模型。
关键词
明代官式建筑 快速建模 营造法式 强连通图 广度优先遍历
Keywords
palace building of the Ming Dynasty rapid modelling construction rules strongly connected graph breadth-first traversal algorithm
分类号
TP391.72
[自动化与计算机技术—计算机应用技术]
题名 基于小波变异的二进制粒子群的软硬件划分算法
19
作者
彭蔓蔓 袁建亮
机构
湖南大学计算机与通信学院
出处
《微计算机信息》
2011年第11期51-53,18,共4页
基金
基金申请人:彭蔓蔓 项目名称:面向可重构片上系统的过程级动态软硬件划分研究 基金颁发部门:国家科技部(754209009)
文摘
针对可重构片上系统软硬件划分问题,采用DAG建模,提出一种改进的图广度优先遍历法,将软硬件划分问题转化为带约束条件的0/1背包问题,提出基于小波变异的二进制粒子群算法。该算法改变BPSO的粒子参数计算模式,利用群体最优值和个体最优值决定粒子当前取值的概率,并引入小波变异以一定概率对粒子变异,得到最优计算结果。实验表明该算法提高了解的精度,得到令人满意的划分结果。
关键词
DAG 广度优先遍历 粒子群优化算法 小波变异
Keywords
directed acyclic graph breadth first search Particle Swarm Optimization wavelet mutation
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
题名 大型复杂雕塑型面钢架特征曲线快速设计方法
被引量：2
20
作者
唐霞 杨颖 刘晓军 仇晓黎 贾连军
机构
无锡职业技术学院机械技术学院 中国人民解放军 东南大学机械工程学院 南京晨光艺术工程有限公司
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2020年第1期114-123,共10页
基金
“六大人才高峰”资助项目 “青蓝工程”资助项目 装备预先研究资助项目(41423010203)~~
文摘
为解决复杂雕塑型面钢架的特征曲线快速设计问题,基于几何约束建立设计问题的数学模型,并完成了数学问题的求解;针对特征曲线分支和多孤立图形的问题,采用广度优先遍历算法对特征曲线进行处理,剔除无用分支和孤立图形。通过设置保留参考平面来避免选择歧义的问题,解决了型面分块问题。采用复杂曲线转换为多段线的方法来解决复杂曲线加工设备不能处理的问题,并设计了转换精度分析方法。设计系统采用程序法建模的方式来进行设计系统的开发,并通过实例验证了设计系统的功能。
关键词
复杂雕塑型面 型面钢架 特征曲线 广度优先遍历 几何约束 多段线 程序法建模
Keywords
sculpture surface surface steel frame characteristic curves breadth-first search geometric constraint multi-line program-modeling
分类号
TP391
[自动化与计算机技术—计算机应用技术]
