/**
 * @author mtanaka
 */





// 短い巡回経路を求める
function localSearch(distanceMatrix, start, end) {

	var optRoute = new Array();
	var nPoint = distanceMatrix.length;
	var initialRoute = createInitialRoute(nPoint, start, end);
	
	for(var i=0; i<nPoint; i++) optRoute[i]=initialRoute[i];

	startIndex = 0;
	
	while(true) {
		var route = search2OPT(optRoute, distanceMatrix, startIndex, start, end);
		if (route != null) {
			optRoute = route; startIndex++; continue;
		}
		
		route = searchOrOPT(optRoute, distanceMatrix, startIndex, start, end);
		if (route != null) {
			optRoute = route; startIndex++; continue;
		}
		break;
	}
	
	return optRoute;
}

// 初期巡回路を作る
// nPoint: 巡回路の長さ
function createInitialRoute(nPoint, start, end) {

	var i, j, r;
	var lg;
	var test = new Array(); // test[i]は地点iの利用フラグ 
	var route = new Array();	
	
	for(i=0; i<nPoint; i++) test[i]=0;
	test[start] = 1; test[end] = 1;
	route[0] = start; route[nPoint-1] = end;
	
	j=0;
	
	for(i=1; i<nPoint-1; i++) {
		r=rand(0, nPoint-i-1); // 地点jからr個目の空き地点をx[i]とする 
		
		while(test[j] == 1) j = (j+1) % nPoint;
		while(r > 0) {
			r = r-1;
			j = (j+1) % nPoint;
			while(test[j] == 1) j = (j+1) % nPoint;
		}
		test[j] = 1; route[i] = j;
	} 
	return route;

}

// 2-OPTで探索
// route: 現在の経路
// distanceMatrix: 地点間距離の行列
// startIndex: 辺の入れ替えを試す起点のインデックス
// return 改善された経路. 改善されなかったら、null
function search2OPT(route, distanceMatrix, startIndex, start, end) {
	var i0, n;

	i0 = startIndex;
	n = distanceMatrix.length; // 地点数
	
	for(var i=i0; i<i0+n; i++) {              /* 2-OPT近傍の探索 */
		for(var j=i+2; j<i+n-1; j++) {        /* lgtempは長さの増分 */
  
  			var lgtemp = length(i, j, route, distanceMatrix) + length(i+1, j+1, route, distanceMatrix)
					- length(i, i+1, route, distanceMatrix) - length(j, j+1, route, distanceMatrix);

			if(lgtemp < 0) {  /* 改良解の発見 */
				newRoute = new Array();
				for(var l=0; l<n; l++) newRoute[l] = route[l];
			
				for(var k=0; k<(j-i)/2; k++) {         /* 改良解の構成 */
					temp = newRoute[(i+1+k)%n];
					newRoute[(i+1+k)%n] = route[(j-k)%n]; 
					newRoute[(j-k)%n]=temp;
				}
				if(checkRoute(newRoute, start, end)) return newRoute;
			}
		} 
	}
	return null; 
}

// Or-OPTで探索
// route: 現在の経路
// distanceMatrix: 地点間距離の行列
// startIndex: 辺の入れ替えを試す起点のインデックス
// return 改善された経路. 改善されなかったら、null
function searchOrOPT(route, distanceMatrix, startIndex, start, end){
	var i0, n, tm;
	
	i0 = startIndex;
	n = distanceMatrix.length; // 地点数
	tm = new Array(3);

	for(var i=i0; i<i0+n; i++) {             /* Or-OPT近傍の探索 */ 
		for(var k=i+1; k<=i+3; k++) {
			for(j=k+1; j<i+n-1; j++) { /* lgtempは長さの増分 */
				var lg0, lg1, lgtemp;
				lg0 = length(i, i+1, route, distanceMatrix) + length(j, j+1, route, distanceMatrix) + length(k, k+1, route, distanceMatrix);
    			lg1 = length(i, k+1, route, distanceMatrix) + length(j, k, route, distanceMatrix) + length(i+1, j+1, route, distanceMatrix);
			    lgtemp = lg1 - lg0;
				if(lgtemp < 0) {   /* 改良解の発見 */
					/* 改良解の構成 */
					newRoute = new Array();
					for(var l=0; l<n; l++) newRoute[l] = route[l];
					
					for(h=i+1; h<=k; h++) tm[h-i-1] = newRoute[h%n];
					for(h=k+1; h<=j; h++) newRoute[(h-k+i)%n] = newRoute[h%n];
					for(h=0; h<k-i; h++) newRoute[(j-k+i+1+h)%n] = tm[k-i-1-h];

					if(checkRoute(newRoute, start, end)) return newRoute;
				}
				if(k == i+1) continue;
			
				lg1 = length(i, k+1, route, distanceMatrix) + length(j, i+1, route, distanceMatrix) + length(k, j+1, route, distanceMatrix); /* 逆方向の挿入 */
				lgtemp =lg1 - lg0;
				if(lgtemp < 0) { /* 改良解の発見 */
					/* 改良解の構成 */
					newRoute = new Array();
					for(var l=0; l<n; l++) newRoute[l] = route[l];

					for(h=i+1; h<=k; h++) tm[h-i-1] = newRoute[h%n];
					for(h=k+1; h<=j; h++) newRoute[(h-k+i)%n] = newRoute[h%n];
					for(h=0; h<k-i; h++) newRoute[(j-h)%n] = tm[k-i-1-h];

					if(checkRoute(newRoute, start, end)) return newRoute;
				}
			}
		}
	}

	return null;
}

function checkRoute(route, start, end) {
	if(route[0] == start && route[route.length-1] == end)
		return true;
		
	return false;
}


function calcRouteLength(route, distanceMatrix) {
	len = 0;
	for(var i=0; i<distanceMatrix.length-1; i++) {
		len += length(i, i+1, route, distanceMatrix);
	}
	
	return len;
}

function length(i, j, route, distanceMatrix)
{
	var n = distanceMatrix.length;
	var ptx = route[i%n];
	var pty = route[j%n];
	
	var tmp;
	if(ptx >= pty) {
		tmp = ptx;
		ptx = pty;
		pty = tmp;
	}
	
	return distanceMatrix[ptx][pty];
}


/* 区間[min, max]からランダムに整数を選ぶ */
function rand(min, max){
	return Math.floor((max - min + 1) * Math.random() + min)
}