關鍵路徑演算法java

① 關鍵路徑怎麼算

關鍵路徑的計算方法如下：

（1） 輸入e條弧<j,k>，建立AOE網的存儲結構；

（2） 從源點v1出發，令ve(1)=0，求 ve(j) ,2<=j<=n；

（3） 從匯點vn出發，令vl(n)=ve(n)，求 vl(i), 1<=i<=n-1；

（4） 根據各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關鍵活動。

求關鍵路徑是在拓撲排序的前提下進行的，不能進行拓撲排序，自然也不能求關鍵路徑。

關鍵路徑是指設計中從輸入到輸出經過的延時最長的邏輯路徑。優化關鍵路徑是一種提高設計工作速度的有效方法。一般地，從輸入到輸出的延時取決於信號所經過的延時最大路徑，而與其他延時小的路徑無關。

(1)關鍵路徑演算法java擴展閱讀：

一、拓撲排序的執行

由AOV網構造拓撲序列的拓撲排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。

（1）選擇一個入度為0的頂點並輸出之；

（2）從網中刪除此頂點及所有出邊。

循環結束後，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」信息，否則輸出的頂點序列就是一種拓撲序列。

二、關鍵路徑相關術語

（1）AOE網

用頂點表示事件，弧表示活動，弧上的權值表示活動持續的時間的有向圖叫AOE網。在建築學中也稱為關鍵路線。AOE網常用於估算工程完成時間。一個AOE網的關鍵路徑可以不止一條。

只有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。只有在進入某一頂點的各有向邊所代表的活動都已經結束，該頂點所代表的事件才能發生。

表示實際工程計劃的AOE網應該是無環的，並且存在唯一的入度為0的開始頂點和唯一的出度為0的完成頂點。

（2） 活動開始的最早時間e(i)；

（3） 活動開始的最晚時間l(i)；

（4） 事件開始的最早時間ve(i)；

（5） 事件開始的最晚時間vl(i)。

② 關鍵路徑怎麼求求詳解。

關鍵路徑的演算法是建立在拓撲排序的基礎之上的，這個演算法中用到了拓撲排序。

1． 什麼是拓撲排序？

舉個例子先：一個軟體專業的學生學習一系列的課程，其中一些課程必須再學完它的基礎的先修課程才能開始。如：在《程序設計基礎》和《離散數學》學完之前就不能開始學習《數據結構》。這些先決條件定義了課程之間的領先(優先)關系。這個關系可以用有向圖更清楚地表示。圖中頂點表示課程，有向邊表示先決條件。若課程i是課程j的先決條件，則圖中有弧<i,j>。若要對這個圖中的頂點所表示的課程進行拓撲排序的話，那麼排序後得到的序列，必須是按照先後關系進行排序，具有領先關系的課程必然排在以它為基礎的課程之前，若上例中的《程序設計基礎》和《離散數學》必須排在《數據結構》之前。進行了拓撲排序之後的序列，稱之為拓撲序列。

2． 如何實現拓撲排序？

很簡單，兩個步驟：

1． 在有向圖中選一個沒有前驅的頂點且輸出。

2． 從圖中刪除該頂點和以它為尾的弧。

重復上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。後一種情況則說明有向圖中存在環。

3． 什麼是關鍵路徑？

例子開頭仍然，圖1是一個假想的有11項活動的A0E-網。其中有9個事件v1,v2......，v9，每個事件表示在它之前的活動一完成，在它之後的活動可以開始。如v1表示整個工程的開始，v9表示整個工程結束，v5表示a4和a5已完成，a7和a8可以開始。與每個活動相聯系的數是執行該活動所需的時間。比如，活動a1需要6天，a2需要4天。

packagegraph;
importjava.util.*;
publicclassGrph_CriticalPath
{
Graph_AdjListadjList;
Stack<Integer>T=newStack<Integer>();
intve[];
intvl[];
finalintmax=10000;

publicGrph_CriticalPath(Graph_AdjListadjList)//圖的存儲結構是用的鄰接表
{
this.adjList=adjList;
intlength=adjList.vetexValue.length;
ve=newint[length];
vl=newint[length];
for(inti=0;i<length;i++)
{
ve[i]=0;
vl[i]=max;
}
}

publicvoidgetCriticalPath()
{
topologicalOrder();

intt=T.pop();
T.push(t);
vl[t]=ve[t];
while(!T.isEmpty())
{
intj=T.pop();
for(Graph_AdjList.ArcNodep=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j]=vl[k]-p.weight;
}
}
}
for(inti=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNodep=adjList.vetex[i].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
intee=ve[i];
intel=vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+"");
}

}
}
}

publicvoidtopologicalOrder()
{
Stack<Integer>S=newStack<Integer>();
S.push(0);
intcount=0;
while(!S.isEmpty())
{
intj=S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNodep=null;
for(p=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weight>ve[k])
{
ve[k]=ve[j]+p.weight;
}
}
}
if(count<adjList.vetexValue.length)
{
System.out.println("圖中存在環路！");
return;
}
}

publicvoidprint()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+"");
}
}

publicvoidprintVel()
{
System.out.println();
for(inti=0;i<ve.length;i++)
{
System.out.print(ve[i]+"");
}
System.out.println();
for(inti=0;i<vl.length;i++)
{
System.out.print(vl[i]+"");
}
}


}

轉自：http://blog.csdn.net/pigli/article/details/5777048

③ 關鍵路徑怎麼算

輸入e條弧<j，k>，建立AOE網的存儲結構；從源點v1出發，令ve(1)=0，求 ve(j)，2<=j<=n；從匯點vn出發，令vl(n)=ve(n)，求 vl(i)，1<=i<=n-1。

根據各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關鍵活動。

求關鍵路徑必須在拓撲排序的前提下進行，有環圖不能求關鍵路徑；只有縮短關鍵活動的工期才有可能縮短工期；若一個關鍵活動不在所有的關鍵路徑上，減少它並不能減少工期；只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。

(3)關鍵路徑演算法java擴展閱讀

在項目管理中，編制網路計劃的基本思想就是在一個龐大的網路圖中找出關鍵路徑，並對各關鍵活動，優先安排資源，挖掘潛力，採取相應措施，盡量壓縮需要的時間。

而對非關鍵路徑的各個活動，只要在不影響工程完工時間的條件下，抽出適當的人力、物力和財力等資源，用在關鍵路徑上，以達到縮短工程工期，合理利用資源等目的。在執行計劃過程中，可以明確工作重點，對各個關鍵活動加以有效控制和調度。

關鍵路徑法主要為一種基於單點時間估計、有嚴格次序的一種網路圖。它的出現為項目提供了重要的幫助，特別是為項目及其主要活動提供了圖形化的顯示，這些量化信息為識別潛在的項目延遲風險提供極其重要的依據。

④ 關鍵路徑演算法的時間復雜度

所謂關鍵路徑，就是從工程開始到工程結束所用時間最長的路徑。這是因為，在途中的每一個階段開始之前，都要保證此前的准備工作都已完成，要不然後續工程會無法完成，在尋找路徑時，只能一條路徑一條路徑的比較。本題結果是

⑤ 關鍵路徑法的公式計算

上面介紹了活動的最早和最遲時間的計算方法，以上的過程可以用比較簡單的公式來表達。 上面所講述的方法，我們一般稱為節點計演算法，節點和活動的最早時間按照正推法進行計算，起點節點未規定時間時，我們取其時間為1，即
ETi=1（i=1）
對於任意一個節點，如果其之前只有一條活動時，則其最早時間按照下式計算，
ETj= ETi+Di-j
如果該節點之前有多條活動時，則其最早時間按照下式計算，ETj= max{ETi+Di-j}
其中Di-j為活動i-j的工期
對於活動的最早時間，最早開始時間為：
ESi-j=ETi
最早結束時間為
EFi-j= ESi-j+ Di-j
計劃的總工期
T=ETn-1
節點和活動的最遲時間以逆推法計算，計算時，首先令最後一個節點的最遲時間等於其最早時間，即
LTn=ETn
對於其之後只有一條活動的節點，最遲時間如下式所示
LTi=LTj-Di-j
對於其之後有多條活動的節點，最遲時間如下式所示
LTj=min{ LTj-Di-j}
工作i-j的最遲完成時間以下式計算，
LFi-j=LTj
最遲開始時間為
LSi-j=LFj- Di-j 以上的演算法是節點計演算法，另外，也可以採用一種叫做工作計演算法的方法進行活動時間的計算，具體如下。
對於最早時間，採用正推法計算。在沒有指定節點的開始時間時，則起點開始活動的最早開始時間定為1，即
ESi-j=1
當工作i-j只有一條緊前工作h-i時，其最早開始時間按如下公式計算ESi-j=ESh-i+ Dh-i
當工作i-j有多條緊前工作時，其最早開始時間按照以下公式計算
ESi-j=max {ESh-j+ Dh-i}
工作i-j的最早完成時間按照下式計算
EFi-j=ESi-j+ Di-j
網路計劃的計算工期按照下式確定
T=max {EFi-n}-1
活動的最遲結束時間和最遲開始時間需要採用逆推法計算。
以終點節點為箭頭節點的活動的最遲完成時間按照網路計劃的工期確定，即
LFi-j=T+1
其它活動的最遲開始時間按照下式計算
LFi-j=min {LFj-k- Dj-k}
活動的最遲開始時間以下式確定
LSi-j=LFi-j- Di-j
對於總時差和自由時差可以採用如下的公式計算。
總時差可以按照下式計算：
TFi-j= LSi-j- ESi-j
或者
TFi-j= LFi-j- EFi-j
當工作i-j有緊後工作j-k時，自由時差可以按照下式計算：
FFi-j=ESi-k- ESi-j- Di-j
或者
FFi-j=ESj-k-EFi-j
由於引入了多種邏輯關系，前導圖（PDM）的時間計算和箭線圖（ADM）有一些差別。除了前導圖（PDM）中不存在節點最早時間和最遲時間，在箭線圖（ADM）中提及的其它時間參數也都適合前導圖（PDM）。 對於活動的最早開始和最早結束時間，採用正推法計算，其演算法如下所示：
⒈將第一個活動的最早開始時間設置為1.
⒉在活動的最早開始時間上加上其工期，得到活動的最早結束時間。
⒊根據該活動與後置活動的邏輯關系，計算後置活動應該的最早開始時間，並與其已有的最早開始時間對比，如果其後置活動還沒有設置最早開始時間，則將此時間設為其最早開始時間，如果此時間早於其後置活動已有的最早開始時間，則保留後置活動的原有最早開始時間，如果此時間遲於其後置活動已有的最早開始時間，則將此時間設置為後置活動的最遲開始時間。
⒋重復步驟2和3，直到所有活動的時間被計算完為止。
對於以上所示的最早時間的計算過程，可以以公式的形式表示如下：
當活動間的邏輯關系為SS，則計算如下
ESj=max{ ESi+ STS}
當活動間的邏輯關系為FS，則計算如下
ESj= max{ESi+ Di+ FTS}
當活動間的邏輯關系為FF，計算如下
ESj= max{ESi+ Di- Dj+FTF}
當活動間的邏輯關系為SF，計算如下
ESj=max{ ESi- Dj+STF}
在計算出各個活動的最早開始和結束時間之後，就可以計算活動的自由時差，在計算前導圖（PDM）的自由時差時應注意，由於引入了多種邏輯關系，並且活動間可以存在延時，所以其計算方法與箭線圖（ADM）的計算方法不一樣。 對於前導圖（PDM）的活動間，除了延時還可以存在時間間隔（LAG），一般可以按照下面的方式計算。
當活動間的邏輯關系為SS，則計算如下
LAGi-j= ESj- ESi- STS
當活動間的邏輯關系為FS，則計算如下
LAGi-j= ESj- EFi- FTS
當活動間的邏輯關系為FF，計算如下
LAGi-j= EFj- EFi- FTF
當活動間的邏輯關系為SF，計算如下
LAGi-j= EFj- ESi- STF
則對於任意一個活動，其自由時差為
FFi=min{ LAGi-j}
最後一個活動的自由時差為0.
對於總時差，終點節點的總時差為0，對於其它任意一個節點，總時差按照下式進行計算
TFi=min{TFj+ LAGi-j}
對於任意一個活動的最晚開始時間可以由其最早開始時間加上總時差得到，同樣，其最晚開始時間可以由最早結束時間加上其總時差得到，公式表示如下
LSi=ESi+TFi
LFi=EFi+TFi

⑥ 題目1:一個簡單的演算法演示程序(JAVA語言實現)

1. 選擇一個演算法（提供選擇見下），利用各種方法（圖形、動畫等）演示演算法的演示過程。
2. 可以進行手動演示，也可以自動步進式演示。
3. 允許用戶設置演算法的各個輸入參數，以及自動步進式演示中的時間間隔。
4. 不同的演算法輸入要求見下。
界面要求：
1. 盡量使用圖形界面實現，要符合日常軟體使用規范來設計菜單和界面。
2. 如果無法實現圖形界面，則在命令行方式下也需要提供菜單，方便用戶操作。
其他要求：
1. 標識符命名遵循Windows命名規范。
2. 能夠注意各種異常處理，注重提高程序運行效率。
提交內容：
1. 全部源代碼。
2. 軟體設計和使用說明書（UML類圖；實現的功能、主要技術；使用幫助文檔）
參考演算法：
1. 最小生成樹演算法：Prim演算法、Kruskal演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
2. 單源最短路演算法：Dijkstra演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
3. 最優編碼演算法：Huffman編碼演算法。允許用戶輸入一段英文文字，或者打開一個txt文檔（英文內容），據此文檔內容進行編碼。要求動態列出每個字元的出現概率統計結果以及對應編碼。
4. 其他可供演示的具有一定難度的演算法，如關鍵路徑問題、有向圖的極大連通分支等。

⑦ java關鍵字查詢演算法

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;

public class search
{
//查找方法，參數，文件絕對路徑，查找關鍵字
public static boolean search(String filepath,String key)
{
try
{
File f = new File(filepath);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String s = "";
//int i = 1;
while((s = br.readLine()) != null)
{
if(s.indexOf(key) != -1)
{
return true;
}
}
return false;
}
catch(Exception e)
{
e.printStackTrace();
return false;
}
}
public static void main(String args[])
{
System.out.println(search.search("d://t.txt","l2"));
}
}

修改了下，加兩個變數，可以指出查找的位置。
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;

public class search
{
//查找方法，參數，文件絕對路徑，查找關鍵字
public static String search(String filepath,String key)
{
try
{
File f = new File(filepath);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String s = "";
int i = 1;
int m = 0;
while((s = br.readLine()) != null)
{
if((m = s.indexOf(key)) != -1)
{
return "第"+i+"段,第"+m+"處";
}
i++;
}
return null;
}
catch(Exception e)
{
e.printStackTrace();
return null;
}
}
public static void main(String args[])
{
System.out.println(search.search("d://t.txt","asd"));
}
}

這個，查漢字是沒有問題的。
另外，你要全文檢索的話，indexOf（）還有個方法，indexOf(int start,String key),指定開始查找的位置跟關鍵字，你查到一處後，將這個數值加1，做為繼續查找的開始位置就可以了。