import?java.util.*;
public?class?TSP{
public?static?final?int?snumber?=?100;
public?int?[][]value?=?new?int[snumber][snumber];//存放城市之間路徑的權(quán)值
public?static?final?int?number?=?snumber?;//城市數(shù)目
public?static?final?int?time?=?20;//遺傳次數(shù)
public?static?final?int?unitNumber?=?4;//種群個(gè)體數(shù)
public?int[]?code?=?new?int[snumber]?;?//編碼數(shù)組

public?int[][]?unit?=?new?int[4][snumber];//個(gè)體
public?int[][]?cunit?=?new?int[4][snumber];//編碼后的個(gè)體
//映射關(guān)系如下（034251）:0?1?2?3?4?5
//unit???0?3?4?2?5?1
//cunit??1?3?3?2?2?1?

public?int[]?adaptValue?=?new?int[4];//各個(gè)個(gè)體的適應(yīng)值

//構(gòu)造函數(shù)
public?TSP（）{
	for（int?i?=?0?;?i?	for（int?i?=?0?;?i?		value[i][i]?=?0;
		for（int?j?=?i?+?1?;?j?	}
	for（int?j?=?0?;?j?		for（int?i?=?0?;?i?	}
}

//編碼函數(shù)
public?void?fcode（int?pos）{
	int?count?=?0;
	for（int?i?=?0?;?i?		for（int?j?=?0?;?j<=?unit[pos][i]?;?j++）count?+=?code[j];
		code[unit[pos][i]]?=??0;
		cunit[pos][i]?=?count?;
		count?=?0;
	}
	for（int?i?=?0?;?i?}

//反編碼函數(shù)
public?void?frcode（int?pos）{
	int?count?=?0;
	for（int?i?=?0?;?i?		int?j;
		for（j?=?0?;?j?			count?+=?code[j];
			if（count?==?cunit[pos][i]）break;
		}
		unit[pos][i]?=?j?-?1;
		code[j]?=?0;
		count?=?0;
	}
	for（int?i?=?0?;?i?}

//檢查函數(shù)
public?boolean?check（int?xpos??int?val??int?pos）{
	for（int?i?=?0?;?i?		if（unit[xpos][i]?==?val）return?false?;
	}
	return?true?;
}

//初始化種群
public?boolean?initCrop（）{
	for（int?i?=?0?;?i?		for（int?j?=?0?;?j?			int?rvalue?;
			while（true）{
				rvalue?=?（int）（Math.random（）*number）;
				//System.out.println（rvalue）;
				if（check（irvaluej））break;
			}
			unit[i][j]?=?rvalue;
		}
		//初始化完成后進(jìn)行編碼
		fcode（i）;?
	}
	return?true?;
}

//適應(yīng)函數(shù)
public?void?fAdaptation（）{
	for（int?pos?=?0?;?pos?		int?sum?=?0;
		for（int?i?=?0?;?i?			sum?+=?value[unit[pos][i]][unit[pos][i+1]];
		}
		sum?+=?value[un