基于遗传算法与有向图拓扑排序的工艺路线优化

针对工艺设计中的工艺路线优化问题,归纳了工步间的基本优先级约束关系。基于约束关系,将整个工艺活动过程转化为工步有向图,工步节点间的拓扑关系以约束矩阵的形式存储。提出了约束矩阵判错的检测方法;建立了工步图的拓扑排序模型。设计了一种随机的深度优先搜索算法对工步图进行拓扑排序,得到全部可行的一定数目初始工艺计划作为遗传算法的初始种群。算法中,提出了基于车间动态资源的加工序列编码策略;定量分析了工艺计划评价准则,采用罚函数的方法将目标函数和约束条件建立成一个无约束的优化目标函数,由此确定了染色体的适应度函数;设计了遗传操作算子(选择、交叉、变异),并通过基于模拟退火机制的精英策略加速算法收敛。最后,通过实例证明了该算法的有效性。

一种新的基于邻接矩阵的拓扑排序算法

为了降低基于邻接矩阵的拓扑排序算法的复杂性,将单顶点算法框架扩展成集合算法框架,给出一些便于进行拓扑排序的有向无环图的性质。在此基础上,定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算,给出了有向弧邻接矩阵的存储方案,最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。

关于拓扑排序算法的讨论

对 AOV网的不同存储结构的拓朴排序 ,在传统算法的基础上提出了新的改进算法 ,并对这些算法的时间、空间复杂性进行了分析和比较 。

面向作业车间调度的基于拓扑排序的二级嵌套蚁群算法研究

蚁群算法的出现,为求解作业车间调度问题提供了新思路。然而,由于作业车间调度问题的可行域属性非常复杂,目前,采用蚁群算法进行求解,还存在收敛可靠性差和优化程度不高的问题。针对以上两个问题,在对工序拓扑排序的约束特性进行分析的基础上,提出基于拓扑排序的二级嵌套蚁群算法,其基本思想是:以拓扑排序为基础,采用受限主路径覆盖可行域,从而降低搜索的规模和盲目性,提升收敛可靠性;将问题分解为工艺路径优化和设备遴选优化两个级别的问题,从而构造二级优化机制,采用工艺主路径与设备支路径嵌套递归的方式,实现工序排序与设备遴选之间的相互干涉,从而提升解的满意度。比较试验表明,与目前常用的蚁群算法求解方法相比,采用基于拓扑排序的二级嵌套蚁群算法求解作业车间调度问题,具有良好的收敛可靠性、求解效率和寻优能力。

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

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

拓扑排序的分布式算法

本文基于异步通讯的分布式计算模型,对AOE 网的拓扑排序问题,提出了一个分布式算法。设计此算法的关键是使用了一种动态生成树结构。算法的通讯复杂性是O(dm),时间复杂性为O(d^2)。这里d 是网络的直径,m 是网络的通讯链数目,n 是网络中处理机数目(d<n)。

一种有向权图的拓扑排序算法及其应用

提出一种有向权图的拓扑排序算法 ,并给出一实例说明其应用。

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

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

拓扑排序在并发控制可串行化算法中的应用

并发控制是分布式数据库管理系统的重要组成部分 ,并发控制用来控制多个事务的并发运行 ,避免它们之间的相互干扰 ,保证每个事务都产生正确的结果。该文从构造并发控制可串行化的前趋图出发 ,利用拓扑排序进一步研究了并发控制可串行化的算法 ,详细阐述了冲突可串行和状态可串行化的测试算法并运用在实例中。该算法可以作为并发控制可串行化的正确性准则 ,在实际中 。

拓扑排序算法在教务管理系统中的应用

提出了一种在教务管理系统中利用拓扑排序算法实现教学计划自动编排的具体实现方法，并介绍了该方法的设计思路。

数字电路并行全入度拓扑排序优化算法

针对当数字电路的时序难以满足优化目标时要进行设计迭代的问题, 通过改进产生线性序列的拓扑排序算法, 提出了并行全入度拓扑排序和数字电路并行全入度拓扑排序优化算法. 该算法通过对电路的有向图并行全入度拓扑排序, 得到电路中插入寄存器可选位置的详细信息; 然后结合得到的信息和优化目标, 直接选择流水线插入位置优化电路, 无需设计迭代. 实验结果表明, 插入同样级数流水线时, 使用文中算法优化的电路面积比重定时优化的减少20%-40%; 与经典有效重定时判定算法FEAS 相比, 该算法拥有更低的时间复杂度.

基于特征分层拓扑排序和改进蚁群算法的工艺路线研究

针对工艺路线决策中多约束问题,提出了一种基于特征分层拓扑排序和改进蚁群算法的优化方法。首先分析零件的特征关系,其次将特征包含的工序元分层拓扑排序并建立加工资源最优模型,最后改进蚁群算法信息素更新规则并对工艺路线进行设计和实例验证。结果表明:与普通蚁群算法相比,采用基于特征分层拓扑排序和改进蚁群算法得到的工艺路线,满足加工顺序约束和加工资源约束,具有良好的收敛性、可靠性。

拓扑排序和强连通算法在源代码分析中的应用

缺少文档的开源项目和文档不完整的开源项目,分析其源代码是了解其运行机理的主要方法,本文提出一种基于函数分析顺序的分析方法,并且提出构建函数分析顺序的过程。过程为首先使用强连通算法消除函数递归调用,得到一些组件,再用拓扑排序对组件和组件内部的各函数节点排序,得到一个分层链表,谊链表包含各函数的调用顺序和分析顺序,再用一种展开算法将分层链表展开,最终得到源代码中的函数分析顺序。

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

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

分层拓扑排序及其算法设计与实现

介绍分层拓扑排序概念以及它与拓扑排序的区别。同时介绍分层拓扑排序算法的设计与实现方法。在算法设计与实现中采用一个链接结构的"优先序列",用它保证有向无回路图顶点的分层拓扑排序。

基于元胞自动机的拓扑排序算法

目的利用元胞自动机的特性,找到一种新的拓扑排序算法。方法将AOV网构造成一个元胞自动机模型,采用经过改造的邻接链表作为元胞的数据结构,并在其中引入随机编号项,所有元胞依据随机编号顺序地遵守演化规则进行演化,实现拓扑排序。结果利用元胞自动机的时空局部规则和并行计算特性,设计并验证了拓扑排序算法。结论与传统算法相比本算法在时间、空间复杂性上都有较大改善,并且在应用元胞自动机理论解决图的问题方面有所贡献。

基于拓扑处理的Logit型网络加载算法

针对均衡交通分配问题,提出了一种基于拓扑处理来改进DIAL算法中合理路径的定义并求解Logit型网络加载模型的新算法。当道路网络存在环路时,算法根据从节点到讫点的阻抗的降序来删除节点上游没有遍历的路段,从而将有环网络变为无环网络并根据拓扑排序确定的节点计算顺序来计算路段权重和流量。对于无环网络,新算法可以得到与理论值完全一致的结果;对有环网络,可以减少DIAL算法中非合理路径的数目。计算实例表明:新算法可降低DIAL算法中合理路径定义过于严格所带来的误差。

贪婪算法之拓扑排序浅谈

在研究拓扑排序的基础上讨论了拓扑排序在工程流程计算机中的应用,提出了用于拓扑排序的贪婪算法,并用C语言进行仿真,给出了仿真结果。

贪婪算法之拓扑排序的实现

拓扑排序是图的应用领域中一种重要运算,可以根据拓扑序列串行地安排活动。本文给出了拓扑排序的贪婪算法,讨论了算法中用到的数据结构,本文采用邻接表和栈以C++语言进行仿真,给出了仿真结果。

同一结点上弧—弧拓扑关系生成的新算法

对于同一结点上弧段之间的拓扑关系建立提出一种新的算法 ,运用计算几何学原理 ,通过各线段的矢量外积直接进行比较排序。此算法避免了以往算法中参数值计算和其它烦琐的数学运算 ,较之以往的生成算法明显优化了代码并提高了算法的执行效率 。