數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蚝完P(guān)鍵路徑的求解_第1頁
數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蚝完P(guān)鍵路徑的求解_第2頁
數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蚝完P(guān)鍵路徑的求解_第3頁
數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蚝完P(guān)鍵路徑的求解_第4頁
數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蚝完P(guān)鍵路徑的求解_第5頁
已閱讀5頁,還剩10頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計大作業(yè) 題 目拓?fù)渑判蚝完P(guān)鍵路徑的求解專 業(yè) 計算機科學(xué)與技術(shù) 學(xué)生姓名 學(xué) 號 指導(dǎo)教師 完成日期 2015.3 哈爾濱理工大學(xué)目 錄一:實驗內(nèi)容概述2二:實驗?zāi)康母攀?三:解題思路的描述3四:源程序清單6五:程序調(diào)試及測試結(jié)果11六:結(jié)論13七:參考文獻(xiàn)13拓?fù)渑判蚝完P(guān)鍵路徑的求解【內(nèi)容摘要】建立一個AOV網(wǎng),把對象與對象之間的關(guān)系在AOV網(wǎng)中體現(xiàn)出來,要注意AOV網(wǎng)不可以建立成環(huán)的形式,否則工程將無法進(jìn)行。之后對建立的網(wǎng)進(jìn)行拓?fù)渑判颉τ谝粋€工程來說,不僅要關(guān)心各子工程的之間的先后關(guān)系,還要關(guān)系整個工程的最短時間,即有向帶權(quán)圖的關(guān)鍵路徑問題。在描述關(guān)鍵路徑問題的有向圖時

2、,頂點表示事件,便表示活動,邊上的權(quán)表示活動所需的時間,即此有向圖為AOE網(wǎng)。對AOV網(wǎng)構(gòu)造其所有定點的線性序列,此序列保持網(wǎng)中各頂點間原有的先后關(guān)系,且是原來沒有先后關(guān)系的頂點也成為有先后關(guān)系,這樣的線性序列稱為拓?fù)溆行蛐蛄校瑯?gòu)造AOV網(wǎng)的拓?fù)溆行蛐蛄胁僮鞣Q為拓?fù)渑判?。在AOE網(wǎng)中有些活動可以并行地進(jìn)行,所以完成整個工程的最短時間是從源點到匯點的最長路徑的長度,路徑長度是路徑各邊的權(quán)值之和,把從源點到匯點的最長路徑稱為關(guān)鍵路徑?!娟P(guān)鍵字】AOE網(wǎng) 拓?fù)渑判?關(guān)鍵路徑 The topological sort and critical path method【Abstract】Establis

3、h a AOV nets, the relationship between the object and the object in AOV nets reflected in AOV nets, should pay attention to the form of can't establish cyclization, otherwise the project will not be able to do so. After the nets to establish topological sort.For a project, it should not only abo

4、ut the relationship between the construction of the project, the shortest time relationship, which is the key to the weighted graph routing problem. In the description of the critical path problem digraph, vertices, then said that events, the right side of the time needed to denote activities, namel

5、y, this is to the net. AOE For all its designated AOV network structure, the sequence of linear sequence of each vertex keep the relationship between the original and is originally has no successively relationship has become a vertex, such as linear topological orderly sequences, AOV tectonic sequen

6、ces of topological orderly sequences operation called topological sort. In some activity can AOE net parallel to complete the whole project, so the shortest time from point of origin to the length of the longest path sinks, path length is the path to the sum of the weights, from the point of origin

7、to the longest path called zhonghua critical path.【Key words】AOE net Topological sort The key path 一:實驗內(nèi)容概述采用圖的鄰接表(出邊表)表示方法,實現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的求解過程。使用實現(xiàn)的算法對于圖的AOE網(wǎng),求出各活動的可能的最早開始時間和最晚開始時間。輸出整個工程的最短完成時間是多少?哪些活動是關(guān)鍵活動?說明哪項活動提高速度后能導(dǎo)致整個工程提前完成。二:實驗?zāi)康母攀?AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖,其中,頂點表示事件,弧表示活動,權(quán)表示活動持續(xù)的時間。在AOE網(wǎng)絡(luò)中, 有些活動順序進(jìn)行,

8、有些活動并行進(jìn)行。由于整個工程只有一個開始點和一個完成點,故在正常情況下(無環(huán)),網(wǎng)中只有一個入度為零的點(稱作源點)和一個出度為零的點(叫做匯點).如圖1 圖1AOE網(wǎng)絡(luò)在某些工程估算方面非常有用,為了進(jìn)行人力、物力的調(diào)度和分配,以縮短工期,我們必須找出影響工程進(jìn)度的關(guān)鍵活動,爭取提高關(guān)鍵活動的功效,若網(wǎng)中有多條關(guān)鍵路徑那么只提高一條關(guān)鍵路徑上的關(guān)鍵活動的速度還不能導(dǎo)致整個工程縮短工期,還必須提高同時在所有關(guān)鍵路徑上的活動的速度,因此必須求出所有關(guān)鍵路徑。三:解題思路的描述從源點到各個頂點,以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同

9、,但只有各條路徑上所有活動都完成了,整個工程才算完成。因此,完成整個工程所需的時間取決于從源點到匯點的最長路徑長度,即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(Critical Path)。要找出關(guān)鍵路徑,必須找出關(guān)鍵活動,即不按期完成就會影響整個工程完成的活動。 事件Vi的最早開始時間Ve(i)為源點V1到Vi的最長路徑長度?;顒觓i的最早開始時間e(i),活動ai 的最遲開始時間l(i),e(i)=l(i)的活動叫做關(guān)鍵活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動。因此,只要找到了關(guān)鍵活動,就可以找到。例如,下圖是一個有11項活動的AOE-網(wǎng)。其中有9個事件V1,

10、V2,V9,每個事件表示在它之前的活動已經(jīng)完成,在它之后的活動可以開始。如V1表示整個工程開始,V9表示整個工程結(jié)束,V5表示活動a4和a5已經(jīng)完成,活動a7和a8可以開始。與每個活動相聯(lián)系的數(shù)指的是執(zhí)行該活動所需的時間。如,活動a1需要6天,活動a4需要1天等等。 從源點到匯點的關(guān)鍵路徑為:V1,V2,V5,V8,V9,路徑長度為18,即活動V9的最早發(fā)生時間是18?;顒觓6的最早開始時間是5,最遲開始時間是8,這意味著:活動a6推遲3天開始或者延遲3天完成,都不會影響這個工程的完成。分析:關(guān)鍵路徑上的所有活動都是關(guān)鍵活動,只有提高關(guān)鍵活動的效率,才能縮短整個工期。提前完成非關(guān)鍵活動并不能加

11、快工程進(jìn)度。辨別關(guān)鍵活動就是找l(i)=e(i)的活動。要得到活動的l(i)和e(i),必須先計算事件的最早和最遲發(fā)生時間ve和vl。關(guān)鍵路徑舉例找出圖一中的關(guān)鍵路徑!為了找出關(guān)鍵路徑,需要找出關(guān)鍵活動;因此需要計算每個事件、每個活動的最早開始時間和最晚開始時間。最早開始時間需要從源點開始正向的進(jìn)行計算,而最晚開始時間需要從匯點逆向的開始計算。(a)(b)(c) 圖二:關(guān)鍵路徑的算法: 1  入e條弧j,k,建立AOE-網(wǎng)的存儲結(jié)構(gòu); 2從源點V0出發(fā),令ve0=0,按拓?fù)溆行蚯笃溆喔黜旤c的最早發(fā)生時間veI(1in-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c個數(shù)小于網(wǎng)中頂點數(shù)n,則說明網(wǎng)中

12、存在環(huán),不能求關(guān)鍵路徑,算法終止;否則執(zhí)行步驟(3)。 3從匯點vn出發(fā),令vln-1=ven-1,按逆拓?fù)溆行蚯笃溆喔黜旤c的最遲發(fā)生時間vlI(n-2i0);      4根據(jù)各頂點的ve和vl值,求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某條弧滿足條件e(s)=l(s),則為關(guān)鍵活動。Status criticalpath(algraph g) /G為有向網(wǎng),輸出G的各項關(guān)鍵活動。 If (!topologicalorder(G,t) return ERROR; Vl0.G.vexnum-1=veG.vexnum-1; /初始化頂點事

13、件的最遲發(fā)生時間 While (!stackempty(t) / 按拓?fù)淠嫘蚯蟾黜楛c的vl值 For (pop(t,j),p=g.vexticesj.firstarc;p;p=p->nextarc) K=p->adjvex;dut=*(p->info); /dutj,k If (vlk-dut<vlj) vlj=vlk-dut; for (j=0;j<g.vexnum;+j) /求ee,el和關(guān)鍵活動 for (p=g.verticesj).firstarc;p;p=p->nextarc) k=p->adjvex;dut=*(p->info);

14、ee=vej;el=vlk-dut; tag=(ee=el)?*:”; printf(j,k,dut,ee,el,tag); /輸出關(guān)鍵活動 /criticalpath 四:源程序清單#include<stdio.h>#include<stdlib.h>#include <process.h>#include <ctype.h>typedef struct node /邊表結(jié)點類型 int adjvex; /頂點的序號int dut; /邊上的權(quán)值struct node *next; /指向下一條邊的指針edgenode;typedef stru

15、ct /頂點表結(jié)點 int projectname; /頂點域int id; /頂點入度edgenode *link; /邊表頭指針vexnode;/建立圖存儲結(jié)構(gòu)void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) /projectnumber為工程的節(jié)點數(shù),activenumber int begin,end,duttem; edgenode *p; for(int i=0;i<projectnumber;i+) Gjectname=i; Graphicmapi

16、.id =0; Graphicmapi.link =NULL; printf("某項目的開始到結(jié)束在圖中的工程輸入<vi,vj,dut>n"); printf("如:1 3 6 回車表示第一個工程到第三各工程之間的活動用了6個小時n"); for(int k=0;k<activenumber;k+) scanf("%d %d %d",&begin,&end,&duttem); p=(edgenode*)malloc(sizeof(edgenode); p->adjvex =end-1;

17、/將鄰接點序號j賦給新結(jié)點的鄰接點域 p->dut =duttem; Graphicmapend-1.id +; / 將入度加1 p->next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; /將新結(jié)點插入到頂點vi的邊表頭部/求關(guān)鍵路徑int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) int i,j,k,m=0; int front=-1,rear=-1; int* topologyst

18、ack=(int*)malloc(projectnumber*sizeof(int) ; /用來保存拓?fù)渑帕?int* vl=(int*)malloc(projectnumber*sizeof(int); /用來表示在不推遲整個工程的前提下,VJ允許最遲發(fā)生的時間 int* ve=(int*)malloc(projectnumber*sizeof(int); /用來表示Vj最早發(fā)生時間 int* l=(int*)malloc(activenumber*sizeof(int); int* e=(int*)malloc(activenumber*sizeof(int); /表示活動最早開始時間 e

19、dgenode *p; totaltime=0; for(i=0;i<projectnumber;i+)vei=0; for(i=0;i<projectnumber;i+) if(Graphicmapi.id=0) topologystack+rear=i;m+; while(front!=rear) front+; j=topologystackfront; m+; p=Graphicmapj.link ; while(p) k=p->adjvex ; Graphicmapk.id -; if(vej+p->dut >vek) vek=vej+p->dut

20、 ; if(Graphicmapk.id =0) topologystack+rear=k; p=p->next ; if(m<projectnumber) printf("n本程序所建立的圖有回路不可計算出關(guān)鍵路徑n"); printf("將退出本程序n"); return 0; totaltime=veprojectnumber-1; for(i=0;i<projectnumber;i+) vli=totaltime; for(i=projectnumber-2;i>=0;i-) j=topologystacki; p=Gra

21、phicmapj.link ; while(p) k=p->adjvex ; if(vlk-p->dut )<vlj) vlj=vlk-p->dut ; p=p->next ; i=0;printf("| 起點 | 終點 | 最早開始時間 | 最遲完成時間 | 差值 | 備注 |n"); for(j=0;j<projectnumber;j+) p=Graphicmapj.link; while(p) k=p->adjvex ; e+i=vej; li=vlk-p->dut; printf("| %5d | %5d |

22、 %5d | %5d | %5d |",Gjectname+1,Gjectname +1,ei,li,li-ei); if(li=ei) printf(" 關(guān)鍵活動 |"); printf("n"); p=p->next ; return 1; /尋找關(guān)鍵路徑void seekkeyroot() int projectnumber,activenumber,totaltime=0; system("cls"); printf("請輸入這個工程個數(shù):&qu

23、ot;); scanf("%d",&projectnumber); printf("請輸入這個工程和工程之間的邊數(shù):"); scanf("%d",&activenumber); vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode); CreateGraphic(Graphicmap,projectnumber,activenumber); SearchMapPath(Graphicmap,projectnumber,activenumber

24、,totaltime); printf("整個工程所用的最短時間為:%d個小時n",totaltime); system("pause"); int main() char ch; for(;) do system("cls"); printf(" =n"); printf(" | 歡迎進(jìn)入求關(guān)鍵路徑算法程序 |n"); printf("%s"," (S)tart開始輸入工程數(shù)據(jù)并求出關(guān)鍵路徑n"); printf("%s"," (E)xit退出!n"); printf(" =n"); printf("%s"," 請輸入選擇(S,E):"); scanf("%c",&ch); ch=toupper(ch); while(ch!=&#

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論