數(shù)學(xué)與計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書課程名稱：算法設(shè)計(jì)與分析-課程設(shè)計(jì)課程代碼：8174123題目：拓?fù)渑判蚺c關(guān)鍵路徑在實(shí)際的應(yīng)用年級(jí)/專業(yè)/班：學(xué)生姓名：學(xué)號(hào):開始時(shí)間：年月日完成時(shí)間：年月日課程設(shè)計(jì)成績(jī)：學(xué)習(xí)態(tài)度及平時(shí)成績(jī)（30）技術(shù)水平與實(shí)際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總分（100）指導(dǎo)教師簽名：年月日e目錄TOC\o"1-5"\h\z\o"CurrentDocument"摘要i\o"CurrentDocument"1引言2\o"CurrentDocument"1.1問題的提出2\o"CurrentDocument"1.2C++語言2\o"CurrentDocument"1.3算法設(shè)計(jì)與分析的地位21.4拓?fù)渑判虻拿枋?\o"CurrentDocument"1.5任務(wù)與分析4\o"CurrentDocument"2設(shè)計(jì)方案4\o"CurrentDocument"2.1問題描述4\o"CurrentDocument"2.2算法描述5\o"CurrentDocument"2.3算法設(shè)計(jì)6\o"CurrentDocument"2.4算法編碼實(shí)現(xiàn)7\o"CurrentDocument"3.系統(tǒng)測(cè)試9\o"CurrentDocument"3.1圖形化界面展示圖及所求解的頂點(diǎn)和路徑9\o"CurrentDocument"3.2算法的時(shí)間復(fù)雜度分析10\o"CurrentDocument"結(jié)論12\o"CurrentDocument"致謝13\o"CurrentDocument"參考文獻(xiàn)14摘要排課問題是現(xiàn)在各個(gè)學(xué)校必須面臨的一個(gè)問題。而且隨著近年來學(xué)生規(guī)模的擴(kuò)招，教育機(jī)構(gòu)的復(fù)雜化，課程各類的多樣化，排課的問題越來越難。盡管目前對(duì)排課采用了程序設(shè)計(jì)的計(jì)算機(jī)智能排課系統(tǒng)，但是仍然存在著這樣或者那樣的問題。最為突出的一個(gè)問題，比如，有一些排課方案，看上去完美無缺，或者效率比較高，甚至達(dá)到了最優(yōu)解,但是具體地去實(shí)施的時(shí)候，發(fā)現(xiàn)整個(gè)課程的設(shè)計(jì)方案有著大的漏洞，經(jīng)常出現(xiàn)的問題是，排課的拓?fù)鋱D出現(xiàn)了一些環(huán)，以至于進(jìn)入了死循環(huán)。該文的目的就是針對(duì)于如何檢測(cè)環(huán)的存在而避免錯(cuò)誤的排課方案。本文采用的算法是基于拓?fù)湫蛄械耐負(fù)渑判蛩惴▽?duì)特定條件的排課問題提出的一種解決方案，具體的實(shí)驗(yàn)結(jié)果是展示出一個(gè)符合條件的課程拓?fù)湫蛄校麄€(gè)算法的設(shè)計(jì)與實(shí)現(xiàn)過程將要用到鄰接表，堆棧等數(shù)據(jù)結(jié)構(gòu)等等。關(guān)鍵詞：有向圖，拓?fù)渑判颍耪n1引言1.1問題的提出自1946年第一臺(tái)計(jì)算機(jī)問世以來，計(jì)算機(jī)產(chǎn)業(yè)的飛速發(fā)展已遠(yuǎn)遠(yuǎn)超出人們對(duì)它的預(yù)料，在某些生產(chǎn)線上，甚至幾秒鐘就能生產(chǎn)出一臺(tái)微型計(jì)算機(jī)，產(chǎn)量猛增，價(jià)格低廉，這就使得它的應(yīng)用范圍迅速擴(kuò)展。如今，計(jì)算機(jī)已深入到人類社會(huì)的各個(gè)領(lǐng)域。計(jì)算機(jī)的應(yīng)用已不再局限于科學(xué)計(jì)算，而更多地用于控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。與這些相應(yīng)，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值處理發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就給程序設(shè)計(jì)帶來一些新的問題。為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特性以及處理對(duì)象之間存在的關(guān)系。這就是“算法設(shè)計(jì)與分析”這門學(xué)科形成和發(fā)展的背景。1.2C++語言C語言本身存在一些局限，例如：C語言不支持代碼重用，C語言對(duì)類型的檢查機(jī)制相對(duì)較弱。為了解決C語言自身所具有的諸多問題，1980年，貝爾實(shí)驗(yàn)室的BjarneStroutstrup博士及其同事開始對(duì)C語言進(jìn)行改進(jìn)和擴(kuò)充，并使C++語言在C語言的基礎(chǔ)上發(fā)展起來。在基本語法特點(diǎn)方面，C++語言保持與C語言兼并，二者沒有本質(zhì)上的差別，大多數(shù)使用C語言編寫的代碼可以在C++語言中直接使用。這也是C++語言很快普及的一個(gè)重要原因。C++語言與C語言的主要區(qū)別是編程思想上的更新，即編碼由面向過程變?yōu)槊嫦驅(qū)ο?，基于此，C++語言引入了類與對(duì)象機(jī)制，包括類的定義，類的繼承與派生，類的多態(tài)性等。在類定義方面，C++語言一方面自定義結(jié)構(gòu)類型進(jìn)行擴(kuò)充，另一方面也支持新的類構(gòu)造。數(shù)據(jù)封裝和隱藏是與類的定義緊密相關(guān)，并且在C++語言中經(jīng)常碰到的現(xiàn)象，也是C++語言中的一大特點(diǎn)。數(shù)據(jù)的封裝和隱藏使重要的內(nèi)部數(shù)據(jù)得到保護(hù)。1.3算法設(shè)計(jì)與分析的地位算法設(shè)計(jì)與分析在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。算法的研究不僅涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)裝置和存取方法等）的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便。因此，可以認(rèn)為算法設(shè)計(jì)與分析是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。在計(jì)算機(jī)科學(xué)中，算法設(shè)計(jì)與分析不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。1.4拓?fù)渑判虻拿枋?.4.1拓?fù)渑判虻幕舅枷耄簩?duì)于學(xué)生選修課程問題：頂點(diǎn)——表示課程；有向弧——表示先決條件，若課程i是j的先決條件，則圖中有弧＜i,j＞。學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)一一拓?fù)渑判颉OV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexnetwork)，簡(jiǎn)稱AOV網(wǎng)。若＜vi,vj＞是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼；AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件。拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程叫拓?fù)渑判?。檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)。1.4.2設(shè)計(jì)拓?fù)渑判虻牟襟E：1、在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之；1、從圖中刪除該頂點(diǎn)和所有以它為尾的孤；3、重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。1.4.3拓?fù)渑判騿栴}的特征：拓?fù)渑判虻挠行砸蕾囉趫D本身所具有的兩個(gè)重要性質(zhì)：有向和無環(huán)。1、有向：任務(wù)之間有先后關(guān)系，即有方向。2、無環(huán)：若有環(huán)，回路中就會(huì)存在彼此矛盾的條件。在項(xiàng)目管理中，關(guān)鍵路徑是指網(wǎng)絡(luò)終端元素的元素的序列，該序列具有最長(zhǎng)的總工期并決定了整個(gè)項(xiàng)目的最短完成時(shí)間。關(guān)鍵路徑的工期決定了整個(gè)項(xiàng)目的工期。任何關(guān)鍵路徑上的終端元素的延遲將直接影響項(xiàng)目的預(yù)期完成時(shí)間(例如在關(guān)鍵路徑上沒

有浮動(dòng)時(shí)間)。一個(gè)項(xiàng)目可以有多個(gè)，并行的關(guān)鍵路徑。另一個(gè)總工期比關(guān)鍵路徑的總工期略少的一條并行路徑被稱為次關(guān)鍵路徑。最初，關(guān)鍵路徑方法只考慮終端元素之間的邏輯依賴關(guān)系。關(guān)鍵鏈方法中增加了資源約束。用頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間的有向圖叫AOE(ActivityOnEdgeNetwork)網(wǎng)。AOE網(wǎng)常用于估算工程完成時(shí)間。1.4.5設(shè)計(jì)關(guān)鍵路徑的步驟:輸入e條弧<j,k>，建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)。從源點(diǎn)v1出發(fā)，令ve(1)=0,求ve(j)2<=j<=n。從匯點(diǎn)vn出發(fā)，令vl(n)=ve(n),求vl(i)1<=i<=n-1。根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s(活動(dòng))的最早開始時(shí)間e(s)和最晚開始時(shí)間l(s)，其中e(s)=l(s)的為關(guān)鍵活動(dòng)。1.4.6關(guān)鍵路徑問題的特征:求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行，有環(huán)圖不能求關(guān)鍵路徑;只有縮短關(guān)鍵活動(dòng)的工期才有可能縮短工期；若一個(gè)關(guān)鍵活動(dòng)不在所有的關(guān)鍵路徑上，減少它并不能減少工期；只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動(dòng)才能縮短整個(gè)工期。1.5任務(wù)與分析掌握拓?fù)渑判蛩惴ǖ幕舅枷?，包括有向無環(huán)圖的性質(zhì)和基于拓?fù)渑判虻年P(guān)鍵路徑計(jì)算方法。熟練掌握拓?fù)渑判蚝完P(guān)鍵路徑分析方法。學(xué)會(huì)利用拓?fù)渑判蚝完P(guān)鍵路徑算法解決實(shí)際問題。2設(shè)計(jì)方案2.1問題描述給定一個(gè)有向無環(huán)圖，其存儲(chǔ)形式為如下所示。在此圖中，從入度為0的頂點(diǎn)出發(fā)，刪除此頂點(diǎn)和所有以它為尾的孤；重復(fù)直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。

2.2算法描述算法分析：這道題如果用拓?fù)渑判蚍?，在圖的頂點(diǎn)數(shù)稍大的情況下(比如40,100或者更大)，由階乘可知需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目，故不做討論。如果用其它方法又往往得不到最優(yōu)解。在用拓?fù)渑判蚩紤]圖的問題時(shí)可以自頂向下的分析，自底向上的計(jì)算。核心是從入度為0頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，刪除該頂點(diǎn)和其尾弧。繼續(xù)向下一個(gè)入度為0頂點(diǎn)做刪除操作，直到全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。具體步驟如下：Stepl：存儲(chǔ)信息，將鄰接矩陣數(shù)據(jù)存放到數(shù)組charindegree[40]中。Step2:階段劃分，對(duì)于拓?fù)渑判騿栴}應(yīng)該從上而下逐層決策，這樣逐層遞推求出最后結(jié)果。Step3：關(guān)鍵路徑的存儲(chǔ)，用indegree[][]存儲(chǔ)各個(gè)路徑的最優(yōu)值，用TopologicalOrder[][]存儲(chǔ)路徑。indegree[i][j]初始化charindegree[i][j],TopologicalOrder[i][j]初始化0，TopologicalOrder[i][j]=0為向左，等于1為向右。Step4：信息的輸出，路徑最優(yōu)質(zhì)為TopologicalOrder[1][1],路徑輸出為：if(count<G.vexnum)returnERROR;//該有向網(wǎng)有回路elsereturnOK;for(j=0;j<G.vexnum;++j)//求ee,el和關(guān)鍵活動(dòng)for(p=G.vertices[j].firstarc;p;p=p->nextarc)(k=p->adjvex;dut=p->info;ee=ve[j];el=vl[k]-dut;tag=(ee==el)?，*':，，;printf(j,k,dut,ee,el,tag);//輸出關(guān)鍵活動(dòng)}returnOK;2.3算法設(shè)計(jì)本次實(shí)驗(yàn)程序主要用到二維數(shù)組，以及通過動(dòng)態(tài)規(guī)劃法進(jìn)行比較每個(gè)數(shù)的大小。主要運(yùn)用兩個(gè)for循環(huán)語句實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃，畫出流程圖如下圖2-1所示。

indegree[j]==0)Push(S,j);YN--indegree[k]==0)Push(S,k);ve[j]+p->info>indegree[j]==0)Push(S,j);YN--indegree[k]==0)Push(S,k);ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;建立鄰接表存儲(chǔ)結(jié)構(gòu)并初始化j從n到1循環(huán)i從1到n循環(huán)輸出結(jié)果2.4算法編碼實(shí)現(xiàn)拓?fù)渑判颍篠tatusTopologicalOrder(ALGraphG,Stack&T)(//有向網(wǎng)G采用鄰接表存儲(chǔ)結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時(shí)間ve(全局變量)。//T為拓?fù)湫蛄卸c(diǎn)棧，S為零入度頂點(diǎn)棧。//若G無回路，則用棧T返回G的一個(gè)拓?fù)湫蛄校液瘮?shù)值為OK，否則為ERROR。StackS;intcount=0,k;charindegree[40];ArcNode*p;InitStack(S);FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]for(intj=0;j<G.vexnum;++j)//建零入度頂點(diǎn)棧Sif(indegree[j]==0)Push(S,j);//入度為0者進(jìn)棧InitStack(T);//建拓?fù)湫蛄许旤c(diǎn)棧Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;//初始化while(!StackEmpty(S))(Pop(S,j);Push(T,j);++count;//j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)for(p=G.vertices[j].firstarc;p;p=p->nextarc)(k=p->adjvex;//對(duì)j號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(--indegree[k]==0)Push(S,k);//若入度減為0，則入棧if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;}//for*(p->info)=dut(<j,k>)}//whileif(count<G.vexnum)returnERROR;//該有向網(wǎng)有回路elsereturnOK;}//TopologicalOrder關(guān)鍵路徑：StatusCriticalPath(ALGraphG)(//算法7.14,G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動(dòng)。StackT;inta,j,k,el,ee,dut;chartag;ArcNode*p;if(!TopologicalOrder(G,T))returnERROR;for(a=0;a<G.vexnum;a++)vl[a]=ve[G.vexnum-1];//初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間while(!StackEmpty(T))//按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的vl值for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)k=p->adjvex;dut=p->info;//dut<j,k>if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}//for(j=0;j<G.vexnum;++j)//求ee,el和關(guān)鍵活動(dòng)for(p=G.vertices[j].firstarc;p;p=p->nextarc)(k=p->adjvex;dut=p->info;ee=ve[j];el=vl[k]-dut;tag=(ee==el)?，*':，，;printf(j,k,dut,ee,el,tag);//輸出關(guān)鍵活動(dòng)}returnOK;}//CriticalPath3.系統(tǒng)測(cè)試3.1圖形化界面展示圖及所求解的頂點(diǎn)和路徑給定一個(gè)有向無環(huán)圖，其存儲(chǔ)形式為如下所示。在此圖中，從入度為0的頂點(diǎn)出發(fā)，在每一入度為0的頂點(diǎn)可以選擇向下走還是向右走，一直走到底層。請(qǐng)找出一條關(guān)鍵路徑。輸入樣例(圖)：9輸出樣例：C3;C6;C5;C2;C4;C10;C11.測(cè)試結(jié)果如下：3.2算法的時(shí)間復(fù)雜度分析。定義：如果一個(gè)問題的規(guī)模是n,解這一問題的某一算法所需要的時(shí)間為T(n),它是n的某一函數(shù)T(n)稱為這一算法的“時(shí)間復(fù)雜性”。當(dāng)輸入量n逐漸加大時(shí)，時(shí)間復(fù)雜性的極限情形稱為算法的“漸近時(shí)間復(fù)雜性”。我們常用大O表示法表示時(shí)間復(fù)雜性，注意它是某一個(gè)算法的時(shí)間復(fù)雜性。大O表示只是說有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n”2)，它給你一個(gè)上界，但并不是上確界，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。for(intj=0;j<G.vexnum;++j)//建零入度頂點(diǎn)棧Sif(indegree[j]==0)Push(S,j);//入度為0者進(jìn)棧InitStack(T);//建拓?fù)湫蛄许旤c(diǎn)棧Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;解：建鄰接表：T(n)=O(e)搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)結(jié)論本次課程設(shè)計(jì)，讓我受益匪淺，本次的課程設(shè)計(jì)主要是對(duì)所學(xué)過的知識(shí)進(jìn)行實(shí)踐應(yīng)用，不僅是鞏固了自己所學(xué)的知識(shí)，而且把知識(shí)與實(shí)踐相結(jié)合，使得自己在各個(gè)方面都有所提高。這學(xué)期我所做的課程設(shè)計(jì)是拓?fù)渑判蚺c關(guān)鍵路徑在實(shí)際中的應(yīng)用，在做本次課程設(shè)計(jì)的時(shí)候，自己也相繼遇到了很多問題，很多自己的不足之處也暴露了出來，但是因?yàn)橹懒俗约耗睦镉胁蛔?，所以可以針?duì)不足去彌補(bǔ)，學(xué)到的東西更深刻，更透徹，所以本次課程設(shè)計(jì)使我對(duì)算法有了更好的理解。經(jīng)過這段時(shí)間的上機(jī)實(shí)踐學(xué)習(xí)，我對(duì)C++有了更進(jìn)一步的認(rèn)識(shí)和了解，要想學(xué)好它要重在實(shí)踐，要通過不斷地練習(xí)和上機(jī)編程才能熟練地掌握它。當(dāng)然，在上機(jī)的同時(shí)也要有一定的C++理論知識(shí)，這樣才能使理論和實(shí)踐相互促進(jìn)，在這兩方面都有所提高。與此同時(shí)，我也認(rèn)識(shí)到了算法設(shè)計(jì)的重要性。算法設(shè)計(jì)為我們提供了很好的結(jié)構(gòu)和算法來實(shí)現(xiàn)一些比較難的程序。同時(shí)，它還能幫助我們減少程序在時(shí)間和空間上的花費(fèi)。在許多與編程有關(guān)的地方都要用到算法設(shè)計(jì)的知識(shí)。通過本次課程設(shè)計(jì)，我對(duì)拓?fù)渑判蚝完P(guān)鍵路徑都有了更深的了解，和更加熟練的應(yīng)用。雖然過去編寫程序也經(jīng)常用到拓?fù)渑判颍钱?dāng)時(shí)根本就不了解拓?fù)?/p>