拓扑排序

摘要： 介绍了排序的基本概念和常见排序类型,讲解了图排序中的一种非常重要的排序算法拓扑排序的概念,研究了拓扑排序的原理以及2种常见的遍历算法,分析了拓扑排序的空间和时间复杂度,采用这2种遍历算法对有向无环图进行拓扑排序的实现,并对拓扑排序的常见应用场景进行了介绍。

摘要： 外键作为关系型数据库中的重要约束之一,对约束数据库的操作顺序有着重要意义,但在数据库集群同步情况下用户无法得知操作顺序,会造成外键冲突,为解决该问题,提出一种基于有向图的外键冲突解决算法.将外键关联转化为有向无环图模型,基于SQL语句实现生成有向图的邻接矩阵数据,通过拓扑排序遍历有向无环图,得到满足数据表写入操作的原子性序列.实验结果表明,与传统暴力枚举算法相比,该算法解决外键冲突的执行时间更短,数据库访问频率更低,且CPU占用率和内存消耗性能指标均体现出明显优势.

摘要： 为解决核电DCS控制逻辑组态软件环境封闭无法扩展的问题,以机组设计文件或现场数据备份为数据源,采用有向图模型对DCS控制逻辑进行离线重建,定义了边的权值和结点比较规则,对有向有环的DCS控制逻辑进行强连通分量计算和缩点操作转换为有向无环图,再基于结点比较规则进行确定性拓扑排序,得到表征结点拓扑结构的唯一序列,设计关系数据库存储有向图各属性得到离线DCS控制逻辑数据库.并将离线数据库应用于CEPR机组DCS离线逻辑查询和自动逻辑风险分析等场景,使用效果表明,重构后的离线数据库能够完整复现出机组封闭DCS控制逻辑数据源的模块属性和详细拓扑结构关系,可为核电DCS控制逻辑相关的计算机辅助分析应用提供一种简单、开放和准确的数据源输入.

摘要： 针对百万机组数据量大、逻辑页面多、多人并行交互调试的应用场景,设计开发了在麒麟系统上运行的符合IEC61131-3标准的工控组态软件SmartIC.该软件采用组件化集成框架,基于虚拟消息总线进行组件间交互;充分利用麒麟多核环境,采用多线程快读机制实时形成、刷新展示组态之间信号引用跳转关系;设计了基于位置视觉和能量流传递相结合的多级反馈图形程序的拓扑排序算法,实现了图形化页面符号自动准确执行.软件支持批量查找替换、导入导出、组态备份等快捷功能.软件在DCS项目中进行了工程应用,稳定可靠,具备工程推广应用条件.

摘要： 分析任务流的调度是人们关注的热点问题之一.在无法提前得知各子任务资源和时间开销以及算子间传输开销的情况下,现有研究缺少较好的调度方法,也无法很好地处理多平台环境下的任务调度.为此,本文提出了一种基于启发式规则优化的拓扑调度算法.该算法通过对同平台任务和后继任务优先选择的规则,对任务流调度顺序进行优化;其次,结合Spark平台下数据分析任务常见的SQL算子和机器学习算子的代价模型,有效对任务的开销做出估计.实验表明,调度优化算法能有效节约时间开销和内存开销,代价模型的估计也较为准确.

摘要： 针对空间飞行器控制系统软件在开发演化时存在管理复杂、开发过程无序、协同度低的问题,提出一种空间飞行器控制系统软件协同演化的方法.首先对软件演化过程中的演化活动、演化策略进行了分析,之后基于对软件演化活动所得到的演化路径利用有向图进行了建模并给出了其演化活动的排序,最后,对演化路径有向图中出现的并行活动和环的情况进行分析,同时给出了相适应的排序算法.基于该方法,软件演化过程得到规范,较好地解决了复杂情况下演化路径求取困难的问题.

摘要： 随着电网规模不断扩大,快速形成大电网节点阻抗矩阵具有重要实用价值.为了加速阻抗矩阵的生成,针对中央处理器(CPU)+图形处理器(GPU)协同计算架构设计了基于GPU的并行支路追加法.通过分析电网拓扑结构与链支的关系,基于图论最小环设计了节点编号优化算法;通过厂站连接关系,提取厂站级别最小环,利用拓扑排序,确定群追加顺序.在群基础上确定厂站追加顺序,进而进行节点编号顺序优化.试验结果表明,相比串行计算方法,所提方法在计算效率方面有显著提高,在大电网计算中,可获得数十倍的加速比,追加链支的加速比达百倍.

摘要： 多核处理器的广泛应用促使了多核并发程序可信问题的研究,因多核并发程序具有数据竞争而引起的程序执行结果的不确定性是并发程序分析与测试的难点.提出一种基于拓扑排序的数据竞争定位方法,采用XML对经过词法、语法解析的结果进行分析建模,利用XQuery查询语言提取XML文件中共享资源访问信息,使用线程访问树生成算法构建NET-TREE模型.基于NET-TREE模型,定位数据竞争点,记录可能的数据竞争序列.大量实验结果表明,该模型能够发现数据竞争并有效确定其位置.

摘要： 可测性分析用于指导数字系统的计算机辅助测试与设计.本文用面向对象程序设计语言构造描述集成电路的数据结构,论文详细介绍了数字电路的描述方法,给出了可测性分析算法,并将有向图的拓扑排序引入可测性分析程序设计,提高了可测性分析的计算速度.理论分析和试验结果表明,用改进后的算法计算可控性可观性是行之有效的.

摘要： 在前馈神经网络中，任意两个神经元之间都可以存在连接，包括神经元的跨层连接，为了适应这种灵活而又复杂的拓扑结构，引入“拓扑排序”（算法1）和“偏序”，并提出了前馈神经网络的BP学习算法（算法2），自构形学习算法（算法5）。上述的稀疏化算法，不仅要修改已有的连接权值与阈值，还要建立新的连接。实验结果表明，这些稀疏化算法都能够有效地稀疏化前馈神经网络。

摘要： 该文在ＣＡＤ／ＣＡＰＰ集成信息的基础上，建立了一个统一的知识库，包括外部知识库和内部知识库，支持工艺决策中加工方法决策和加工顺序决策，通过产生式规则的正向推理机制，提出了加权值有向图拓扑排序与二叉查找树中序遍厉的分层排序算法，为计算机辅助柔性生产线方案设计快速响应ＣＡＰＰ技术实现提供一种方法。

摘要： 本文采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾。

摘要： 本文采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾。

摘要： 本文采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾。

摘要： 本文采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾。

摘要： 本文采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾。

摘要： 产品多样化是提高制造企业提高竞争力的一种必要途径,然而多样化又要求企业具有敏捷制造的能力和先进的管理方法.本文提出了一种并行工序的编排方法,力图提高企业的生产效率.在实际中,生产作业计划的编排往往建立在产品的工艺结构之上,因而本文提出的方法建立在有向层次图理论的基础上,理论严谨,方法简单、直观.本文提出的方法灵活性较强,可根据不同的生产策略和生产条件做适当的调整,为了说明这一点,本文在末尾讨论了针对不同的物料需求而编排不同的并行工序.本文从结构上讲,主要分为五个部分:第一分部是引言,主要引入了并行生产;第二部分分析了有向层次图和多种产品结构的关系;第三部分介绍了如何根据有向层次图的关键路径和生产计划期限来安排并行计划;第四部分分析了基于不同的物料需求的不同并行策略;第五部分是结论和今后的研究方向.

摘要： 一种基于拓扑排序的矩阵分块划分方法，包括：1）根据LU分解规则，求出矩阵各列之间的依赖关系；2）对所述依赖关系进行拓扑排序，将所有列分成至少一层；3）根据层次关系，对所述矩阵列的位置进行重排；4）对位置重排后的新矩阵进行分块划分；5）按层级顺序对同一层级的所述分块进行并行计算。本发明的一种基于拓扑排序的矩阵分块划分方法，可以更加有效地利用计算机的CPU/GPU资源，提高矩阵并行计算的能力。

摘要： 本发明涉及一种基于有向无环图和拓扑排序的自动化测评方法与系统。该方法将逻辑节点和逻辑节点间指向关系构成有向无环图，将有向无环图进行拓扑排序，产生解集；将使用者提交的结果序列与解集中的解进行遍历比对，获得最终结果。该系统包括信息生成子系统、前台交互子系统和逻辑验证子系统。使用者可以使用该系统生成数学证明和推导过程中的元素，并实现大规模在线检测学习者的逻辑思维严密性与演绎推理能力，同时获取学习者在推导过程中遇到的问题。本发明为教学工作者提供了一个高效率且简单易用的教学工具，同时也为学习者提供了一个互动性强且有趣味的信息交互和学习平台，更有效地锻炼使用者的计算思维。

摘要： 本发明公开了一种基于拓扑排序算法的飞控系统分层SDG建模方法，包括如下步骤：S1、初步SDG建模；其中，根据飞控系统的组成器件及器件之间的影响关系和电信号传播方向，明确器件数量、名称和功能，根据敏感性分析法，结合经验知识的方法确定各器件之间的影响关系，基于器件间正负关系，以具体器件为节点，正负关系为有向边，建立飞控系统的符号有向图模型；S2、模型分层；其中，以建立好的符号有向图为基础，结合飞控系统特点，将闭环回路断开，基于拓扑排序算法，遍历所有节点，计算所有节点的入度，并将入度为0的节点从原符号有向图中取出，循环至原符号有向图节点为空。本发明能够提高分层效率和模型的可理解性、降低分层操作的复杂度。

摘要： 一种基于DAG的拓扑排序方法，包括如下步骤，S1、获取第一无直接前驱头节点集，所述无直接前驱头节点为无前节点的节点，无直接前驱头节点集就是无前节点的节点的集合，S2、循环遍历所述第一无直接前驱头节点集中的无直接前驱头节点，对每个无直接前驱头节点引出的所有边，对每条边逐一获取该边连接的第二节点，再对每条边逐一进行移除，并进行判断：如果获取的所述第二节点的入度在移除边之后为0，则将所述第二节点放到当前批次的第一无直接前驱头节点集中；通过上述方案，使数据存储效能呈现几何级提升，完全解决了传统区块链的单链线性存储效率低下的问题，使得区块链的瓶颈问题得以突破和解决。

摘要： 本发明涉及智能计算技术领域，尤其涉及一种基于改进的拓扑排序的培养方案教学计划编制方法，具体步骤如下：S1：根据培养方案中的课程信息，得到反映课程之间关系的有向图G；S2：在拓扑排序中增设阶数对有向图G进行拓扑排序，得到拓扑序列S1；S3：对拓扑序列S1按阶数进行排序，得到序列S2；S4：量化课程设置条件；S5：按课程设置条件，将序列S2分割成若干个子序列，将课程落实到每学期中。本发明能够使教学计划制定自动化，一方面提高教学计划编制的工作效率，另一方面提高教学计划的科学性和合理性，并且可以方便教学评估、专业认证中教学计划方面的数据分析。本发明可以用于高校人才培养方案的教学计划编制，所以实用性强，使用面广。

摘要： 本发明涉及一种基于时间轮和拓扑排序的分布式任务调度方法，包括如下步骤：包括如下步骤：S1：进行作业组的批量配置，并将配置后的作业组保存至配置库中，通过调度任务线程对配置库进行作业组及作业运行状态库的更新，根据作业运行状态库进行作业信息的获取并发送至消息队列；S2：进行消息队列中待执行的作业组信息的获取，执行器根据服务器资源占比进行该作业组的执行状态判定；S3：对所批量配置的作业组进行执行状态的统计。本发明提供了一种基于时间轮和拓扑排序的分布式任务调度方法，解决了现有技术中大数据批量任务并发难、服务器资源不能得到充分利用的问题，同时还提高了任务处理的效率以及资源的利用率。

摘要： 本发明涉及数据处理技术领域，具体为一种基于拓扑排序的任务编排方法、装置、设备及存储介质，包括：启动跑批业务，并进行统一处理；统一处理包括：构建跑批业务的拓扑结构；根据拓扑结构，处理业务：当一个业务正常完成后，根据拓扑结构，判断是否存在依赖于该业务的下一业务，若存在，则触发该下一业务启动，直至完成跑批；在处理一个业务时，当一个业务中的任一子任务完成后，根据拓扑结构，判断是否存在依赖该子任务的下一子任务，若存在，则触发该下一子任务启动；在过程中进行异常监控。本方案以拓扑排序将跑批业务中的各业务以及其子任务进行串联，控制运行的过程和可视化操作，降低出错异常的概率。

摘要： 本发明公开了一种基于拓扑排序的任务调度方法及系统，属于计算机系统技术领域。包括：获取大规模有向无环任务调度图，并基于拓扑排序的粗化算法对大规模有向无环任务调度图进行多级粗化处理，以获得对应的有向无环初始调度图；基于小规模调度算法对有向无环初始调度图进行初始划分，以获得有向无环初始调度图的粗化图划分结果；基于细化算法将粗化图划分结果映射回大规模有向无环任务调度图，并进行细化调整，以获得大规模有向无环任务调度图的任务调度划分结果。由于预先对大规模有向无环任务调度图进行了多级粗化处理，对任务进行了聚类，从而对于大规模任务调度场景，使用任务调度算法也能够有效缩小处理量，进而降低运算复杂度。

摘要： 本发明公开了一种基于拓扑排序的地层顺序获取方法，包括以下步骤：采集若干实验区钻孔数据，得到每个钻孔数据对应的地层顺序；根据每个钻孔数据对应的地层顺序，构建加权有向图；基于加权有向图，对地层进行排序，得到预估地层顺序；核查预估地层顺序是否正确，若是，则得到最终地层顺序，否则对错误的地层顺序进行修改，得到最终地层顺序。本发明能够在缺少地质背景资料的情况下获取地层序列；且能在有地质背景资料的下，快速核对地层序列，从而减少人工工作量。

摘要： 本发明是一种基于拓扑排序的区块链交易依赖分析方法，其主要特征包括以下步骤:（1）对待处理的每个交易，循环步骤（2）到步骤（5）的操作。（2）计算交易哈希泳道号wn。（3）交易依赖冲突检测。无冲突则为交易分配依赖分析泳道号dn，进入下一步。否则交易退回交易池。（4）交易泳道号冲突检测。如果wn==dn，为交易分配最终泳道号wn，进入下一步。否则交易退回交易池。（5）交易进入分配的泳道分析集合，创建或更新DAG。（6）根据各泳道内的DAG进行拓扑排序，入度为0的交易根据时间戳确定在该泳道内的唯一执行顺序。本发明涉及区块链技术领域，通过分析存在依赖关系的交易，使交易能够在多个泳道上并行执行，提高区块链系统的交易速度。