圖論的基本算法-資料下載頁
2024-10-09 15:10本頁面
【正文】 ?請你告訴瘦陀陀回家的最小費用 ?你的程序會接收到多次詢問 ?即對于每對城市 (c1,c2)，你的程序應該立刻給出瘦陀陀從 c1到 c2的最小花費。 分析 ? 胖陀陀規(guī)定必須在最貴的城市舉辦宴會 ?因此不能簡單地選擇一條最短路走 ?若路上有一個花費特別貴的城市 … ? 對于每個點 X，如果在那里辦宴會 … ?如何求最短路？ ?多個詢問怎么處理？ ? floyd計算每兩點的距離？ ? SSSP就可以勝任嗎？ ? AB = AX + XB… 關鍵工程 ? 在大型工程的施工前，我們把整個工程劃分為若干個子工程，并把這些子工程編號為 …… 、 N；這樣劃分之后，子工程之間就會有一些依賴關系，即一些子工程必須在某些子工程完成之后才能施工。由于子工程之間有相互依賴關系，因此有兩個任務需要我們?nèi)ネ瓿桑菏紫龋覀冃枰嬎阏麄€工程最少的完成時間；同時，由于一些不可預測的客觀因素會使某些子工程延期，因此我們必須知道哪些子工程的延期會影響整個工程的延期，我們把有這種特征的子工程稱為關鍵子工程，因此第二個任務就是找出所有的關鍵子工程，以便集中精力管理好這些子工程，盡量避免這些子工程延期，達到用最快的速度完成整個工程。為了便于編程，現(xiàn)在我們假設： （ 1）根據(jù)預算，每一個子工程都有一個完成時間。 （ 2）子工程之間的依賴關系是：部分子工程必須在一些子工程完成之后才開工。 （ 3）只要滿足子工程間的依賴關系，在任何時刻可以有任何多個子工程同時在施工，也既同時施工的子工程個數(shù)不受限制。 （ 4）整個工程的完成是指：所有子工程的完成。 示例 1 序號 完成時間 子工程1 子工程2 子工程3 子工程4 子工程5 子工程1 5 0 0 0 0 子工程2 4 0 0 0 0 子工程3 12 0 0 0 0 子工程4 7 1 1 0 0 子工程5 2 1 1 1 1 約束條件 ? 輸入：第 1行為 N， N是子工程的總個數(shù)， N≤200。 ? 第 2行為 N個正整數(shù)，分別代表子工程 …… 、 N的完成時間。 ? 第 3行到 N+2行，每行有 N1個 0或 1。其中的第 I+2行的這些 0， 1，分別表示“子工程 I”與子工程 … 、 II+ …N 的依賴關系，（ I= …… 、 N）。每行數(shù)據(jù)之間均用空格分開。 ? 輸出：如子工程劃分不合理，則輸出 1；如子工程劃分合理，則用兩行輸出：第 1行為整個工程最少的完成時間。第 2行為按由小到大順序輸出所有關鍵子工程的編號。 求有向圖的關鍵路徑 分析 （ 1）根據(jù)的得到鄰接矩陣對子工程進行拓撲排序。如果該圖能夠進行拓撲排序的話，證明有解，反之則無解。 （ 2）根據(jù)的得到拓撲序列進行動態(tài)規(guī)劃求解，得到工程所需的完成時間。動態(tài)規(guī)劃方程： F[I]=MAX{F[J]}+COST[I] {A[I， J] 0，第 I子工程必須在子工程 J之后完工 } F[I]表示完成子工程 I所需的最早時間， COST[I]表示完成子工程 I所需的時間。 （ 3）根據(jù)的得到的 F序列和拓撲序列，查找關鍵工程。 如果 F[I]=F[J]COST[J]（ A[J， I] 0）的話且第 I個子工程為關鍵工程，那么第 J個子工程也是關鍵工程。初始時，最后完成的一個或多個工程為關鍵工程。 這一道試題的時間復雜度大致為 O(N2)。 算法 思想：求事件的最早開始時間 ve[i]和最遲開始時間 vl[i]。 從 ve(1)=0開始往前遞推 ve(j)=Max{ve(i)+dut(i,j)} 從 vl(n)=ve(n)開始往后遞推 vl(i)=Min{vl(j)dut(i,j)} 算法步驟： 1)輸入 e條弧 j,k建立 AOE網(wǎng)的存儲結構 2)從源點 V1出發(fā) ,令 ve[1]=0，按拓撲有序求其余各定點最早發(fā)生時間 ve[i]。如果得到拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù) n，則說明網(wǎng)中存在環(huán)，不能求關鍵路徑，算法中止；否則執(zhí)行步驟 3 3)從匯點 Vn出發(fā)，令 vl[n]=ve[n]，按逆拓撲有序求其余各定點的最遲發(fā)生時間 vl[i] 4)根據(jù)各定點的 ve和 vl的值求每條弧的最早開始時間 e(s)和最遲開始時間 l(s)。若滿足 e(s)=l(s),則該活動為關鍵活動 求關鍵路徑 PROC critical_path(Var dig:adjlisttp)。 crt_adjlist(dig)。 if not toporder(dig) then writeln(39。Has a cycle39。) else [ vl[1..n]:=ve[n]。 {初始化最遲發(fā)生時間 } while Not empty(top2) Do [ j:=pop(top2)。 k:= firstadj(dig,j)。 while k0 do [ if vl[k]dut(j,k)vl[j] then vl[j]:=vl[k]dut(j,k)。 k:=nextadj(dig,j,k)。 ]
外語相關推薦
鄂ICP備17016276號-1