您的位置:

关键路径算法java实现(什么情况下需要使用关键路径算法)

本文目录一览:

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,做为继续查找的开始位置就可以了。

关键路径怎么算

输入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)的为关键活动。

求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期;若一个关键活动不在所有的关键路径上,减少它并不能减少工期;只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。

扩展资料

在项目管理中,编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径,并对各关键活动,优先安排资源,挖掘潜力,采取相应措施,尽量压缩需要的时间。

而对非关键路径的各个活动,只要在不影响工程完工时间的条件下,抽出适当的人力、物力和财力等资源,用在关键路径上,以达到缩短工程工期,合理利用资源等目的。在执行计划过程中,可以明确工作重点,对各个关键活动加以有效控制和调度。

关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助,特别是为项目及其主要活动提供了图形化的显示,这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。

参考资料来源:百度百科-关键路径法

参考资料来源:百度百科-关键路径

JAVA问题求解求速度 http://zhidao.baidu.com/question/206204688.html

功能要求:

1. 选择一个算法(提供选择见下),利用各种方法(图形、动画等)演示算法的演示过程。

2. 可以进行手动演示,也可以自动步进式演示。

3. 允许用户设置算法的各个输入参数,以及自动步进式演示中的时间间隔。

4. 不同的算法输入要求见下。

界面要求:

1. 尽量使用图形界面实现,要符合日常软件使用规范来设计菜单和界面。

2. 如果无法实现图形界面,则在命令行方式下也需要提供菜单,方便用户操作。

其他要求:

1. 标识符命名遵循Windows命名规范。

2. 能够注意各种异常处理,注重提高程序运行效率。

提交内容:

1. 全部源代码。

2. 软件设计和使用说明书(UML类图;实现的功能、主要技术;使用帮助文档)

参考算法:

1. 最小生成树算法:Prim算法、Kruskal算法。允许以下方式输入一个图形:绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。

2. 单源最短路算法:Dijkstra算法。允许以下方式输入一个图形:绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。

3. 最优编码算法:Huffman编码算法。允许用户输入一段英文文字,或者打开一个txt文档(英文内容),据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。

4. 其他可供演示的具有一定难度的算法,如关键路径问题、有向图的极大连通分支等。

图的关键路径

关键概念定义

AOV网 :在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,就是AOV网。

关键路径算法原理 :先求所有顶点的事件最早发生时间(从起点开始计算),如有顶点1和顶点2都到达顶点3,那么顶点3的最早开始时间为max(顶点1 + 路径长度,顶点2 + 路径长度);之后求出所有顶点的时间最迟发生时间(从终点开始计算),如顶点3会到达顶点4和顶点5,那么顶点3的最迟发生时间为min(顶点4 - 路径长度,顶点5 - 路径长度)。比较事件最早发生时间数组和事件最迟发生时间数据,若是对应位置的值相等(即没有可延迟的时间),那么该顶点就是关键路径上的顶点。比较完所有顶点即可输出关键路径。

关键路径怎么求?求详解。

关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序。

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天。

由于整个工程只有一个开始点和一个完成点,故在正常情况(无环)下,网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。

那么该工程待研究的问题是:1.完成整项工程至少需要多少时间?2.哪些活动是影响工程进度的关键?

由于在AOE-网中有些活动可以并行进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。

假设开始点是v1,从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i),这是在不推迟整个工程完成的前提下,活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候,也即是l(i)=e(i)的活动,我们称其为关键活动。显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。

因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的功效,缩短整个工期。

4. 如何实现关键路径?

由上面的分析可知,辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i),首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧j,k表示,其持续时间记为dut(j,k),则有如下关系

e(i) = ve(j)

l(i) = vl(k) - dut(j,k)

求解ve(j)和vl(j)需分两个步进行:

1) 从ve(0)=0开始向前推进求得ve(j)

Ve(j) = Max{ve(i) + dut(i,j) };i,j属于T,j=1,2...,n-1

其中T是所有以第j个顶点为头的弧的集合。

2) 从vl(n-1) = ve(n-1)起向后推进求得vl(j)

vl(i) = Min{vl(j) - dut(i,j};i,j属于S,i=n-2,...,0

其中,S是所有以第i个顶点为尾的弧的集合。

这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说,ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定,而vl(j-1)必须在Vj的所有后继的最迟发生时间求得之后才能确定。因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。

具体算法描述如下:

1. 输入e条弧j,k,建立AOE-网的存储结构。

2. 拓扑排序,并求得ve[]。从源点V0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3。

3. 拓扑逆序,求得vl[]。从汇点Vn出发,令vl[n-1] = ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。

4. 求得关键路径。根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s),则为关键活动。

为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值,需记下在拓扑排序的过程中求得的拓扑有序序列,这就需要在拓扑排序算法中,增设一个栈,以记录拓扑有序序列,则在计算求得各顶点的ve值之后,从栈顶到栈底便为逆拓扑有序序列。

package graph;

import java.util.*;

public class Grph_CriticalPath 

{

Graph_AdjList adjList;

StackInteger T = new StackInteger(); 

int ve[];

int vl[];

final int max = 10000;

public Grph_CriticalPath(Graph_AdjList adjList)                   //图的存储结构是用的邻接表

{

this.adjList = adjList;

int length = adjList.vetexValue.length;

ve = new int[length];

vl = new int[length];

for(int i=0;ilength;i++)

{

ve[i] = 0;

vl[i] = max;

}

}

public void getCriticalPath()

{

topologicalOrder();

int t = T.pop();

T.push(t);

vl[t] = ve[t];

while(!T.isEmpty())

{

int j = T.pop();

for(Graph_AdjList.ArcNode p = adjList.vetex[j].firstArc; p!=null ;p = p.next)

{

int k = p.adjvex;

if(vl[k]-p.weightvl[j])

{

vl[j] = vl[k]-p.weight;

}

}

}

for(int i=0;ive.length;i++)

{

for(Graph_AdjList.ArcNode p = adjList.vetex[i].firstArc; p!=null ;p = p.next)

{

int k = p.adjvex;

int ee = ve[i];

int el = vl[k]-p.weight;

if(ee==el)

{

System.out.print(i+","+k+"     ");

}

}

}

}

public void topologicalOrder()

{

StackInteger S = new StackInteger();

S.push(0);

int count = 0;

while(!S.isEmpty())

{

int j = S.pop();

T.push(j);

count++;

Graph_AdjList.ArcNode p = null;

for(p = adjList.vetex[j].firstArc; p!=null ;p = p.next)

{

int k = p.adjvex;

if(--adjList.degree[k]==0)

{

S.push(k);

}

if(ve[j]+p.weightve[k])

{

ve[k] = ve[j]+p.weight;

}

}

}

if(countadjList.vetexValue.length)

{

System.out.println("图中存在环路!");

return;

}

}

public void print()

{

while(!T.isEmpty())

{

System.out.print(T.pop()+"     ");

}

}

public void printVel()

{

System.out.println();

for(int i=0;ive.length;i++)

{

System.out.print(ve[i]+"    ");

}

System.out.println();

for(int i=0;ivl.length;i++)

{

System.out.print(vl[i]+"    ");

}

}

}

转自:

一个简单的算法演示程序(JAVA语言实现)

还真敢要,别说5分了,5块钱也没人帮你做,自己想办法吧,懒鬼