`
若是人间
  • 浏览: 76297 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

java AOE网与关键路径

阅读更多

通常我们用有向图表示一个工程。在这种有向图中,用顶点表示活动,用有向边

<Vi,Vj>表示活动Vi必须先于活动Vj进行。如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动 (ACTIVITY),用有向边上的权值表示活动的持续时间(DURATION),用顶点表示事件(EVENT),则这种的有向图叫做用边表示活动的网 络,简称AOE(active on edges)网络。

  AOE网络在某些工程估算方面非常有用。他可以使人们了解:

     (1):研究某个工程至少需要多少时间?

     (2):那些活动是影响工程进度的关键?

在AOE网络中,有些活动可以并行的进行。从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径 的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,这个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在 这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径(critical path)。

 

java代码实现:

 

Node类:

package com.javaeye.rsrt.regular;

/**
 * 
 * @author nishiting
 *
 */

public class Node {

	private Object data;

	private Node next;
	
	private int weight;
	
	/**
	 * 构造一个节点
	 * @param data	节点的数据,用来标识这个节点
	 * @param next	下一个节点
	 * @param weight	节点的权值,用来表示任务完成所要花费的时间
	 */
	Node(Object data, Node next,int weight) {
		this.data = data;
		this.next = next;
		this.weight = weight;
	}
	
	/**
	 * 
	 * @return 节点标识
	 */

	public Object getData() {
		return data;
	}
	
	/**
	 * 
	 * @param data 节点标识
	 */

	public void setData(Object data) {
		this.data = data;
	}
	
	/**
	 * 
	 * @return 下一个结点
	 */

	public Node getNext() {
		return next;
	}
	
	/**
	 * 
	 * @param next 下一个结点
	 */

	public void setNext(Node next) {
		this.next = next;
	}
	
	/**
	 * 
	 * @return  完成任务所要花费的时间
	 */

	public int getWeight() {
		return weight;
	}
	
	/**
	 * 
	 * @param weight 完成任务所要花费的时间
	 */

	public void setWeight(int weight) {
		this.weight = weight;
	}
	
	

}

 Link类:(用来存储图的链表)

package com.javaeye.rsrt.regular;

public class Link {

	private Node head;
	private int length;
	
	/**
	 * 构造函数,初始化链表
	 * @param index
	 */

	public Link(int index) {
		head = new Node(index, null, 0);
		length = 0;
	}
	
	/**
	 * 增加节点,每次都加在链表的头部
	 * @param item	节点标识
	 * @param weight	完成任务所需要的时间
	 */

	public void addhead(Object item, int weight) {
		Node node = new Node(item, null, weight);
		node.setNext(head.getNext());
		head.setNext(node);
		length++;
	}  
	
	/**
	 * 增加节点,每次都加在链表的尾部
	 * @param item	节点标识
	 * @param weight	完成任务所需的时间
	 */

	public void addtail(Object item, int weight) {
		Node node = new Node(item, null, weight);
		Node temp = head;
		while (null != temp.getNext()) {
			temp = temp.getNext();
		}
		temp.setNext(node);
		length++;
	}
	
	/**
	 * 
	 * @return 链表的头元素
	 */

	public Node head() {
		return head;
	}
	
	/**
	 * 找到指定位置的链表元素
	 * @param index	指定的位置
	 */

	public void find(int index) {
		if (index < 1 || index > length) {
			System.out.print(" 此位置空!");
		}
		Node temp = head;
		for (int i = 0; i < index; i++) {
			temp = temp.getNext();
		}
		System.out.println("链表中第" + index + "个位置的值为" + temp.getData());
	}
	
	/**
	 * 删除指定位置的链表元素
	 * @param index	指定的位置
	 */

	public void delindex(int index) {
		if (index < 1 || index > length) {
			System.out.print("位置不存在!");
		}
		Node temp = head;
		for (int i = 0; i < index - 1; i++) {
			temp = temp.getNext();
		}
		temp.setNext(temp.getNext().getNext());
		length--;

	}
	
	/**
	 * 打印链表的元素
	 */

	public void print() {
		Node temp = head;
		while (null != temp.getNext()) {
			System.out.println(temp.getNext().getData());
			temp = temp.getNext();
		}
		System.out.println("链表长度为:" + length);
	}

}

 Stack类:(栈)

package com.javaeye.rsrt.regular;

/**
 * 栈,遵循先进后出的原则,用来保存元素
 * 
 * @author nishiting
 * 
 */
public class Stack {

	private int[] st;
	private int top;
	private int count;

	/**
	 * 构造一个栈
	 * 
	 * @param size
	 *            栈的大小
	 */
	public Stack(int size) {
		st = new int[size];
		top = -1;
		count = 0;
	}

	/**
	 * 元素进栈
	 * 
	 * @param j
	 *            要进栈的元素
	 */

	public void push(int j) {
		count++;
		st[++top] = j;
	}

	/**
	 * 元素出栈
	 * 
	 * @return 出栈的元素
	 */

	public int pop() {

		return st[top--];
	}

	/**
	 * 查询栈顶元素
	 * 
	 * @return 栈顶元素
	 */

	public int peek() {
		return st[top];
	}

	/**
	 * 查询栈是否为空
	 * 
	 * @return 栈是否为空
	 */

	public boolean isEmpty() {
		count--;
		return (top == -1);
	}

	/**
	 * 查看栈里的所有元素
	 */

	public void list() {

		for (int i = 0; i < count; i++) {

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

		}
		System.out.println();
	}

	/**
	 * 得到栈里一共有多少元素
	 * 
	 * @return 栈里的元素个数
	 */
	public int getCount() {
		return count;
	}

	/**
	 * 查看栈里是否包含某个元素
	 * 
	 * @param i
	 *            要查询的元素
	 * @return 是否包含了要查询的元素
	 */

	public boolean isContains(int i) {
		for (int k = 0; k < st.length; k++) {

			System.out.print("开始比较" + i + "此时的result:");
			list();
			System.out.println();
			if (st[k] == i) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 得到栈里的元素集
	 * @return 栈里的元素集合
	 */
	public int[] getSt(){
		return st;
	}
	
	/**
	 * 返回指定位置的栈元素
	 * @param i	要取得的栈元素所在的位置
	 * @return 指定位置的栈元素
	 */
	public int getElement(int i){
		return st[i];
	}

}

 Vertex类:(顶点)

package com.javaeye.rsrt.regular;

public class Vertex {
	
	public  int in;
	private Object value;
	private boolean isVisited;
	Vertex(Object value){
		this.value = value;
	}
	
	Object value(){
		return value;
	}
	
	
	
}

 Graph类:

package com.javaeye.rsrt.regular;

public class Graph {

	private Vertex[] vertexs;// 节点数组,用来保存结点
	private Link[] adjTab;// 存取图链表
	private int pos = -1;
	private Stack stack;// 栈
	private Stack restack;// 栈的备份
	private Stack backstack;// 栈的备份
	private int vertexNum;// 结点数
	private Node start;
	private int edgeCount;// 记录边的个数
	private int kNum;// 记录关键活动的数量

	private int[] ve;// 事件的最早发生时间
	private int[] vl;// 事件的最迟发生时间
	private int[] e;// 活动的最早发生时间
	private int[] l;// 活动的最晚发生时间
	private int[] key;// 用来存储关键路径

	/**
	 * 构造函数,用来初始化一个图
	 * 
	 * @param size
	 *            图的结点数量
	 */

	public Graph(int size) {
		vertexNum = size;
		vertexs = new Vertex[size];
		adjTab = new Link[size];
		stack = new Stack(size);
		restack = new Stack(size);
		backstack = new Stack(size);
		for (int i = 0; i < size; i++) {
			adjTab[i] = new Link(i);
		}
		ve = new int[size];
		vl = new int[size];
		for (int d = 0; d < size; d++) {
			vl[d] = -1;
		}
		edgeCount = 0;
	}

	/**
	 * 增加结点
	 * 
	 * @param obj
	 *            结点的名称
	 */
	void add(Object obj) {
		/**
		 * 所添加的结点个数必须小于所申请的结点空间
		 */
		assert pos < vertexs.length;
		vertexs[++pos] = new Vertex(obj);
	}

	/**
	 * 增加任务之间的依赖关系和任务运行时间
	 * 
	 * @param from
	 *            被依赖的事件
	 * @param to
	 *            依赖的事件
	 * @param weight
	 *            从被依赖的事件到到依赖的事件之间所要花费的时间
	 */
	void addEdge(int from, int to, int weight) {

		adjTab[from].addtail(to, weight);
		vertexs[to].in++;
		edgeCount++;
	}

	/**
	 * 根据拓扑排序算法判断图是有环的存在
	 * 
	 * @return 是否有环的存在
	 */

	boolean topo() {

		int count = 0;// 用来记录拓扑排序时,没有入度的结点数是否小于节点数

		/**
		 * 扫描顶点表,将入度为0的顶点压栈
		 */

		for (int i = 0; i < vertexNum; i++) {
			if (vertexs[i].in == 0) {
				stack.push(i);
				start = adjTab[i].head();
			}
		}

		/**
		 * 如果栈不为空的话,则进行循环 退出栈顶元素,输出,累加器加1,将顶点的各个邻接点的入度减1,将新的入度为0的顶点入栈
		 * 
		 */

		while (!stack.isEmpty()) {
			/**
			 * 利用restack将栈的拓扑顺序进行备份
			 */
			restack.push(stack.peek());
			/**
			 * 取出栈顶元素,累加器加1
			 */
			int j = stack.pop();
			count++;
			Node p = adjTab[j].head();
			Node earlyest = p;

			/**
			 * 记录当前的事件最早发生时间
			 */
			int preweight = ve[j];

			/**
			 * 将与此节点有关的点的入度减1,若入度减为0,则入栈
			 */
			while (p != null) {
				int k = ((Integer) p.getData()).intValue();
				vertexs[k].in--;
				if (vertexs[k].in == 0)
					stack.push(k);

				/**
				 * 求事件的最早发生时间ve[k]
				 */

				p = p.getNext();
				if (p != null) {

					int temp = ((Integer) p.getData()).intValue();

					/**
					 * 判断新得到的事件最早发生时间是否比原先的事件最早发生时间长 公式:ve[1] = 0; ve[k] =
					 * max{ve[j]+len<vj,vk>}
					 */
					if (p.getWeight() + preweight > ve[temp]) {
						ve[temp] = p.getWeight() + preweight;
					}

				}
			}

		}

		/**
		 * 如果得到的节点数量比原先的结点少,则证明有回路存在
		 */

		if (count < vertexNum) {

			System.out.println("有回路,无法得到关键路径!");
			return false;

		}
		return true;

	}

	/**
	 * 计算出事件最早开始时间,事件最晚开始时间,活动最早开始时间,活动最晚开始时间
	 */

	public void calculate() {

		int s = 0;// 控制e(活动的最早发生时间)的增长
		int t = 0;// 控制l(活动的最迟发生时间)的增长

		/**
		 * 初始化活动的最早开始时间与最迟开始时间
		 */
		e = new int[edgeCount];
		l = new int[edgeCount];
		key = new int[edgeCount];

		/**
		 * 按逆拓扑有序来求其余各顶点的最迟发生时间
		 * 原理:restack里保存着拓扑排序的顺序数列,将从restack里将最后一个节点取出,即没有事件依赖于它的结点
		 * 取出的数放进backstack中,
		 * 再从restack里一个一个取出节点元素,看其是否跟已放入backstack中的元素相连,若有相连,则进行vl的计算,如此重复
		 * 计算公式:vl[k] = min{vl[j]-len<vk,vj>}
		 */
		backstack.push(restack.peek());
		int z = restack.pop();
		vl[z] = ve[z];

		/**
		 * 当记录原拓扑顺序的restack不为空时,则进行循环
		 */
		while (!restack.isEmpty()) {

			/**
			 * 将已经比较完的结点放进backstack中,然后将restack里取出来的值与backstack里的值一一对比
			 */
			backstack.push(restack.peek());
			int q = restack.pop();

			Node vertex = adjTab[q].head();

			for (int k = 0; k < backstack.getCount(); k++) {
				Node ver = vertex;
				while (ver.getNext() != null) {

					/**
					 *查询这个节点的下一个结点是否有backstack里的结点,从而证明两者是否相连
					 */
					if (((Integer) ver.getNext().getData()).intValue() == backstack
							.getElement(k)) {
						int yuanxian = vl[((Integer) vertex.getData())
								.intValue()];
						int jiangyao = vl[backstack.getElement(k)]
								- ver.getNext().getWeight();
						/**
						 *若两点之间相连的话,更新结点的vl值 计算vl的公式是:发vl[n] = ve[n] vl[k] =
						 * min{vl[j]-len<vk,vj>}
						 */
						if (jiangyao < yuanxian || yuanxian == -1) {
							vl[((Integer) vertex.getData()).intValue()] = vl[backstack
									.getElement(k)]
									- ver.getNext().getWeight();
						}

					}
					ver = ver.getNext();
				}

			}

		}

		/**
		 * 求活动的最早开始时间e[i]与活动的最晚开始时间l[i]
		 * 若活动ai是由弧<Vk,Vj>表示,根据AOE网的性质,只有事件vk发生了,活动ai才能开始
		 * 。也就是说,活动ai的最早开始时间应等于事件vk的最早发生时间。 因此有e[i] = ve[k];
		 * 活动ai的最晚开始时间是指,在不推迟整个工期的前提下
		 * ,ai必须开始的最晚开始时间。若ai由有向边<vi,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后
		 * 因此,应该有l[i] = vl[j] - len<vk,vj>
		 */

		for (int h = 0; h < vertexNum; h++) {

			Node begin = adjTab[h].head();
			Node backbegin = begin;
			if (begin != null) {
				/**
				 * 查看所有当前节点的下一个结点
				 */
				while (begin.getNext() != null) {
					e[s++] = ve[((Integer) backbegin.getData()).intValue()];
					l[t++] = vl[((Integer) begin.getNext().getData())
							.intValue()]
							- begin.getNext().getWeight();
					begin = begin.getNext();
				}

			}

		}

		kNum = 0;
		for (int w = 0; w < e.length; w++) {

			if (l[w] - e[w] <= 0) {
				key[kNum++] = w;
			}

		}
	}

	/**
	 * 
	 * @return 事件的最早开始时间
	 */
	public int[] getVE() {
		return ve;
	}

	/**
	 * 
	 * @return 事件的最迟开始时间
	 */
	public int[] getVl() {
		return vl;
	}

	/**
	 * @return 活动的最早开始时间
	 */
	public int[] getE() {
		return e;
	}

	/**
	 * 
	 * @return 活动的最晚开始时间
	 * 
	 */
	public int[] getL() {
		return l;
	}

	/**
	 * 
	 * @return 关键活动的点
	 */
	public int[] getKey() {
		return key;
	}

	/**
	 * 
	 * @return 关键活动的个数
	 */
	public int getKNum() {
		return kNum;
	}
}

 测试类:

package com.javaeye.rsrt.regular;

import com.javaeye.rsrt.regular.Graph;

import junit.framework.TestCase;

public class GraphTest extends TestCase {

	public void testGraph() {

		/**
		 * 测试没有回路的情况
		 * 
		 */
		System.out.println("<!--------测试没有回路的情况-------------->");
		Graph graph = new Graph(9);
		graph.add("a");
		graph.add("b");
		graph.add("c");
		graph.add("d");
		graph.add("e");
		graph.add("f");
		graph.add("g");
		graph.add("h");
		graph.add("i");
		graph.addEdge(0, 1, 6);
		graph.addEdge(0, 2, 4);
		graph.addEdge(0, 3, 5);
		graph.addEdge(1, 4, 1);
		graph.addEdge(2, 4, 1);
		graph.addEdge(3, 5, 2);
		graph.addEdge(4, 6, 9);
		graph.addEdge(4, 7, 7);
		graph.addEdge(5, 7, 4);
		graph.addEdge(6, 8, 2);
		graph.addEdge(7, 8, 4);
		if (graph.topo()) {
			graph.calculate();

			int[] e = graph.getE();
			int[] l = graph.getL();
			int[] key = graph.getKey();
			int[] ve = graph.getVE();
			int[] vl = graph.getVl();

			System.out.println("事件的最早发生时间:");
			for (int w = 0; w < ve.length; w++) {
				System.out.print(ve[w] + "      ");
			}
			System.out.println();

			System.out.println("事件的最晚发生时间:");
			for (int w = 0; w < vl.length; w++) {
				System.out.print(vl[w] + "      ");
			}
			System.out.println();

			System.out.println("活动的最早发生时间:");
			for (int w = 0; w < e.length; w++) {
				System.out.print(e[w] + "      ");
			}

			System.out.println();
			System.out.println("活动的最迟发生时间:");
			for (int w = 0; w < l.length; w++) {
				System.out.print(l[w] + "      ");
			}

			System.out.println();

			System.out.println("关键活动有:");
			for (int w = 0; w < graph.getKNum(); w++) {
				System.out.print(key[w] + "      ");
			}
			System.out.println();

			/**
			 * 测试有回路的情况
			 * 
			 */
			System.out.println("<!--------测试没有回路的情况-------------->");
			graph = new Graph(9);
			graph.add("a");
			graph.add("b");
			graph.add("c");
			graph.add("d");
			graph.add("e");
			graph.add("f");
			graph.add("g");
			graph.add("h");
			graph.add("i");
			graph.addEdge(0, 1, 6);
			graph.addEdge(2, 0, 4);
			graph.addEdge(0, 3, 5);
			graph.addEdge(1, 4, 1);
			graph.addEdge(4, 2, 1);
			graph.addEdge(3, 5, 2);
			graph.addEdge(4, 6, 9);
			graph.addEdge(4, 7, 7);
			graph.addEdge(5, 7, 4);
			graph.addEdge(6, 8, 2);
			graph.addEdge(7, 8, 4);

			if (graph.topo()) {
				graph.calculate();

				int[] e1 = graph.getE();
				int[] l1 = graph.getL();
				int[] key1 = graph.getKey();
				int[] ve1 = graph.getVE();
				int[] vl1 = graph.getVl();

				System.out.println("事件的最早发生时间:");
				for (int w = 0; w < ve.length; w++) {
					System.out.print(ve[w] + "      ");
				}
				System.out.println();

				System.out.println("事件的最晚发生时间:");
				for (int w = 0; w < vl.length; w++) {
					System.out.print(vl[w] + "      ");
				}
				System.out.println();

				System.out.println("活动的最早发生时间:");
				for (int w = 0; w < e.length; w++) {
					System.out.print(e[w] + "      ");
				}

				System.out.println();
				System.out.println("活动的最迟发生时间:");
				for (int w = 0; w < l.length; w++) {
					System.out.print(l[w] + "      ");
				}

				System.out.println();

				System.out.println("关键活动有:");
				for (int w = 0; w < graph.getKNum(); w++) {
					System.out.print(key[w] + "      ");
				}
			}

		}

	}

}
 
4
0
分享到:
评论

相关推荐

    Java 编写的AOE网络求关键路径

    Java编程实现AOE(Arc-Of-Event)网络来寻找关键路径是一种常见的项目管理和工程计划优化技术。AOE网络是一种图形表示法,用于表示任务之间的依赖关系和它们所需的时间,其中节点代表活动,边代表活动之间的顺序关系。...

    数据结构关键路径AOE网

    在这个项目中,我们将使用数据结构中的图来表示关键路径问题,并通过读取字符文件来构建AOE(Activity On Edge)网络,这是一种特殊的有向无环图(DAG),其中边表示活动,节点表示事件。 首先,我们需要理解AOE...

    java做的关于AOE网络的课程设计

    在IT行业中,AOE(Activity On Edge)网络是一种用于项目管理的图形表示法,它源自关键路径方法(CPM)。AOE网络通过图形化展示任务之间的依赖关系,帮助项目经理优化资源分配,确定项目的最短完成时间。在这个Java...

    数据结构课程设计汇本关键路径.doc

    - AOE网用于估计项目的总时间和确定关键路径。 2. **关键路径**: - 关键路径是从项目开始(源点)到结束(汇点)的最长路径,它决定了项目的最短可能完成时间。 - 如果关键路径上的任何活动延误,整个项目完成...

    软考题库试题及其解析.docx

    在AOE网中,有些活动可以并行地进行,完成工程所需的最少时间是从开始点到完成点的最长路径,即关键路径。 * **题目**:程序中凡是引用( )对象的地方都可使用( )对象代替。 A. 基类 B. 派生类 C. 抽象类 D...

    数据结构课程设计(医院选址系统)

    这个系统采用了两种经典路径查找算法:Floyd算法和Dijkstra算法,同时还有AOE网(Activity On Edge Network)用于求解关键路径。 1. **Floyd算法**:也称为Floyd-Warshall算法,是一种解决所有对之间最短路径问题的...

    消息队列.docx

    总的来说,RabbitMQ在分布式系统中扮演着关键角色,通过消息队列实现解耦、异步处理、流量控制等功能,但同时也需要注意其潜在的问题,如性能、消息重复和过期等,合理设计和使用能有效提升系统整体性能和稳定性。

    数据结构大纲.doc

    了解 AOE 网的关键路径算法。 13. 分而治之算法:了解分而治之思想;掌握归并排序、快速排序实现方法。了解选择问题基本思想。 14. 动态规划:掌握所有顶点对时间的最短路径算法。 本文档为考研学生提供了系统的...

    图算法

    5. **关键路径算法**:在项目管理中,AOE网(活动-on-edge)或AOV网(活动-on-vertex)常用来找出完成项目所需的最短时间,关键路径法(CPM)就是解决这类问题的算法。 6. **强连通分量**:对于有向图,判断两个节点...

    2020中国石油大学(华东)数据结构考研初试考试大纲.docx

    图的遍历(深度优先和广度优先)和生成树(如最小生成树)是解决许多问题的基础,如最短路径问题和工程调度(AOV和AOE网络)。查找技术包括顺序查找、折半查找、二叉排序树、B树和B+树以及散列查找,它们都涉及到...

Global site tag (gtag.js) - Google Analytics