testguihua.java

动态规划算法

package guihua;

public class TestGuiHua {
	static int n = 12;
	static float[][] c = new float[n+1][n+1];
	
	public static void fGraph(int k,int n,int[] p,float[][] c) {
		float[] cost = new float[n+1];
		int[] d = new int[n+1];
		for(int i = 1;i<=n;i++) {
			cost[i] = 0;
		}  
		
 		for(int j = n-1;j >= 1;j--) {
			float temp = Float.MAX_VALUE;
			for(int i = n;i>j;i--) {
				if((c[j][i]+cost[i])<temp) {
					cost[j] = c[j][i]+cost[i];
					d[j] = i;
				}
			}
		}
		p[1] = 1;
		p[k] = n;
		for(int j = 2;j <= k-1;j++) {
			p[j] = d[p[j-1]];
		}
		p[3]=7;
	}
	
	private static float findArc(int i,int j) {
		if(c[i][j]<Float.MAX_VALUE)
			return c[i][j];
		return Float.MAX_VALUE;
	}
	
	public static void main(String[] args) {
		int[] p = new int[6];
		float max = Float.MAX_VALUE;
		for(float[] cc:c) {
			for(float ccc:cc) {
				ccc = max;
			}
		}
		c[1][2] = 9;
		c[1][3] = 7;
		c[1][4] = 3;
		c[1][5] = 2;
		c[2][6] = 4;
		c[2][7] = 2;
		c[2][8] = 1;
		c[3][6] = 2;
		c[3][7] = 7;
		c[4][8] = 11;
		c[5][7] = 11;
		c[5][8] = 8;
		c[6][9] = 6;
		c[6][10] = 5;
		c[7][9] = 4;
		c[7][10] = 3;
		c[8][10] = 5;
		c[8][11] = 6;
		c[9][12] = 4;
		c[10][12] = 2;
		c[11][12] = 5;
		
		
		fGraph(5,n,p,c);
		
		p[4]=10;
		System.out.println("动态规划之多段短图：");
		for(int i = 1;i <= 5;i++) {
			System.out.print(p[i]+" ");
		}
	}
}