教育培训机构招生网站建设网站建设与管理实践收获怎么写

教育培训机构招生网站建设,网站建设与管理实践收获怎么写,苏州设计公司有哪些,wordpress设置权限拓扑排序其实就是为了解决一个工程是否能够顺利解决的问题#xff0c;但是我们在解决问题的时候往往需要考虑最短路径的问题#xff0c;而最短路径在工程中往往不是费时最短时间所完成的路径#xff0c;反而是最长时间的路线才是所需要的最短时间。就比如制造一辆汽车#…拓扑排序其实就是为了解决一个工程是否能够顺利解决的问题但是我们在解决问题的时候往往需要考虑最短路径的问题而最短路径在工程中往往不是费时最短时间所完成的路径反而是最长时间的路线才是所需要的最短时间。就比如制造一辆汽车造轮子很快但是制造外壳比较慢那么等到汽车完全制造完毕的时间就取决于耗时最长造外壳的路线。关键路径算法就是为了解决这个问题与拓扑排序不同的是拓扑排序的网中无权值也就是AOV网而关键路径涉及权值也就是AOE网。接下来讲解关键路径的原理我们在下图中的每个顶点记为事件每条弧边记为活动。实现关键路径就是让活动最早开工时间 ete (earliest time of edge)活动最晚开工时间 lte (late time of edge)因为当活动的最早和最晚开工时间一致时说明这个活动是无法拖延的也就是时间最长的工程的完成与否由这几个活动决定 而求活动的时间就要得到事件最早开始的时间etv (earlist time of vertex)和事件最晚开始的时间 ltv (late time of vertex)。由于仍旧是在一个工程中所以我们求活动和事件的时间仍旧需要通过拓扑排序确定简单的说我们进行关键路径的步骤就是先正常的进行一遍拓扑排序找到每个顶点事件的最早开始的时间etv然后再通过逆拓扑排序得到每个顶点事件最晚开始的时间ltv最后由每个事件的最早最晚时间得出活动的最早最晚时间。结合以下图我们具体来看看关键路径的实现过程在最开始的时候我们在每个顶点旁边的事件时间表中先初始化最早开始时间都为0因为后面会再更新。图中的V1有两个出度分别指向了V2和V3V1到V2的边权值是2所以我们就先更新成2。但是不一定是最早的时间我们先暂时更新一下等到顶点再更新时再观察是否有更短的时间可以更新。所以V3也就更新成5然后我们将V1从网中删去得到了下图。此时的V2就成了拓扑的下一个点发现V2也有两个出度分别指向了V3和V4我们再来看V2到V3这条路很显然21 3 5说明到V3之前有更耗时的路因为我们需要找在整个工程中更耗时的路线所以我们就不更新V3中的etv接下来看V4中的数据。23 5 0,所以V4中更新为5再将V2从网中删除结果如下图所示。就这样依次将路径上的权值与前一个结点的最早开始时间相加与后一个结点的最早开始时间进行对比取最耗时的填入etv中最后将所有事件的最早开始时间求出来得到了下图。接下来我们就该求每一个事件最晚的开始时间了最晚开始时间就是逆拓扑排序也就是先找出度为0的点然后删除该结点和头弧寻找下一个出度为0的结点。同时我们将初始的ltv初始化为12因为最后的事件若完成那么整个工程就完成了所以为了不拖延工期最早的开始时间也是最晚的开始时间。所以如下图所示。接下来就是逆拓扑的过程先从V6开始向前面看可以发现V6有三个入度分别是V3、V4、V5。先看V5的ltv的计算就是12-1 11 12所以更新V5的ltv为11为什么现在取的是较小的值呢因为如果这个工程12天完成的话如果V5第12天才开始干的话就会变成121 13 12耽误了一天工期。所以在求最早的时间时选择相加更大的时间更新在求最晚的时间时选选择更短的时间更新。接下来我们看V4减完后就是8再看V3减完后就是11最后的样子如下图所示。在将 V6 删除后无出度的顶点就成了V5 V5的入度有两个分别是V3、V4。接下来仍然是计算部分V4中11 - 1 10 8不更新V3中11 - 4 7 11进行更新更新完的结果如下图所示。剩下的结点同上面一样的步骤最后就能得到事件的最早和最晚开始时间如下图所示最后将数据都放在一个表格中。我们有了事件的时间数据就可以求活动的时间了。首先先看ete简单地说就是活动由谁发出就是发出结点的最早开始时间 。a、b由于都是由V1所发出来的所以最早开始时间就是V1的最早开始时间 0同理c、d都是V2所发出来的所以c、d的最早开始时间就是V2的最早开始时间2同理可得全部活动的最早开始时间ete。接下来看lte简单地说就是活动指向谁就用被指的结点的最晚时间减去边权值。a指向了V2所以就是V2的最晚开始时间4减去边权值2也就是4 - 2 2。b就是V3的最晚开始时间5减去边权值5也就是5 -5 0。同理可得剩下的最晚开始时间lte。此时可以观察到b、e、i三个活动的最早开始时间和最晚开始时间相同所以b、e、i这三个活动的路径就是我们所求的关键路径。接下来则是关键路径的代码实现这里我们需要用到的拓扑排序和之前的拓扑排序有些许的出入下面的代码用注释将新添加的部分标注了出来与之前拓扑排序相同的结构这里就不再给出。int* etv;//事件最早发生时间数组 int* ltv;//事件最晚发生时间数组 int* stack2;//用于存储拓扑序列的栈 int top2;//用于stack2的指针 //拓扑排序若GL无回路则输出拓扑排序序列并返回1若有回路则返回0 Status TopologicalSort(GraphAdjList GL) { EdgeNode* e; int i, k, gettop; int top 0;//用于栈指针下标 int count 0;//用于统计输出顶点的个数 int* stack;//建栈将入度为0的顶点入栈 stack (int*)malloc(GL-NumVertex * sizeof(int)); for (i 0; i GL-NumVertex; i) { if (0 GL-adjlist[i].in)//将入度为0的顶点入栈 { stack[top] i; } } //***********************************添加部分↓************************************************ top2 0;//初始化 etv (int*)malloc(GL-NumVertex * sizeof(int));//事件最早发生实践数组 for (i 0; i GL-NumVertex; i) { etv[i] 0;//初始化 } stack2 (int*)malloc(GL-NumVertex * sizeof(int));//初始化拓扑序列栈 //***********************************添加部分↑************************************************ while (top ! 0) { gettop stack[top--];//出栈 printf(%d - , GL-adjlist[gettop].data);//打印此顶点 count;//统计输出顶点数 //************************************添加部分↓********************************************** stack2[top2] gettop;//将弹出的顶点序号压入拓扑序列的栈 //************************************添加部分↑********************************************** for (e GL-adjlist[gettop].firstedge; e; e e-next);//对此顶点弧表遍历 { k e-adjvex; if (!(--GL-adjlist[k].in))//将k号顶点邻接点的入度减1若为0则入栈以便下次循环输出 { stack[top] k; } //**************************************添加部分↓*********************************************** if ((etv[gettop] e-weight) etv[k])//求各顶点事件的最早发生时间etv的值 { etv[k] etv[gettop] e-weight; } //**************************************添加部分↑*********************************************** } } if (count GL-NumVertex)//count小于顶点数说明存在环 { return ERROR; } else return OK; }新的拓扑序列就只是多了处理事件最早发生时间 etv 和存储拓扑排序用于在主函数中进行逆拓扑的功能整体的改动并不多原理和拓扑是一样的这里不再过多的进行解释。接下来则是关键路径的主体函数//求关键路径GL为有向图 void CriticalPath(GraphAdjList GL) { EdgeNode* e; int i, gettop, k, j; int ete, lte;//活动最早发生时间和最晚发生时间 TopologicalSort(GL);//求拓扑序列计算数组etv和stack2的值 ltv (int*)malloc(GL-NumVertex * sizeof(int));//事件发生最晚时间数组 for (i 0; i GL-NumVertex; i) { ltv[i] etv[GL-NumVertex - 1];//初始化 } while (top2 ! 0) { //计算ltv 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; } } } for (j 0; j GL-NumVertex; j)//求ete,lte和关键活动 { 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 \n, GL-adjlist[j].data, GL-adjlist[k].data, e-weight); } } } }前面的内容仍旧是定义变量然后求得拓扑之后的序列和etv值得注意的是这里对ltv进行初始化第一个结点是以V0开始的 如果以V1开始的话初始化的时候就不需要再进行-1操作了。然后再往下的while循环中就是对拓扑排序的逆过程和求最早最晚的活动我们从stack2中取出度为0的结点然后在for循环中进行计算ltv得出所有的最晚事件的时间后进入后面的for循环中求ete和lte再进行比较得出关键路径。到此有关关键路径的部分就到此结束了。