一种模糊关键路径求解新方法*

由于不能用传统的前向计算和后向计算方法求解模糊网络关键路径,通过定义模糊必然关键路径、可能关键路径和不可能关键路径,提出一种求解模糊关键路径的新算法。该算法扩充图的邻接表的存储结构,通过判断每个子模糊网络的关键路径,当成为关键路径的可能性为零时,在节点链表中删除相应的节点,减少下回重复遍历该子路径的次数,从而提高算法执行效率。该算法数据结构形式简单直观,易于实现。     

基于CXPST攻击算法的BGP协议安全性分析

针对CXPST攻击算法存在的一些不符合网络实际情况的假设条件进行了深入研究和分析,重点对CXPST攻击算法中关键路径的选取策略进行了详细的分析,提出了关键路径选取的改进策略,并结合路由器中路由表内容进行分析,使得开展CXPST攻击算法过程中关键路径的选取更有针对性。仿真测试结果表明,文章研究的攻击算法比原始的CXPST攻击算法和单纯改变关键路径选取策略的攻击算法,都更具有实效性,能够导致网络中的骨干路由器更快的进入崩溃状态。     

统一关键路径时延为基准FPGA模拟退火布局算法

传统FPGA模拟退火布局算法中衡量布局质量的时延代价计算是以各自布局的关键路径时延为基础的,在一定条件下并不能准确地反映实际布局变化情况.为此,提出一种统一关键路径时延为基准FPGA模拟退火布局算法.该算法设置了统一关键路径时延基准,通过引入惩戒系数来降低关键路径时延增加的布局方案被接受的概率,根据惩戒系数对关键路径时延收敛效果的影响制定了基准值设置标准,得到了与布局变化相匹配的时延代价函数.实验验证了文中算法的有效性.     

一种求关键路径的新算法

文章提出了一种求关键路径的新算法,该算法数据结构形式简单,求解方便且易于实现,并且算法能求出所有关键路径。用C语言设计了相应的程序验证了此算法。     

基于PathFinder和拆线-重布的FPGA时序布线算法

为了解决当前FPGA布线算法的绕线问题,进一步减少关键路径的延时,提出一种混合PathFinder和拆线-重布的FPGA时序布线算法.在PathFinder时序算法整体布线布通之后,拆掉一些影响关键路径延时的线网路径,再对这些拆掉的线网采用PathFinder算法进行增量布线;在重布的过程中,通过为关键连接和其他连接采用差别化的关键度来专门优化关键连接的路径,从而减少整个关键路径的延时.实验结果表明,与VPR时序驱动布线算法相比,该算法能平均减少12.97%的关键路径延时,而运行时间仅增加了4.87%.     

基于蚁群算法的拥堵交通最短路径研究

针对当前交通网络在路径选择研究中,存在只考虑静态交通网络的路径选择的问题,提出了利用蚁群算法的拥堵交通网络的最短路径算法,建立了采用Petri网的交通网络模型,运用蚁群算法对静态交通网络进行了最短路径求解,并加入天气状况、道路容量等动量建立动态交通网络.运用层次分析法并结合Petri网对交通拓扑图进行了最短路径的探索并进行了对比分析.研究结果表明在道路拥挤的情况下,动态交通网络下的路径算法可以为出行者找到更快捷方便的路线.     

基于动态关键路径的仿真网格资源调度算法

从仿真系统工作流的关键路径分析，确定关键路径上的联邦成员节点，使网格资源调度方面优先获得保证。簦于仿真网格系统运行的复杂性和不确定性，引入了随机规划理论，提出了仿真网格的动态关键路径概念以及基于动态关键路径的资源调度算法，共同解决当资源有限以及任务相关情况下仿真网格的资源调度问题。具体实现，主要使用遗传算法以及MCP算法。仿真实验结果表明，基于动态关键路径的资源调度算法能够优化仿真网格资源的调度。     

一种新的关键路径求解算法

关键路径通常是在拓扑排序的基础上求得的,本文提出了一种新的求关键路径的算法,该算法数据结构形式简单直观,且易于实现。用C语言设计了相应的程序验证了此算法的有效性。     

基于动态规划思想求解关键路径的算法

关键路径通常是在拓扑排序的基础上求得的。提出了一种利用图的广度优先搜索与动态规划算法相结合求解关键路径的新算法,该算法采用图的邻接表结构形式,不需要进行拓扑排序,较传统的算法具有较高的效率,同时具有较高的健壮性。     

交通网络最短路径标号算法的实现与效率分析

标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的D ijkstra算法(D IKBA与D IKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。     

基于任务复制的多关键路径任务调度算法

高效的任务调度算法使多核处理器的资源分配和并行计算能力更加高效。通过研究关键路径对任务调度算法的重要性后提出TDMCP算法。对DAG上关键任务的确定采用一种多关键路径选取的方法,使得关键路径上信息在任务调度的每一步都是实时更新的;保证调度的每一步优先执行紧迫性高的任务;对首任务采用任务复制技术,使得后续任务的调度更加的高效,从整体上提高任务调度效率。和两个经典任务调度算法进行实验性能的比较,比较结果表明TDMCP算法在任务调度时间和算法执行效率方面都要优于两种经典算法。     

AOE网的关键路径求解算法改进及其应用

在项目企业生产管理中,合理估计工期是一个必不可少的环节。而AOE网的关键路径算法是用于此环节的核心方法。文中分析了关键路径算法的传统解决方法,并针对分析结果提出算法的改进方案,从而使算法效率得到提高。并将此算法应用于生产工序的管理中,结果表明了此方案的有效性。     

交通诱导系统中动态路径诱导算法的研究

动态交通网络中两节点之间最优路径的选择是目前的一个重要难题。通过对比不同的静态路径算法,并结合实际交通网络的特点,最终选择以A＊算法为基础,并在此之上研究出实现动态交通网络中路径诱导的方案。     

面向对象技术实现活动网络图及关键路径算法

采用邻接矩阵表示项目活动网络图需要较多的存储空间,且基于结构化程序设计思想实现网络图和关键路径算法都非常繁琐。采用面向对象的类表示活动,基于动态数组表示活动网络图及活动之间的逻辑关系,并据此开发了基于面向对象技术实现关键路径算法的代码,进一步从理论上分析了采用面向对象技术的优势。研究表明,相对于传统的处理方式,基于面向对象技术的项目活动网络图表示及关键路径的算法较大降低了存储和计算的复杂性。     

相关任务图的均衡动态关键路径调度算法

表调度（list scheduling)法是解决任务调度问题的较为有效的方法,该文对两个典型的表调度算法-MCP算法和ETF算法进行了分析,发现它们均存在着一定的不足,文中提出了一个更好的表调度算法BDCP,它采用动态关键路径技术并均衡考虑关键路径结点和非关键路径结点,使得对相关任务图调度长度影响最大的就绪结点能够被优先调度,从而极大地缩短了任务图的调度长度,分析和实验结果表明,BDCP算法要优于MCP和ETF算法。     

基于关键路径优化交叉遗传算法的掌纹识别

传统的掌纹识别算法在大多情况下运行缓慢以致效率不高,通常会依赖昂贵的技术装备而导致成本较高。针对这一问题,提出基于关键路径优化交叉遗传算法(CGA)的掌纹识别算法。首先,利用关键路径算法找到染色体的关键路径,借助于交叉概率剔除染色体的最差候选种群;然后选择最佳候选种群进行交叉运算,有效地改善低质量掌纹图像的问题;最后,在掌纹图像上的实验验证该算法的有效性及可靠性。实验结果表明,相比18项参数总和算法,该算法取得了更高的识别率,同时大大地降低了识别所耗时间,有望运用于实时掌纹识别系统。     

基于关键区间可靠度的网格工作流资源分配算法

目前针对执行时间限制严格的网格工作流资源调度与分配的研究工作已经取得了进展,然而这些工作没有考虑关键路径和非关键路径上任务执行时间的相对差异对资源分配算法产生的影响,这些算法或者仅考虑关键路径任务的资源可靠度问题而降低工作流执行成功率,或者仅考虑所有任务的资源可靠度问题而造成算法的低效率.针对这些问题,提出了一些新的定义,如关键区间和关键区间可靠度;同时也提出了一个新的网格工作流资源分配算法.与现有的分配算法相比,新的分配算法能既能保证限定期限内网格工作流执行成功率,又能提高资源分配效率.仿真结果证明了算法的正确性.     

不确定性交通网络中的top-k路径查询

该文将交通网络抽象为不确定性图模型,并用概率图的方式研究了不确定交通网络中的top-k路径查询,给出了求解概率图中top-k路径查询的数学模型,提出了一种基于遗传算法的不确定性交通网络top-k路径查询算法,并对算法进行了测试,得到了较好的结果。     

关键路径求解的新算法

关键路径通常是在拓扑排序的基础上求得的。文中在按广度优先搜索基础上，提出了一种新的求解关键路径的算法，该算法采用图的十字链表结构形式，不需要进行拓扑排序，算法的时间复杂度为O(n e)，较传统的算法效率更高。     

多核片上系统的高效软硬件划分及调度算法

软硬件划分与调度是软硬件协同设计的关键环节,是经典的组合优化问题。本文针对调度与软硬件划分问题提出一种高效的启发式算法。调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级,出度越大,优先级越高,出度相同的情况下,软件计算时间越大,优先级越高。划分算法首先寻找关键路径,然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环,直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止,这样使得硬件面积的使用率比较高。实验表明,该算法对已有算法的改进可达到38%。