AOV网中全拓扑排序算法的设计及应用

以顶点表示活动的网络(AOV网)可用来表示整个工程中各个子工程的先后次序制约关系,利用拓扑排序算法能求得子工程的线性序列———拓扑序列。按此序列安排各子工程,能保证整个工程的顺利完成。传统的拓扑排序算法基于栈结构实现,只能求得实际存在的多个拓扑序列中的一种,削弱了算法的实用价值。文中为了弥补这一缺陷,设计全拓扑排序算法求出了AOV网中实际存在的全部拓扑序列。给出了AOV网的定义及拓扑排序算法思想,分析了传统拓扑算法的不足,提出了一个全拓扑排序求解算法。并讨论了算法中用到的数据结构,以及算法的伪代码实现,通过一个应用实例验证了全拓扑排序算法的实用性和正确性。     

AOV网中全拓扑排序算法的设计及应用

以顶点表示活动的网络(AOV网)可用来表示整个工程中各个子工程的先后次序制约关系,利用拓扑排序算法能求得子工程的线性序列--拓扑序列.按此序列安排各子工程,能保证整个工程的顺利完成.传统的拓扑排序算法基于栈结构实现,只能求得实际存在的多个拓扑序列中的一种,削弱了算法的实用价值.文中为了弥补这一缺陷,设计全拓扑排序算法求出了AOV网中实际存在的全部拓扑序列.给出了AOV网的定义及拓扑排序算法思想,分析了传统拓扑算法的不足,提出了一个全拓扑排序求解算法.并讨论了算法中用到的数据结构,以及算法的伪代码实现,通过一个应用实例验证了全拓扑排序算法的实用性和正确性.     

并行拓扑排序算法PTSA的设计与实现

文章对AOV网首次提出了一种基于层次的混合数据结构,按分层处理的方法实现并行拓扑排序算法PTSA,求得了AOV网中顶点的所有拓扑序列,克服了以往基于栈结构只能求得一种拓扑序列的缺陷。PTSA算法为工程中各子工程的串行或并行安排提供了确定的选择,提升了拓扑排序算法的实用价值。     

一种有向图并行性全拓扑排序算法设计与实现

讨论了AOV网的一种并行性全拓扑排序的算法及实现,解决了传统拓扑排序算法的单一性问题,说明了并行全拓扑排序有重要的实用价值。     

一种新的AOV网络拓扑排序算法

通过表达每个顶点在图中相对其他顶点的位置，提出的后序集的概念。基于此将图用二维数组存储，构造出一种新的基于后序集的AOV网拓扑排序算法，给出了算法的思路和实现步骤，采用一个装配生产线作业顺序规划问题为实例，验证了算法的正确性和可行性。     

基于模拟退火遗传算法的服务选择

为了解决面向服务体系结构服务组合中服务选择问题,提出了一种将模拟退火算法与遗传算法相结合的融合算法。将服务流程等效成AOV图,对AOV图进行拓扑排序,并将生成的拓扑序列作为遗传算法的编码,使用QoS参数作为适应度,在遗传算法生成每一代子代后,利用模拟退火算法对其进行局部优化调整。仿真实验结果表明,模拟退火遗传算法在减少服务流程资源消耗上能取得理想的效果。     

基于AOV图和多叉树的功能块程序编译算法北大核心CSCD

针对可编程逻辑控制器(PLC)的功能块(Function BlockDiagrams,FBD)程序指令类型多、串并联复杂和多重输出等问题,提出一种基于顶点活动图(Activity on Vertex,AOV)和多叉树的功能块程序编译算法。该算法将功能块程序映射为AOV图,首先用邻接表存储AOV图中的顶点信息和顶点之间的连接信息,对功能块程序进行语法检查,然后通过邻接表建立表示功能块间逻辑关系的多叉树,通过先根遍历算法遍历多叉树确定功能块执行顺序,最后按照遍历顺序和PLC指令结构将功能块程序转换成二进制代码,形成目标程序。该算法能将PLC支持的功能块指令程序编译为目标程序,具有通用性,已经成功应用在PLC开发平台软件PLC_Config中。     

一种HRG模型初始化算法及在链路预测中的应用

在利用层次随机图（HRG）模型对真实网络进行链路预测的过程中,需要构造一个初始层次随机图来初始化马尔科夫链以运行马尔科夫链蒙特卡洛抽样算法。针对现有的层次随机图初始化方案效率不高的问题,本文对初始层次随机图模型进行重建,提出一种新的层次随机图模型初始化算法。该算法分为2个阶段,第一阶段引入相似性指标（LHN-I指标）为网络中的边进行排序;第二阶段利用排序好的边对层次随机图模型进行构造。在该过程中,设计一种将网络顶点插入到层次随机图模型中的方法。通过3个实例网络对提出的算法与现有算法的性能进行比较,实验结果表明,利用提出的初始化算法构造出的初始层次随机图不仅有着较高的似然值,而且使得马尔科夫链蒙特卡洛算法能够更快地收敛,进而降低链路预测的时间消耗。除此之外,在链路预测实验中,改进的基于层次随机图模型的链路预测算法相比一些基于相似性指标的链路预测算法有着较好的预测精度。     

布尔表达式的化简与并行排序网络验证

为设计出能够验证并行排序网络正确性的有效工具,根据[0,1]原理和布尔函数的特点和性质,提出一种布尔表达式的化简算法,并根据此算法设计出验证工具.对[0,1]原理和布尔函数的特点和性质进行了讨论,指出有利于化简操作的性质.设计出的工具能够根据并行排序网络的参数显示网络图形、自动生成布尔表达式并实现化简验证,工具的输出有利于对排序网络的分析,也可以用于辅助排序网络的设计和优化.实验结果表明了该工具的有效性.     

一种新的无线传感器网络拓扑发现算法*

GBGD是一种面向攻击的隐蔽性较强的拓扑发现算法,通过分析发现,该算法对实际网络进行了过于理想化的假设,导致无法在实际中应用。在GBGD算法工作模式的基础上,对实际网络提出了合理假设,设计实现了一种新的网络拓扑发现算法,通过对报文向基站汇聚过程中每一跳转发时延进行分析得出节点在路由树中的层次关系,进而推算出网络的拓扑。仿真实验结果表明,该算法能准确推断出网络的拓扑,并在报文存在丢失较多的情况下具有较好的鲁棒性。由Mica2节点组成的原型系统实验结果表明,该算法能够较好地应用于实际网络。     

PLC梯形图向结构文本转换的算法及实现

通过分析IEC61131-3标准规定的PLC梯形图语言及结构文本语言,提出对梯形图不同图元分类处理实现梯形图向结构文本转换的算法.该算法引入了虚节点,通过对虚节点的合并建立AOV图,按AOV图拓扑排序的顺序对不同类型节点分类处理,实现梯形图向结构文本的转换,并给出转换实例.该算法具有通用性,能转换任何复杂逻辑梯形图,已成功应用到高档数控国家工程研究中心的蓝天系列数控系统.     

关于软PLC梯形图向语句表转换方法的研究

以行双向链表作为梯形图数据结构,记录梯形图载有的信息,确保梯形图的正确显示和存储;从有向图的角度出发,经过顶点扫描﹑弧扫描﹑和构图,将梯形图映射至AOV网;根据顶点在AOV网中位置关系的不同,研究转换算法的实现。     

产品报价系统的模式和算法设计

本文讨论了产品报价系统的关系模式设计方法，给出了用二维表表示ＡＯＶ网的逆拓扑排序和按后根次序遍历树的算法。     

Topological ordering algorithm for LDAG

Directed Acyclic Graph (DAG) is an important tool for workflow modeling and data provenance management. In these applications, DAG usually performs well. Yet for some workflow applications, except data or control dependencies between atomic tasks, there exists another requirement that each atomic task should be accomplished at an expected stage. Therefore, this paper proposes an improved DAG model – LDAG, in which each vertex has a level. Three cases of the level of vertices are discussed. For a reasonable one of these cases, this paper proposes a topological ordering algorithm and proves its correctness. In addition, it discusses the complexity of the algorithm and some other relevant problems.     

基于AOV图存储PLC梯形图的方法

提出一种直接以AOV(Activity On Vertex)图存储PLC(Programmable Logic Controller)梯形图的方法。编辑梯形图的同时,修改AOV图,然后根据AOV图的拓扑结构更新梯形图图符坐标,最后进行绘制显示。该方法无需进行梯形图向AOV图的转换,通过操作规则的约束来替代语法的检查,使梯形图的编辑更加便捷和规范。详细介绍了AOV图的编辑过程和坐标的更新算法。对AOV图向二叉树的转换算法进行修改,使其能适应于所有AOV图,并给出了相应的实例。     

踪迹聚类下组织实体的重要度排序方法

针对简单套用交接网络等社会网络分析方式不能很好地反映踪迹聚类生成的一系列流程的组织实体的重要度的问题,提出了一种踪迹聚类下组织实体的重要度排序方法。首先,对于参与踪迹聚类生成的一系列流程的组织实体构建踪迹聚类与组织实体关系网络;其次,定义基于踪迹聚类与组织实体关系网络的节点重要度评估方法;最后,对踪迹聚类下的各个组织实体节点计算其在关系网络中的重要度评分并排序。实验结果表明,所提方法构建的关系网络相比踪迹聚类下的交接网络能够更准确地反映组织实体的实际重要度;与基于拓扑势的网络社区节点重要度排序算法相比,所提方法的节点重要度排序结果更符合实际业务流程,能更好地区分关系网络中重要度不同的节点。     

基于AOV网的应用程序构建模型研究

消灭“软件遗产工程”,实现软件的“自由动态修改维护”,是软件工程学面临的一大难题,至今尚未彻底解决。文中提出一种新的应用程序的构建模型—“AOV网模型”(modelofActivityOnVertexnetwork),即用AOV网描述应用程序的拓扑结构,用脚本语言构造AOV描述文件,利用事件驱动机制,通过周游AOV网,控制调度程序的运行。使程序的功能流程完全由可编辑的AOV描述文件确定,实现了软件的完全、自由意义上动态修改、维护特性。解决了可执行软件像铁板一块,不可改变和重用等弊端。作为构建模型的应用,给出了“语音服务系统”的设计与实现。