基于时间约束的DAG图上的最短路径算法研究

一、引言 设G一(V,E)是一个有向无环图(DAG图).在该图上计算单源最短路径算法的经典算法是Dijkstra算法.     

基于DAG的分布式账本共识机制研究

自2008年比特币出现以来,研究学者相继提出了多种分布式账本技术,其中,区块链是当前分布式账本最主要的实现形式之一.但当前区块链中存在一个核心问题:可扩展性瓶颈.具体而言,区块链的吞吐量严重不足,且其交易确认也较为缓慢,这些因素极大地限制了它的实际应用.在此背景下,基于DAG(有向无环图)的分布式账本因其具有高并发特性,有望突破传统区块链中的性能瓶颈,从而受到了学术界和产业界越来越多的关注和研究.在基于DAG的分布式账本中,最为核心和关键的技术是其共识机制,为此,对该关键技术进行了系统深入的研究.首次从共识形态出发将现有基于DAG的分布式账本分为以下3类:基于主干链的DAG账本;基于平行链的DAG账本;基于朴素DAG的账本.在此基础上,对不同类型的共识机制本质原理及特性进行了深入阐述,并从不同层面对它们进行了详细的对比分析.最后,指出基于DAG的共识机制研究中存在的问题与挑战,并给出进一步的研究方向.     

分布式系统下的DAG任务调度研究综述

近年来随着网格、云计算工作流等分布式计算技术的发展,关于DAG(有向无环图)模型任务在分布式系统环境下的调度问题逐渐成为备受关注的研究热点。根据最新研究进展,对分布式系统下的DAG任务调度问题和有关技术进行了研究与讨论,主要包括四个方面:系统地描述了分布式系统和异构分布式系统的有关概念,异构分布式系统下的DAG任务调度问题、调度模型及其典型应用;对现有分布式系统下DAG任务调度的研究按照不同的方式进行了分类;探讨了多DAG共享异构分布式资源调度的研究现状;讨论了目前多DAG共享异构分布式资源调度研究存在的问题和未来可能的研究方向。     

云计算环境下多DAG调度的资源分配进化算法

现有多DAG调度研究主要在多个DAG共享资源调度的时间最小化、公平性最大化、吞吐量最大化等问题方面提出了相关的解决方案,然而,现有的方法还不能很好地解决云计算环境下多DAG共享资源调度的资源分配优化问题.为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享资源调度的资源分配优化问题,既保证了多DAG的调度执行时间最小化,也避免了资源的浪费.实验表明,EFRD算法能够有效地收敛到最优解.     

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。     

异构分布式环境下多DAG工作流的混合调度策略

关于多个DAG工作流在异构分布式环境下调度的研究近来有了新的进展,也解决了一些问题,但现阶段还没有考虑和解决根据不同类型DAG的需求按优先级进行分类,以及对不同时间到达的多个不同优先级DAG进行调度的问题.为解决这些问题,针对各用户对DAG工作流的QoS需求的不同,在对不同用户的DAG工作流进行优先级划分的基础上,首先提出了一种新的调度模型,并改进了已有的公平调度算法,解决在不同时间上被提交的具有相同优先级的多个DAG工作流之间调度的公平性问题.为了提高资源利用率和高优先级DAG尽可能小地受低优先级DAG的影响,又提出了一种适用于多个不同优先级DAG之间调度的Backfill算法.在新的系统模型和这两种算法的基础上,提出了一种混合调度策略.实验结果表明,这种混合调策略能够兼顾不同时间到达的多个不同类型DAG调度需求和资源利用率的改善.另外,通过实验发现了关于两个DAG调度所特有的"拖尾"规律,具有进一步研究和应用的价值.     

基于有向无环图的倒排链等字长划分压缩算法

在搜索引擎的倒排索引等字长（FWA）类型压缩算法中,倒排链的“贪心”分块划分策略和码字信息的交错存储使算法难以达到最优的压缩效果。针对上述问题,提出了一种基于有向无环图（DAG）的FWA划分压缩算法。首先,考虑到互联网网页聚类特性带来的倒排链小数字信息,设计了一种数据区为64位分块的新型FWA压缩格式。该压缩格式通过4位的指示区将数据区划分为16种适合于连续小数字压缩的存储模式,并将倒排链每个分块的指示位和数据位分类存储,从而保证了较好的批量解压性能。其次,在新压缩格式的基础上提出一种基于DAG描述的倒排链FWA划分压缩方法——固定字对齐划分（WAP）算法。该算法利用DAG将倒排链分块划分问题归结为单源最短路径（SSSP）问题,并考虑FWA压缩格式中数据区存储模式的限制条件来确定SSSP问题的结构形式和递归定义。然后,给出了采用动态规划求解SSSP问题并形成最优划分向量的伪码和算法复杂度,并对S9、S16、S8b等传统FWA算法的原有存储模式进行了基于DAG的划分优化,把优化前后的算法的计算复杂度进行比较分析。最后,使用仿真整数序列数据和文本检索会议（TREC） GOV2网页索引数据进行压缩性能实验。实验结果表明,相较于传统FWA类型算法,基于DAG的FWA划分算法在通过批量解压和划分优化技术提升算法的压缩率和解压速度同时,对连续小数字整数序列进行压缩时能够获得比传统参照框架（FOR）类型算法更高的压缩率。     

有期限约束的多DAG共享资源的调度及公平费用优化方法

随着网格和云计算工作流技术的发展,近来关于多DAG(Directed Acyclic Graph)共享资源调度的研究取得了一些进展,然而,关于具有最晚完成期限约束的多DAG共享一组有限异构资源的调度及其费用最低化等问题还有待进一步研究和解决.针对这些问题,文中首先提出了衡量DAG期限紧急水平的"相对严格程度"的新方法,并在此基础上提出了基于相对严格程度的调度算法MDRS(Scheduling for Multi-DAGs with Deadline based on Relative Stritness).该算法不仅能够合理处理多个DAG之间调度的紧急水平关系,也能对由于DAG期限过于严格而可能产生的"过饱和"情况进行探测和处理.一旦遇到"过饱和"情况,则采用"堆栈"与"调度回溯"相结合的机制尽可能少地丢弃其中的DAG,从而达到DAG吞吐量最大化调度目标.在MDRS算法的基础上,为了满足各DAG期限内完成约束条件,并尽可能公平地降低多个DAG执行的费用,又提出了基于单位相对严格程度变化量的费用降低率最大化方法的费用优化算法CDVRS(Cost Decrease based on Variance of the Relative Strictness).实验表明:这些方法及算法能够达到较好的性能.     

带限制条件的多权最短路径近似算法

带限制条件的多权最短路径问题具有广泛的用途。该文针对有向图，给出了一个带一个限制条件的多权最短路径的近似算法并且分析了它的时间复杂度。     

基于资源有效度的网格工作流任务调度算法

针对执行时间限制严格的DAG类型网格工作流任务调度问题,考虑到网格环境中存在多个性能相同的网格资源,但其有效度和价格各不相同将会对工作流任务调度产生影响,该文利用有限状态连续时间的Markov过程的数学模型,提出一种网格工作流调度算法。在DAG中的关键路径上资源系统有效度满足用户要求的一定信任水平,选择执行费用相对较低的资源。仿真实验结果验证了算法的有 效性。     

过必经点集且具有额外硬约束的最短路径算法

求解过必经点集的最短路径问题已有多种算法,但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题,提出一种基于深度优先搜索发展的随机搜索算法,由使用者依据现场情况给出数学描述,建模抽象为无向带权图表示;依据路径规划要求定义相关变量,包括路径规划的起点、终点、必经点集以及额外硬约束条件,图信息和节点信息以邻接矩阵的形式保存;搜索过程中对路径的可行性加入额外硬约束条件进行实时判定,最终获得最短路径解。实验仿真和实测结果表明,该算法能有效规避额外硬约束条件下的中间路径,生成合理的最短路径,改善相关问题的可求解性。     

一个有效的延迟费用受限的多路径算法

在集成网络中,服务质量(QoS)的一个重要方面是寻找满足端到端约束的可行路径,从而有效利用网络资源。考虑端到端的延迟约束和传输费用,对宽度优先算法(BFS)进行扩展,提出了满足延迟约束多路径算法K_DCP,并对其进行改进,得到多路径算法K_EDCP。仿真结果显示,两种算法性能良好。     

Time optimal path planning for a wheeled mobile robot

This paper investigates time optimal path planning under kinematic and dynamic constraints for a 2‐DOF wheeled mobile robot (WMR). The dynamic model of a WMR is derived using the Newton–Euler method and the constraints are analyzed. Kinematic constraints are imposed by WMR's nonholonomy and structural limits, while dynamic constraints are due to motor saturation. The path planning is formulated as a two‐stage planning. First, path planning under kinematic constraints is transformed into a pure geometric problem. The shortest path composed of circular arcs and straight lines is obtained. Then, a time optimal velocity profile is generated under dynamic constraints. Since constraints of a WMR are fully exploited, the proposed method is simple and effective. Simulation results are demonstrated. © 2000 John Wiley & Sons, Inc.     

一种满足时延和时延抖动约束的多播路由算法

多播路由已有广泛的应用,但对于实时多播应用,多播路由的同时必须提供QoS保证。为此,论文研究带有时延和时延抖动约束的多播路由问题,通过对Dijkstra最短路径算法的扩展,提出一个快速有效的满足时延和时延抖动约束的多播路由算法EDDVCMR。实验结果表明,对解决带有时延和时延抖动约束的多播路由问题,该算法与DVMA算法相比,有高出7%的求解成功率,同时,算法执行的CPU时间减少36%。     

附有条件的最短路径算法

分析目前最短路径算法特点和存在问题,并讨论附有条件的最短路径问题.以邻接矩阵为数据存储结构,在迪杰斯特拉(Dijkstra)最短路径算法的基础上,提出了附有条件的最短路径算法.最后,通过实例进行算法测试和比较.算法测试表明:附有条件的最短路径算法是完全可行和有效的.     

IT项目进度计划风险量化预测方法

针对IT项目进度基线定义质量普遍偏低的问题,提出了一种资源约束条件下基于蒙特卡洛模拟的进度风险量化评估方法．首先,考虑资源对进度的限制问题,提出资源约束条件下的活动历时抽样方法;其次,提出在活动历时随机变化情况下,项目关键路径动态识别方法,研究项目工期概率分布问题．最后,通过实例表明,资源约束条件下的蒙特卡洛模拟方法,能够有效地评估IT项目中的进度风险,辅助项目决策．     

通信距离约束下异构水下爬游机器人任务分配

为了保证执行任务的水下爬游机器人之间时刻保持信息交互,提出了一种带通信距离约束的异构水下爬游机器人集群任务分配方法;首先,建立了异构水下爬游机器人集群的任务分配数学模型;其次,分析了多水下爬游机器人通信距离、航程等约束条件;最后,采用蚁群优化算法对异构水下爬游机器人集群的任务分配问题进行求解,在满足约束条件情况下实现了多爬游机器人总航行距离最短;仿真验证了该方法在通信距离约束下实现多水下爬游机器人任务分配的有效性.     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem.     

Distributed shortest-path protocols for time-dependent networks

 This paper addresses algorithms for networks whose behavior changes with time according to known functions. Because the computation depends on the same functions it attempts to compute, its execution must obey strict timing constraints. When distributed versions of such algorithms are considered, a key difficulty is how to transfer local timing functions among the participating nodes. To that end it is necessary to characterize the parameterization of the functions and accommodate this parameterization in the computation. In particular, we consider the shortest-path problem in networks in which the delay of the edges changes with time according to continuous functions. We present distributed protocols for finding the shortest and minimum delay path under various waiting constraints. We investigate and analyze protocols that exchange local time-delay functions only within limited intervals yet allow every node to calculate its representation in the shortest path in time for it to be used. Received: November 1992 / Accepted: December 1995