package?tabu;

import?java.io.BufferedReader;
import?java.io.FileInputStream;
import?java.io.IOException;
import?java.io.InputStreamReader;
import?java.util.Random;

public?class?HillClimbing?{

	private?int?MAX_GEN;//?迭代次數(shù)
	private?int?cityNum;?//?城市數(shù)量編碼長度
	private?int[][]?distance;?//?距離矩陣
	private?int?bestT;//?最佳出現(xiàn)代數(shù)
	private?int[]?bestGh;//?最好的路徑編碼
	private?int?bestEvaluation;

	private?Random?random;

	public?HillClimbing（）?{

	}

	/**
	?*?constructor?of?GA
	?*?
	?*?@param?n
	?*????????????城市數(shù)量
	?*?@param?g
	?*????????????運行代數(shù)
	?*?
	?**/
	public?HillClimbing（int?n?int?g）?{
		cityNum?=?n;
		MAX_GEN?=?g;
	}

	//?給編譯器一條指令，告訴它對被批注的代碼元素內(nèi)部的某些警告保持靜默
	@SuppressWarnings（“resource“）
	/**
	?*?初始化HillClimbing算法類
	?*?@param?filename?數(shù)據(jù)文件名，該文件存儲所有城市節(jié)點坐標(biāo)數(shù)據(jù)
	?*?@throws?IOException
	?*/
	private?void?init（String?filename）?throws?IOException?{
		//?讀取數(shù)據(jù)
		int[]?x;
		int[]?y;
		String?strbuff;
		BufferedReader?data?=?new?BufferedReader（new?InputStreamReader（
				new?FileInputStream（filename）））;
		distance?=?new?int[cityNum][cityNum];
		x?=?new?int[cityNum];
		y?=?new?int[cityNum];
		for?（int?i?=?0;?i?			//?讀取一行數(shù)據(jù)，數(shù)據(jù)格式1?6734?1453
			strbuff?=?data.readLine（）;
			//?字符分割
			String[]?strcol?=?strbuff.split（“?“）;
			x[i]?=?Integer.valueOf（strcol[1]）;//?x坐標(biāo)
			y[i]?=?Integer.valueOf（strcol[2]）;//?y坐標(biāo)
		}
		//?計算距離矩陣
		//?針對具體問題，距離計算方法也不一樣，
		//?此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優(yōu)值為10628
		for?（int?i?=?0;?i?			distance[i][i]?=?0;?//?對角線為0
			for?（int?j?=?i?+?1;?j?				double?rij?=?Math
						.sqrt（（（x[i]?-?x[j]）?*?（x[i]?-?x[j]）?+?（y[i]?-?y[j]）
								*?（y[i]?-?y[j]））?/?10.0）;
				//?四舍五入，取整
				int?tij?=?（int）?Math.round（rij）;
				if?（tij?					distance[i][j]?=?tij?+?1;
					distance[j][i]?=?distance[i][j];
				}?else?{
					distance[i][j]?=?tij;
					distance[j][i]?=?distance[i][j];
				}
			}
		}
		distance[cityNum?-?1][cityNum?-?1]?=?0;

		bestGh?=?new?int[cityNum];
		bestEvaluation?=?Integer.MAX_VALUE;
		bestT?=?0;

		random?=?new?Random（System.currentTimeMillis（））;
	}

	//?初始化編碼Ghh
	void?initGroup（）?{
		int?i?j;
		bestGh[0]?=?random.nextInt（65535）?%?cityNum;
		for?（i?=?1;?i?		{
			bestGh[i]?=?random.nextInt（65535）?%?cityNum;
			for?（j?=?0;?j?				if?（bestGh[i]?==?bestGh[j]）?{
					break;
				}
			}
			if?（j?==?i）?{
				i++;
			}
		}
	}

	public?int?evaluate（int[]?chr）?{
		int?len?=?0;
		//?染色體，起始城市城市1城市2...城市n
		for?（int?i?=?1;?i?			len?+=?distance[chr[i?-?1]][chr[i]];
		}
		//?城市n起始城市
		len?+=?distance[chr[cityNum?-?1]][chr[0]];
		return?len;
	}

	//?爬山算法
	public?void?pashan（int[]?Gh?int?T）?{
		int?i?temp?tt?=?0;
		int?ran1?ran2;
		int?e;//?評價新值
		int[]?tempGh?=?new?int[cityNum];
		bestEvaluation?=?evaluate（Gh）;

		//?爬山代數(shù)T
		for?（tt?=?0;?tt?			for?（i?=?0;?i?