[wip] brute force TSP solver, with visualizations, and graphs and stuff.
A Pen by Keegan Brown on CodePen.
<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> |
// 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 = " " + 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+"•"+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 ); |
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; | |
} |
[wip] brute force TSP solver, with visualizations, and graphs and stuff.
A Pen by Keegan Brown on CodePen.