关键路线的确定对于运用关键路线法进行项目管理具有十分重要的意义。本文首先定义了项目管理图模型,然后在此基础上提出了一种基于广度优先遍历的关键路线生成树算法,最后通过对项目管理图模型的研究,实现了对算法的优化。仿真结果表明,该算法能够生成一棵保留根节点到任意节点最大路径信息的树,通过生成的树能够方便地确定关键路线。
Computer Science and Application 计算机科学与应用, 2012, 2, 51-56
doi:10.4236/csa.2012.22010 Published Online June 2012 (doc.guandang.net)
A Critical Path Spanning Tree Algorithm Based on
Breadth-First Traversal*
Dongmei Fu1, Dingfu Lian2
School of Automation, University of Science and Technology, Beijing
Email: liandingfu@126.com
Received: Apr. 21st, 2012; revised: May 14th, 2012; accepted: May 25th, 2012
Abstract: To get critical path is of great significance for the use of critical path method in project management. This paper first defines project management graph model, and then puts forward a critical path spanning tree algorithm based on breadth-first traversal, and then achieves the optimization algorithm through the research of the model. The simula- tion shows that the algorithm can create a tree which keeps the maximum path from the root node to any node in the graph model, and get the critical path easily through the tree.
Keywords: Project Management Graph Model; Spanning Tree; Critical Path; Breadth-First Traversal
基于广度优先遍历的关键路线生成树算法*
付冬梅1,练丁榑2
北京科技大学自动化学院,北京 Email: liandingfu@126.com
收稿日期:2012年4月21日;修回日期:2012年5月14日;录用日期:2012年5月25日
摘 要:关键路线的确定对于运用关键路线法进行项目管理具有十分重要的意义。本文首先定义了项目管理图模型,然后在此基础上提出了一种基于广度优先遍历的关键路线生成树算法,最后通过对项目管理图模型的研究,实现了对算法的优化。仿真结果表明,该算法能够生成一棵保留根节点到任意节点最大路径信息的树,通过生成的树能够方便地确定关键路线。
关键词:项目管理图模型;生成树;关键路线;广度优先遍历
1. 引言
网络计划技术是指用于工程项目的计划与控制的一项管理技术,自二十世纪五十年代兴起以来,网络计划技术已经被许多国家认为是当今最行之有效的、先进的、科学的管理方法。关键路线法(CPM)作为网络计划技术的一个核心工具,实施多年以来在各个领域都得到了普遍的运用,并取得了巨大的成功。该方法用网络图表示各项工作之间的相互关系,通过
*
找出控制项目工期的关键路线,在一定工期、成本、资源条件下获得最佳的计划安排,以达到缩短工期、提高工效、降低成本的目的。
建立项目的网络图模型之后,关键路线的寻找能够采用动态规划方法进行求解[3]。但是,现代工程项目正朝着大型化、规模化的方向发展,与之对应的网络图复杂度也呈指数级增长,动态规划方法面临着网络图存储管理难度大、关键路线计算复杂等挑战[4]。同时,动态规划这类传统方法仅仅对网络图的关键路线进行计算,缺乏对整个网络图模型的研究,从而忽视网络图中许多重要的信息。随着计算机技术的不断
51
[1]
[2]
基金项目:北京市教育委员会重点学科共建项目资助(xk100080537)。
Copyright © 2012 Hanspub
27 摘要 很多涉及图上操作的算法都是以图的遍历操作...关键字:图、深度优先遍历、广度优先遍历、生成树。 ...[]存储最短路径的前一个结点 int i,j,k,min; ...
17 1 摘 要 很多涉及图上操作的算法都是以图的...关键字:图;深度优先遍历;广度优先遍历;生成树 1....图的遍历是从图中某个顶点出发,沿着某条搜索路径对...
沿着某条搜索路径对图中每个顶 点各做一次且仅做...(3)栈在深度优先遍历算法中的作用 )深度优先遍历...广度优先遍历过程 广度优先生成树 G8的广度优先遍历...
深度优先遍历和广度优先遍历图的遍历 数据结构与算法 ---第二十讲北方民族大学 ...另有一些重要 操作,如最短路径问题、最小生成树问题, 操作,如最短路径问题、...
关键词:计算机;图;算法。 图的遍历和生成树的求解 YHT 引 言 很多涉及图的...很多问题都可以用广度优先搜索进行处理、如翻币问题、最短路径问题等。 在计算机...
图的存储方式的相互转换,图的遍历及最小生成树算法_IT/计算机_专业资料。图...(ALGraph ALG)//邻接表广度优先搜索 { int v,u,w; queue <int> Q; for...
一些重要操作的实现, 包括遍历、拓扑排序、关键路径...另有一些重要 操作,如最短路径问题、最小生成树问题...一般算法 下面考虑深度优先遍历的递归实现的一般方法(...
( 行深度优先遍历和广度优先遍历得到的一棵生成树,...实现过程中的关键和难点在于: Kruskal算法在实现过程...以不受屏蔽的通信线路为边构建图,就可以直 接套用...
在广度优先遍历算法中, 在广度优先遍历算法中,需设置一队列 Q,保存已访问的...均有路径相通,删去边(u’,v’) ,便可消除上述回路,同时得到另一 棵生成树 ...
算法设计:深度优先遍历和广度优先遍历实现 深度优先遍历过程 1、图的遍历 和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶 点各做一次...
热门文档