關(guān)鍵路徑問題

一、課題內(nèi)容和要求關(guān)鍵路徑問題。二、設(shè)計思路分析（1）選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種方法，要選取一種適當(dāng)?shù)姆椒ńD，才能提高算法效率，降低時間復(fù)雜度和空間復(fù)雜度。（2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。對于給出的事件AOE網(wǎng)絡(luò)，要求求出從起點到終點的所有路徑，經(jīng)分析、比較后找出長讀最大的路徑，從而得出求關(guān)鍵路徑的算法，并給出計算機上機實現(xiàn)的源程序。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。具體要解決的問題有如下四個：1）將項目中的各項活動視為有一個時間屬性的結(jié)點，從項目起點到終點進(jìn)行排列；2）用有方向的線段標(biāo)出各結(jié)點的緊前活動和緊后活動的關(guān)系，使之成為一個有方向的網(wǎng)絡(luò)圖；3）用正推法和逆推法計算出各個活動的最早開始時間，最晚開始時間，最早完工時間和最遲完工時間，并計算出各個活動的時差；4）找出所有時差為零的活動所組成的路線，即為關(guān)鍵路徑；三、概要設(shè)計算法分析：（1）求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行，有環(huán)圖不能求關(guān)鍵路徑;（2）只有縮短關(guān)鍵活動的工期才有可能縮短工期；（3）若一個關(guān)鍵活動不在所有的關(guān)鍵路徑上，減少它并不能減少工期；（4）只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動才能縮短整個工期。（5）關(guān)鍵路徑：從源點到匯點的路徑長度最長的路徑叫關(guān)鍵路徑。（6）活動開始的最早時間e（i）；（7）活動開始的最晚時間l（i）;（8）定義e（i）=l（i）的活動叫關(guān)鍵活動；事件開始的最早時間ve(i)；事件開始的最晚時間vl(i)o設(shè)活動ai由弧<j,k>(即從頂點j到k)表示,其持續(xù)時間記為dut(〈j,k>),則：e(i)=ve(j)1(i)=vl(k)-dut(<j,k>)求ve(i)和vl(j)分兩步：從ve(l)=0開始向前遞推ve(j)=Max(ve(i)+dut(<i,j?)<i,j>T,2<=j<=n其中，T是所有以j為弧頭的弧的集合。從vl(n)=ve(n)開始向后遞推vl(i)=Min(vl(j)-dut(<i,j>))<i,j>S,K=i<=n-1其中，S是所有以i為弧尾的弧的集合。兩個遞推公式是在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。算法步驟：輸入e條孤<j,k>,建立A0E網(wǎng)的存儲結(jié)構(gòu)。從源點vl出發(fā)，令ve(l)=0,求ve(j),2<=j<=no從匯點vn出發(fā),令vl(n)=ve(n),求vl(i)K=i<=n-lo⑷根據(jù)各頂點的ve和vl值，求每條孤s(活動)的最早開始時間e(s)和最晚開始時間1(s),其中e(s)=l(s)的為關(guān)鍵活動。四、詳細(xì)設(shè)計主要函數(shù)的核心代碼：創(chuàng)建圖的函數(shù)求出最大路徑，并打印出關(guān)鍵路徑的函數(shù)球關(guān)鍵路徑的函數(shù)主函數(shù)#include<stdio.h>#include<stdlib.h>#include<iomanip.h>#include〈process.h>typedefstructnode//邊表結(jié)點{intadjvex;〃鄰接點編號intdut;〃弧的信息structnode*next;//下一條弧指針/edgenode;typedefstruct〃頂點表結(jié)點{intprojectname;//頂點域intid;//頂點的入度信息edgenode*link;//邊表頭指針}vexnode;voidCreateGraphic(vexnode*Graphicmap,intprojectnumber,intactivenumber)//創(chuàng)建圖{intbegin,end,duttem;//分別代表弧的前節(jié)點，尾節(jié)點，活動時間edgenode*p;〃邊表頭指針for(inti=0;i<projectnumber;i++){GraphicmapLiLprojectname=i;//頂點的命名按0,1,2,3GraphicmapEi].id=0;//頂點的信息的度數(shù)均賦為零GraphicmapEi].link二NULL;}printf(〃\n");printf("請輸入某項目的信息，并請用整形數(shù)字表示(格式：孤頭，弧尾，權(quán)值)：\n〃)；printfC例如:輸入1,2,4即代表結(jié)點1與4之間的活動需要4個時間單位。\n〃);printf(〃\n");for(intk=0;k<activenumber;k++)//activenumber為活動的數(shù)目，即弧的條數(shù){scanf(〃％d,%d,%d",&begin,&end,&duttem);//請輸入第％d條的起點、終點和權(quán)值p=(edgenode*)malloc(sizeof(edgenode));//臨時分配存儲空間p->adjvex二end-l;〃因為是從零開始記的，姑要減一，就是讓終點插入到鄰接表內(nèi)p->dut=duttem;//該弧的活動時間為duttemGraphicmapLend-1].id++;//入度加一p->next=GraphicmapLbegin~l].link;Graphicmap[begin~1].link=p;〃讓下一■個節(jié)點作為下一插入節(jié)點的前驅(qū)節(jié)點}intSearchMapPath(vexnode*Graphicmap,intprojectnumber,intactivenumber,int&totaltime)〃求出最大路徑，并打印出關(guān)鍵路徑{inti,j,k,m=0;intfront=~l,rear=-l;int*topologystack=(int*)malloc(projectnumber*sizeof(int));//用來保存拓?fù)渑帕衖nt*vl=(int*)malloc(projectnumber*sizeof(int));//用來表不在不推遲整個工程的前提下，VJ允許最遲發(fā)生的時間int*ve=(int*)malloc(projectnumber*sizeof(int));//用來表不Vj最早發(fā)生時間int*1=(int*)malloc(activenumber*sizeof(int));//用來表不活動Ai最遲完成開始時間int*e=(int*)malloc(activenumber*sizeof(int));//表小活動最早開始時間edgenode*p;//邊表頭的指針totaltime=0;//存放整個工程的最短時間for(i=0:i<projectnumber;i++)ve[i]=0;//先把每個工程的最早發(fā)生時間初始化為零for(i=0;i<projectnumber;i++){if(Graphicmap[i].id=0){topologystack[++rear]=i;//讓所有的頭節(jié)點入隊列m++;〃記錄入隊列的頂點個數(shù)}}while(front!=rear){front++;//出隊列j二topologystack[front];//拓?fù)渑判虻墓?jié)點依次出隊列m++;〃記錄入隊列的節(jié)點個數(shù)p二Graphicmap[j].link;〃指向頂點指向的下一個頂點while(p){k=p->adjvex;//鄰接點編號Graphicmap[k].id—;//讓入度減一，相當(dāng)于刪除一個入度為零的前驅(qū)節(jié)點，和相關(guān)的弧if(ve[j]+p->dut>ve[k])//將最長的路徑賦給VE[K]ve[k]=ve[j]+p->dut;if(Graphicmap[k].id=0)//如果入度為零，則入隊列topologystack[++rear]=k;p=p->next;//指向下一個節(jié)點}}if(m<projectnumber)//如果有環(huán)，則不能遍歷每個節(jié)點{printf("\n本程序所建立的圖有回路不可計算出關(guān)鍵路徑!\n〃)；printfC將退出本程序！\n");return0;}totaltime=ve[projectnumber-1];//最短完成時間即為最后一個節(jié)點所累加的時間之和for(i=0;i<projectnumber;i++)vl[i]二totaltime;for(i=projectnumber-2;i>=0;i—)//用逆拓?fù)渑判騺砬蠡顒覣i最遲完成開始時間，即從最后一■個節(jié)點減去最短的時間{j二topologystack[i];p二Graphicmap[j].link;while(p){k=p->adjvex;if((vl[k]-p->dut)<vl[j])vl[j]=vl[k]-p->dut;p=p~>next;}}i=0；printf("\n");printfC|起點|終點|最早開始時間|最遲完成時間|差值|備注\n〃)；for(j=0;j<projectnumber;j++){p=Graphicmap_j].link;while(p){k=p->adjvex;e[++i]=ve[j];l[i]=vl[k]-p->dut;printf("|%4d|%4d|%lld|%lld%3d|Graphicmap[j].projectname~1,Graphicmap[k].projectname+1,e[i],l[i],1[i]-e[i]);if(Hi]=e[i])〃當(dāng)差值為零時，則為關(guān)鍵路徑printf("關(guān)鍵活動<%2d,%4d>，；Graphicmap_j].projectname+1,Graphicmap[kJ.projectname+1);printf("\n");p=p~>next;}}return1;voidseekkeyroot()//求關(guān)鍵路徑的主函數(shù)(intprojectnumber,activenumber,totaltime=0;printf(〃\n");printf(〃輸入符合標(biāo)準(zhǔn)，歡迎進(jìn)入求關(guān)鍵路徑的系統(tǒng)!\n〃)；printf(〃\n");printfC請輸入這個項目的AOE-網(wǎng)的節(jié)點數(shù)：")；scanf&projectnumber);printfC請輸入這個項目的AOE-網(wǎng)的活動個數(shù)：〃);scanf&activenumber);vexnode*Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));CreateGraphic(Graphicmap,projectnumber,activenumber);〃創(chuàng)建鄰接圖SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);//求出最大路徑，并打印出關(guān)鍵路徑printf(〃\n");printf(，z整個工程所用的最短時間為：甄d個單位時間\n〃，totaltime);system("pause");}intmainO(charch;for(;;)(do{system(，，cls，/);printf\n");printfC歡迎進(jìn)入求關(guān)鍵路徑算法程序\n〃)；printf\n");printf"\ns(start)開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)鍵路徑\n〃)；printf(〃\n");printf(exit)退出\n");printf(〃\n");printf請輸入選擇:〃)；scanf("%c",&ch);ch=toupper(ch);}while(ch!='S'&&ch!='E');switch(ch)case'S':seekkeyroot0;break;case'E':return1;}}}程序流程圖:i?u五、測試數(shù)據(jù)及其結(jié)果分析-inlxi1.開始界面i?u-inlxi:\DocumentsandSettings\Administrator\Debug\OO.exeM歡迎進(jìn)入求關(guān)鍵路徑算法程序s<start>開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)鍵路徑e〈exit〉退出請輸入選擇:2.進(jìn)入求關(guān)鍵路徑的系統(tǒng)cCMC:\DocumentsandSettings\Administrator\Debug\OO.exeM歡迎進(jìn)入求關(guān)鍵路徑算法程序開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)鍵路徑〉退出請輸入選擇:S蒂入符合標(biāo)準(zhǔn)，歡迎進(jìn)入求關(guān)鍵路徑的系統(tǒng)?請輸入這個項目的AOE-網(wǎng)的節(jié)點數(shù)：2.輸入節(jié)點數(shù)和活動個數(shù)]□]xJcaMC:\DocumentsandSettings\Administrator\Debug\OO.exefla歡迎進(jìn)入求關(guān)鍵路徑算法程序s<start>開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)鍵路徑e<exit>退出請輸入選擇:s]□]xJ屬貓入這個項目的AOE-網(wǎng)的節(jié)點數(shù)：3請瑞入這個項目的AOE-網(wǎng)的活動個數(shù)：33.輸入某項目的信息（弧頭，弧尾，權(quán)值）4.打印出關(guān)鍵路徑3.輸入某項目的信息（弧頭，弧尾，權(quán)值）4.打印出關(guān)鍵路徑清籟入這個項目的AOE-網(wǎng)的節(jié)點數(shù)：3請輸入這個項目的QOE-網(wǎng)的活動個數(shù)：3|請摘入某項目的信息，并請用整形數(shù)字表示（燼：瓠為，^尾，權(quán)值）:例如扁入L2,4帥代表結(jié)點1與4之間的活就需妻4個時間簞位。1,2,4?35236!起點；終點；最早開始時間；最返完成時間；差值；備注TOC\o"1-5"\h\z:1：3：0:5：5：：1；2；0:0：0：關(guān)鍵沽勵<1,2>\213；4:4101關(guān)犍活動<2,3>整個工程所用的最短時間為：拘個單位時間請按任意鍵繼續(xù)..?六、調(diào)試過程中的問題應(yīng)輸入的數(shù)為整形，若輸入非整形的數(shù)據(jù)，則程序遇到問題關(guān)閉。歡迎進(jìn)入求關(guān)鍵路徑算法程序OO.exes<start>開始輸/00.exe遇到問題需要關(guān)閉.我們對此引起的不便表示抱缺.請輸入選擇:S如果您正處于進(jìn)程當(dāng)中■信息有可能丟失.關(guān)于此錯誤的其他信息，珂入符合標(biāo)準(zhǔn)，.請新入這個項目請輸入這個項目的AOE-網(wǎng)的涪動個數(shù)：3請輸入某項目的信息，并請用整形數(shù)字表示例址:輸入1,2,4即代盛吉點1與4之間的活請單擊此處。調(diào)試但）|，權(quán)值）:七、專業(yè)課程設(shè)計總結(jié)歷時一周的課程設(shè)計終于結(jié)束了，現(xiàn)在來做一下總結(jié)。首先，關(guān)于程序方面，我發(fā)現(xiàn)即使對設(shè)計思路有了眉目，知道了所要用到的數(shù)據(jù)結(jié)構(gòu)、用鄰接表來存儲AOE-網(wǎng)、建立棧來求拓?fù)湫蛄小⑤敵龅耐負(fù)湫蛄械膫€數(shù)少于節(jié)點數(shù)則有回路等等，要把這些方法寫成函數(shù)代碼，其實還是一件非常不容易的事情。再加上要完善設(shè)計思路，構(gòu)造整個程序框架在內(nèi)，都是一件工作量非常大的工作。幸好，有很多資料可以在網(wǎng)路上搜到。所以課程設(shè)計的第一天，我們搜集了很多關(guān)于關(guān)鍵路徑的資料，包括兒種不同思路的程序代碼，以及程序流程。然后我們的工作就變成：看懂并整理這些代碼，然后再其基礎(chǔ)上增加自己需要的功能，按照自己的意愿來修改與完善。在處理程序代碼的時候，有兩個問題始終解決不了。一是程序輸入時只能輸入整形數(shù)據(jù)，而非整形的輸入則會導(dǎo)致程序異常停止，但是因為整形的輸入方式己貫穿整個程序，若要修改只能另外重做整個程序，所以暫不考慮修改，而打算做一個判錯系統(tǒng)，判斷若非整形的輸入則報錯；二是第一種錯誤的解決方案未能成功實行，于網(wǎng)路上搜索到了兒種判斷是否為整形數(shù)據(jù)的程序代碼，但將其修改融合到求關(guān)鍵路徑的程序中，雖然沒有錯誤可以運行，但是卻不能正確的報錯。于是，在嘗試多種方案卻仍不成功的前提下，我只好選擇加上提示語，即：printfC請輸入某項目的信息，并清用整形數(shù)字表示（格式：弧頭，弧尾，權(quán)值）：\n〃）；printfC例如:輸入1,2,4即代表結(jié)