[v2] Brute Force Random Traveling Salesman solver

index.html

	<div class="left">
		<h1>Input</h1>
		<div id="input"></div>
		<hr />
		<h1>Distance Table</h1>
		<div id="distance"></div>
    <hr/>
    <div class="left">
    <h1>Lowest Solution:</h1>
    <p id="lowestSolution"></p>
    </div>
    <div class="right">
    <h1>Permutations: ~<span id="numPerms"></span></h1>
    <hr/>
    <h1 id="possiblePerms"></h1>
    </div>
	</div>
	<div class="right">
		<h1>Chart</h1>
		<canvas id="chart"></canvas>
		<h2>Batch Lowest: <span id="lastSolve"></span>+ | Lowest Solve: <span id="lowestSolve"></span></h2>
		<hr>
		<a href="#" onclick="location.href = (location.href)">refresh</a>
	</div>

script.js

// POLYFILLS FIRST, ACTUAL LOGIC AFTER

// requestAnimationFrame polyfill by Erik Möller. fixes from Paul Irish and Tino Zijdel
// MIT license
(function(){var lastTime=0;var vendors=["ms","moz","webkit","o"];for(var x=0;x<vendors.length&&!window.requestAnimationFrame;++x){window.requestAnimationFrame=window[vendors[x]+"RequestAnimationFrame"];window.cancelAnimationFrame=window[vendors[x]+"CancelAnimationFrame"]||window[vendors[x]+"CancelRequestAnimationFrame"]}if(!window.requestAnimationFrame)window.requestAnimationFrame=function(callback,element){var currTime=(new Date).getTime();var timeToCall=Math.max(0,16-(currTime-lastTime));var id=
	window.setTimeout(function(){callback(currTime+timeToCall)},timeToCall);lastTime=currTime+timeToCall;return id};if(!window.cancelAnimationFrame)window.cancelAnimationFrame=function(id){clearTimeout(id)}})();

//ARRAY INDEXOF POLYFILL
if(!Array.prototype.indexOf)Array.prototype.indexOf=function(searchElement,fromIndex){if(this===undefined||this===null)throw new TypeError('"this" is null or not defined');var length=this.length>>>0;fromIndex=+fromIndex||0;if(Math.abs(fromIndex)===Infinity)fromIndex=0;if(fromIndex<0){fromIndex+=length;if(fromIndex<0)fromIndex=0}for(;fromIndex<length;fromIndex++)if(this[fromIndex]===searchElement)return fromIndex;return-1};



//ACTUAL LOGIC
var input = document.getElementById("input");
var distance = document.getElementById("distance");
var chart = document.getElementById("chart");
var lowestSolveEle = document.getElementById("lowestSolve");
var lastSolveEle = document.getElementById("lastSolve");

var lowestSolve = 999999999;
var lowestSolveData = null;

//For verification purposes. Solution 187.
var cannedData = [ 
	'0039,0003',
	'0011,0055',
	'0025,0044',
	'0073,0006',
	'0012,0067',
	'0071,0012',
	'0035,0060',
	'0082,0035',
	'0043,0075',
	'0045,0083'
];

var distancedata = [];
var permValueMap = {};
var data;



//INITIALIZE
function init () {
	data = generateData(11, 100, false);
	data = data.sort(sortCities);
}
function generateData(numCities, distmax, useCannedData) {
	var outArr = [];
	if ( !!useCannedData ) {
		outArr = shuffle(cannedData);
	} else {
		for ( var i = 0; i < numCities; i++ ) {
			outArr.push( 
				padLeadingZeros( Math.round(Math.random()*distmax), 4 )+","+ padLeadingZeros( Math.round(Math.random()*distmax), 4 )
			);
		}
	}
	generatePermValueMap(outArr);
	return outArr;
}
function generatePermValueMap ( citiesArr ) {
	for (var i = citiesArr.length - 1; i >= 0; i--) {
		permValueMap[ citiesArr[i] ] = Math.floor( Math.random()*999999999 );
	}
}
function padLeadingZeros(num, size) {
	var s = "000000000" + num;
	return s.substr(s.length-size);
}
function padNBSP(num, size) {
	var s = "" + num;
	if ( s.length < size ) {
		for ( var i = 0, len = size-s.length; i < len; i++ ) {
			s = "&nbsp;" + s;
		}
	}
	return s;
}
function getDistance ( x1, y1, x2, y2 ) {
	var a = parseFloat(x2, 10) - parseFloat(x1, 10);
	var b = parseFloat(y2, 10) - parseFloat(y1, 10);
	return Math.round( Math.sqrt((a*a)+(b*b)) );
}
function outputCities (data) {
	var out = [];
	out.push("<ol>");
	data.forEach( function (cityData, i) {
		out.push( "<li>" + cityData + "</li>" ); 
	});
	out.push("</ol>");  
	return out.join(" \n ");
}
function outputDistanceTable ( data ) {
	var out = [];
	out.push("<table>");
	data.forEach( function (cityData1, i) {
		out.push( "<tr>" );
		distancedata.push([]);
		data.forEach( function (cityData2, j) {
			var city1 = cityData1.split(",");
			var city2 = cityData2.split(",");
			distancedata[i][j] = getDistance( city1[0], city1[1], city2[0], city2[1] );
			out.push( '<td class="'+getCityClass(data[i])+'_to_'+getCityClass(cityData2)+'">' + padNBSP( distancedata[i][j], 4 ) + "</td>" );
		});
		out.push( "</tr>" ); 
	})
	out.push("</table>");  
	return out.join(" \n ");
}
function getCityClass (city) {
	return "city_"+city.replace(",","_");
}
function getCityObj (city) {
	var cityArr = city.split(",");
	return [ parseFloat(cityArr[0], 10), parseFloat(cityArr[1], 10) ];
}
function factorial(n) { 
	if (n <= 1) return 1; 
	return n*factorial(n-1); 
} 
function drawCities (canvas) {
	document.getElementById("possiblePerms").innerHTML = "Total Possible Permutations: "+factorial(data.length);
	var scale = 5;
	canvas.height=100*scale;
	canvas.width=100*scale;
	var ctx = canvas.getContext("2d");
	ctx.fillStyle = "#000000";
	var city = [];
	var cityProp = {x:0, y:0};
	data.forEach( function (cityData, i) {
		city = cityData.split(",");
		cityProp = [ parseFloat(city[0],10), parseFloat(city[1],10) ];
		ctx.fillRect((cityProp[0]*scale)-5,(cityProp[1]*scale)-5,10,10);
	})
}

var solveCertainty = 0.01;
function drawSolution (canvas, data, lineWidth, hue, certainty) {
	var scale = 5;
	var thisSolve = 0;
	var ctx = canvas.getContext("2d");
	var newData = (data.join("|")).split("|");

	var cityObj = [ 0, 0 ];
	var firstCity = getCityObj( newData[0] );
	var lastCity = getCityObj( newData.pop() );

	ctx.beginPath();
	ctx.moveTo( firstCity[0]*scale, firstCity[1]*scale );
	ctx.lineTo( lastCity[0]*scale, lastCity[1]*scale );

	var fullpath = true;
	while ( !!newData.length ) {
		cityObj = getCityObj( newData.pop() ); 
		ctx.lineTo( cityObj[0]*scale, cityObj[1]*scale );
		thisSolve += getDistance( cityObj[0], cityObj[1], lastCity[0], lastCity[1] );
		if ( thisSolve > lowestSolve ) {
			//IF CURRENT SOLVE IS TOO HIGH ALREADY, STOP SOLVING AND MOVE ON.
			//DRAMATIC PERFORMANCE INCREASE.
			fullpath = false;
			newData = [];
		}
		lastCity = cityObj;
	}
	if ( fullpath ) {
		console.log( "fullpath" )
		ctx.lineTo( firstCity[0]*scale, firstCity[1]*scale );
		thisSolve += getDistance( firstCity[0], firstCity[1], lastCity[0], lastCity[1] );
		if ( thisSolve > lowestSolve ) {
			fullpath = false;
		}
	}

	writeLowestSolve( thisSolve, (data.join("|")).split("|") );

	if ( !certainty ) {
		var certainty = solveCertainty;
	}
	if ( fullpath ) {
		ctx.lineWidth = lineWidth;    
		ctx.strokeStyle = "hsla("+hue+",70%,60%,"+certainty+")";    
		ctx.stroke();
	}
	ctx.closePath();
	return [ thisSolve, data.slice() ];
}
function writeLowestSolve ( newSolve, newData ) {
	if ( newSolve < lowestSolve ) {
		solveCertainty += 0.01;
		lowestSolveEle.innerHTML = newSolve;
		lowestSolve = newSolve;
		lowestSolveData = newData;
		document.getElementById("lowestSolution").innerHTML = newData.join(" \<br\/\>");
		var tds = document.querySelectorAll("#distance td");
		var solveTds = [];
		for (var i = 0, len = lowestSolveData.length; i < len; i++) {
			if ( i > 0 ) {
				var sel = "."+getCityClass( lowestSolveData[i] )+'_to_'+getCityClass( lowestSolveData[i-1] );
				solveTds.push( document.querySelector( sel ) );
				//console.log( td );
			}
		};
		writeStyle( tds, "" );
		writeStyle( solveTds, "hsla(128,70%,60%,0.8)" );
	}  
}
function writeStyle (eleArr, styleString ) {
	if ( !!eleArr.length ) {
		for ( var i = 0, len = eleArr.length; i < len; i++ ) {
			eleArr[i].style.backgroundColor = styleString;
		}
	}
}
function writeLastSolve ( newSolve, newData ) {
	lastSolveEle.innerHTML = newSolve;
}
function permValue ( input ) {
	/*
	var _a = ( input ).split(",");
	var a0 = parseInt(_a[0]);
	var a1 = parseInt(_a[1]);
	return a0 + a1 + Math.floor( a0 / a1 );
	*/
	return permValueMap[input];
}
function nextPermutation(permArr) {
	var i = permArr.length - 1;
	while (i > 0 && permValue( permArr[i - 1] ) >= permValue( permArr[i] ) ) {
		i--;
	}

	if (i == 0) {
		return false;
	}

	var j = permArr.length - 1;
	while ( permValue( permArr[j] ) <= permValue( permArr[i - 1] ) ) {
		j--;
	}

	var temp = permArr[i - 1];
	permArr[i - 1] = permArr[j];
	permArr[j] = temp;

	j = permArr.length - 1;
	while (i < j) {
		temp = permArr[i];
		permArr[i] = permArr[j];
		permArr[j] = temp;
		i++;
		j--;
	}

	return true;
}
function sortCities (a,b) {
	if ( permValue(a) < permValue(b) ) return -1;
	if ( permValue(a) > permValue(b) ) return 1;
	return 0;
}
var batches = 0;
var $numPerms = document.getElementById("numPerms");
function nextOnRaf () {
	batches++;
	var batch = 4*1000;
	var numbatch = batch;
	var continueBatch = true;
	var tempSolve;
	while ( batch-- ) {
		continueBatch = nextPermutation(data);
		if ( continueBatch ) {
	      	var _temp = drawSolution(chart,data,2,10);
	      	if ( !tempSolve || ( !!tempSolve && _temp[0] < tempSolve[0] ) ) {
	      		tempSolve = _temp;
	    	}
		} else {
			console.log( "DONE! Last Solve: ", tempSolve );
			batch = 0;
		}
	}
	$numPerms.innerHTML = getNumPermsHTML(batches, numbatch);
	if (!!tempSolve) {
		writeLastSolve(tempSolve[0], tempSolve[1]); 
	}
	if ( continueBatch ) {
		//console.log(batches);
		requestAnimationFrame( nextOnRaf );   
	} else {
		solveCertainty = 1;
		drawSolution(chart,lowestSolveData,5,128);
		console.log( "End Run!" );
	}
}
function getNumPermsHTML (batches, numbatch) {
	return (batches*numbatch)+" <br/> ["+batches+"&bull;"+numbatch+"]";
}


// UTILS
function shuffle(array) {
  	var currentIndex = array.length, temporaryValue, randomIndex;

  	while (0 !== currentIndex) {
	    randomIndex = Math.floor(Math.random() * currentIndex);
	    currentIndex -= 1;
	    temporaryValue = array[currentIndex];
	    array[currentIndex] = array[randomIndex];
	    array[randomIndex] = temporaryValue;
  	}

  	return array;
}

init();

input.innerHTML = outputCities( data );
distance.innerHTML = outputDistanceTable( data );

drawCities( chart );

requestAnimationFrame( nextOnRaf );

style.css

body {
  font-family: monospace;
}
table td {
  text-align: right;
  padding: 5px;
  border: 1px solid #DDD;
}
#chart {
  height: 500px;
  width: 500px;
  display: block;
  border: 1px solid #000;
}
.left, .right {
  width: 50%;
  margin: 0;
  padding: 0;
  float: left;
  border: 1px solid #DDD;
  box-sizing: border-box;
}

v2-brute-force-random-traveling-salesman-solver.markdown

[v2] Brute Force Random Traveling Salesman solver

[wip] brute force TSP solver, with visualizations, and graphs and stuff.

A Pen by Keegan Brown on CodePen.

License.