genalgrthm.java

java编写的最短路径算法

package engine;
public class genAlgrthm {
	
	public static final int MAXCELLS = 40;
	/** Array of current cell x co-ordinates */
	public int xCell[] = new int[MAXCELLS];
	/** Array of current cell y co-ordinates */
	public int yCell[] = new int[MAXCELLS];
	/** Array of current route */
	public int route[] = new int[MAXCELLS + 1];
	/** Array of candidate route */
	public int can_route[] = new int[MAXCELLS + 1];
	/** current cells array */
	public int currentCells[]= new int[MAXCELLS];
	/** current cells number */
//	public int cells;
	/** random times */
	public int iterations;
	/** distance matrix */
//	public double d[][] = new double [40][40];
	public double optimalDistance ; // let it be, primary minimal distance;
	
	public int isChanged=0;

	public int[] optimal=new int[41];
	
	public genAlgrthm(double x, int[] opt){
		optimalDistance=x;
		for (int i=0; i<MAXCELLS + 1; i++){
			optimal[i]=opt[i];
		}
	}
	
	public int [] initialRoute(int r[]){
		for (int i = 1; i < 40; i++){
			route [i] = r [i];
		}
		
//		System.out.print("iterations="+iterations+"\n");
		return route;
	}
	
	
	public void iteration(int cells){
		iterations = 1;
		for(int i = 1; i < cells; i++){
			iterations = iterations * i ;
		}
		iterations+=100;
		
	if (iterations>30000000)
		iterations=30000000;
		
		
	}
	
	public void candidateRoute(int cells){
//		generate a candidate route
		int i = (int)(Math.random()* (cells-1) + 1);
		int j=i;
		while (i==j){
			j = (int)(Math.random()* (cells-1) + 1);
		}
		for (int k = 0; k < cells; k++) {
			if(k == i){
				can_route[k] = route[j];
			}else if(k == j){
				can_route[k] = route[i];
			}else{
				can_route[k] = route[k];
			}
		}
	}
	
	public double calDistance(double d[][],int cells){	
//		calculate the route distance
		double routeDistance = 0; 
		for (int i = 0; i < cells-1; i++) {
			int cell = can_route [i];
			int next_c = can_route [i+1];
			routeDistance = routeDistance + d[cell][next_c];
			}
		int t = can_route [cells-1];
		routeDistance = routeDistance + d[t][0];
		return routeDistance; 
	}
	
	public void newRoute(double d, int cells){
//		keep the route with shorter distance
//		if(d < currentDistance) {
		for( int i = 0; i < cells; i++){
				route [i] = can_route[i];
			
		}
		if (d<optimalDistance){
			isChanged=1;
			optimalDistance=d;
			for (int i=0; i<MAXCELLS + 1; i++){
				optimal[i]=route[i];
			}
			
		}
//		}
	}
	
	
	
}