关键路径 订阅
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地,从输入到输出的延时取决于信号所经过的延时最大路径,而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用,直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计,提高速度。 [1] 展开全文
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地,从输入到输出的延时取决于信号所经过的延时最大路径,而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用,直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计,提高速度。 [1]
信息
发    明
杜邦公司
别    称
要径法
应用学科
数学 运筹学 计算机
中文名
关键路径
应    用
计划项目活动
外文名
Critical Path
关键路径介绍
关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径,即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期,任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间(例如在关键路径上没有浮动时间)。 [2]  但特殊情况下,如果总浮动时间大于零,则有可能不会影响项目整体进度。一个项目可以有多个、并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。最初,关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。关键路径方法是由杜邦公司发明的。
收起全文
精华内容
下载资源
问答
  • 关键路径

    千次阅读 多人点赞 2017-02-28 10:41:47
    关键路径

    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)。

    如下图所示:



    AOV网与AOE网的比较

    下面是AOV网


    下面是AOE网



    下面介绍几个名词解释:

    etv(Earliest Time Of Vertex):事件最早发生时间,就是顶点的最早发生时间;
    ltv(Latest Time Of Vertex):事件最晚发生时间,就是每个顶点对应的事件最晚需要开始的时间,如果超出此时间将会延误整个工期。
    ete(Earliest Time Of Edge):活动的最早开工时间,就是弧的最早发生时间。
    lte(Latest Time Of Edge):活动的最晚发生时间,就是不推迟工期的最晚开工时间。

    所以可以知道:


    此图的etv和ltv和ete和lte

    如下图:



    由此,可以做出他的邻接表,如下所示:


    所以可以得出他的关键路径:


    代码如下:

    // 边表结点声明
    typedef struct EdgeNode
    {
    	int adjvex;
    	struct EdgeNode *next;
    }EdgeNode;
    
    // 顶点表结点声明
    typedef struct VertexNode
    {
    	int in;			// 顶点入度
    	int data;
    	EdgeNode *firstedge;
    }VertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
    	AdjList adjList;
    	int numVertexes, numEdges;
    }graphAdjList, *GraphAdjList;
    
    int *etv, *ltv;
    int *stack2;			// 用于存储拓扑序列的栈
    int top2;				// 用于stack2的栈顶指针
    
    // 拓扑排序算法
    // 若GL无回路,则输出拓扑排序序列并返回OK,否则返回ERROR
    Status TopologicalSort(GraphAdjList GL)
    {
    	EdgeNode *e;
    	int i, k, gettop;
    	int top = 0;		// 用于栈指针下标索引
    	int count = 0;		// 用于统计输出顶点的个数
    	int *stack;			// 用于存储入度为0的顶点
    	
    	stack = (int *)malloc(GL->numVertexes * sizeof(int));
    	
    	for( i=0; i < GL->numVertexes; i++ )
    	{
    		if( 0 == GL->adjList[i].in )
    		{
    			stack[++top] = i;	// 将度为0的顶点下标入栈
    		}
    	}
    	
    	// 初始化etv都为0
    	top2 = 0;
    	etv = (int *)malloc(GL->numVertexes*sizeof(int));
    	for( i=0; i < GL->numVertexes; i++ )
    	{
    		etv[i] = 0;
    	}
    	stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
    	
    	while( 0 != top )
    	{
    		gettop = stack[top--];		// 出栈
    		// printf("%d -> ", GL->adjList[gettop].data); 
    		stack2[++top2] = gettop;	// 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
    		count++;				
    		
    		for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    		{
    			k = e->adjvex;
    			// 注意:下边这个if条件是分析整个程序的要点!
    			// 将k号顶点邻接点的入度-1,因为他的前驱已经消除
    			// 接着判断-1后入度是否为0,如果为0则也入栈
    			if( !(--GL->adjList[k].in) )	
    			{
    				stack[++top] = k;
    			}
    			
    			if( (etv[gettop]+e->weight) > etv[k] )
    			{
    				etv[k] = etv[gettop] + e->weight;
    			}
    		}
    	}
    	
    	if( count < GL->numVertexes )	// 如果count小于顶点数,说明存在环
    	{
    		return ERROR;
    	}
    	else
    	{
    		return OK;
    	}
    }
    
    // 求关键路径,GL为有向图,输出GL的各项关键活动
    void CriticalPath(GraphAdjList GL)
    {
    	EdgeNode *e;
    	int i, gettop, k, j;
    	int ete, lte;
    	
    	// 调用改进后的拓扑排序,求出etv和stack2的值
    	TopologicalSort(GL);
    	
    	// 初始化ltv都为汇点的时间
    	ltv = (int *)malloc(GL->numVertexes*sizeof(int));
    	for( i=0; i < GL->numVertexes; i++ )
    	{
    		ltv[i] = etv[GL->numVertexes-1];
    	}
    	
    	// 从汇点倒过来逐个计算ltv
    	while( 0 != top2 )
    	{
    		gettop = stack2[top2--];	// 注意,第一个出栈是汇点
    		for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    		{
    			k = e->adjvex;
    			if( (ltv[k] - e->weight) < ltv[gettop] )
    			{
    				ltv[gettop] = ltv[k] - e->weight;
    			}
    		}
    	}
    	
    	// 通过etv和ltv求ete和lte
    	for( j=0; j < GL->numVertexes; j++ )
    	{
    		for( e=GL->adjList[j].firstedge; e; e=e->next )
    		{
    			k = e->adjvex;
    			ete = etv[j];
    			lte = ltv[k] - e->weight;
    			
    			if( ete == lte )
    			{
    				printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
    			}
    		}
    	}
    }


    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,006
精华内容 4,802
关键字:

关键路径