A Pen by Keegan Brown.

Brute-Force-Random-Traveling-Salesman-solver.markdown

Brute Force Random Traveling Salesman solver

Work in progress.

A Pen by Keegan Brown on CodePen.

License.

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

// 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)}})();
  



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;

var data = generateData(10, 100);
    data = data.sort(sortCities);
var distancedata = [];

function generateData(numCities, distmax) {
  var outArr = [];
  for ( var i = 0; i < numCities; i++ ) {
    outArr.push( 
      padLeadingZeros( Math.round(Math.random()*distmax), 4 )+","+ padLeadingZeros( Math.round(Math.random()*distmax), 4 )
    );
  }
  return outArr;
}
function padLeadingZeros(num, size) {
  var s = "000000000" + num;
  return s.substr(s.length-size);
}
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>");
  for ( var i in data ) {
    out.push( "<li>" + data[i] + "</li>" ); 
  }
  out.push("</ol>");  
  return out.join(" \n ");
}
function outputDistanceTable ( data ) {
  var out = [];
  out.push("<table>");
  for ( var i in data ) {
    out.push( "<tr>" );
    distancedata.push([]);
    for ( var j in data ) {
      var city1 = data[i].split(",");
      var city2 = data[j].split(",");
      out.push( '<td class="'+getCityClass(data[i])+' '+getCityClass(data[j])+'">' + getDistance( city1[0], city1[1], city2[0], city2[1] ) + "</td>" );
      distancedata[i][j] = getDistance( city1[0], city1[1], city2[0], city2[1] );
    }
    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 { x: parseFloat(cityArr[0], 10), y: 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};
  for ( var i in data ) {
    city = data[i].split(",");
    cityProp = {x:parseFloat(city[0],10), y:parseFloat(city[1],10)}
    ctx.fillRect((cityProp.x*scale)-5,(cityProp.y*scale)-5,10,10);
  }
}

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

  var cityObj = {x:0,y:0};
  var firstCity = getCityObj( newData[0] );
  var lastCity = getCityObj( newData.pop() );
  

  
  
  ctx.moveTo( lastCity.x*scale, lastCity.y*scale );
  ctx.beginPath();
  ctx.lineTo( lastCity.x*scale, lastCity.y*scale );

  var fullpath = true;
  while ( !!newData.length ) {
    cityObj = getCityObj( newData.pop() ); 
    ctx.lineTo( cityObj.x*scale, cityObj.y*scale );
    thisSolve += getDistance( cityObj.x, cityObj.y, lastCity.x, lastCity.y );
    if ( thisSolve > lowestSolve ) {
      fullpath = false;
      newData = [];
    }
    lastCity = cityObj;
  }
  if ( fullpath ) {
    ctx.lineTo( firstCity.x*scale, firstCity.y*scale );
    thisSolve += getDistance( firstCity.x, firstCity.y, lastCity.x, lastCity.y );
    if ( thisSolve > lowestSolve ) {
      fullpath = false;
    }
  }
  
  writeLowestSolve( thisSolve, (data.join("|")).split("|") );
  
  if ( fullpath ) {
    ctx.lineWidth = lineWidth;    
    ctx.strokeStyle = "hsla("+hue+",70%,60%,"+solveCertainty+")";    
    ctx.stroke();
  }
  ctx.closePath();
  return [ thisSolve, (data.join("|")).split("|") ];
}
function writeLowestSolve ( newSolve, newData ) {
  if ( newSolve < lowestSolve ) {
    solveCertainty += 0.01;
    lowestSolveEle.innerHTML = newSolve;
    lowestSolve = newSolve;
    lowestSolveData = newData;
    document.getElementById("lowestSolution").innerHTML = newData.join(" \<br\/\>");
  }  
}
function writeLastSolve ( newSolve, newData ) {
  lastSolveEle.innerHTML = newSolve;
}
function permValue ( input ) {
  var _a = ( input ).split(","); 
  return parseInt(_a[0]) + parseInt(_a[1]);
}
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;
function nextOnRaf () {
  batches++;
  var batch = 2000;
  var numbatch = batch;
  var continueBatch = true;
  var tempSolve;
  while ( batch-- ) {
    continueBatch = nextPermutation(data);
    if ( continueBatch ) {
      //console.log(data);
      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;
    }
  }
  document.getElementById("numPerms").innerHTML = (batches*numbatch)+" <br/> ["+batches+"&bull;"+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!" );
  }
}

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;
}

Traveling-Salesman-incomplete.marktdown

A Pen by Keegan Brown
---------------------


A [Pen](http://codepen.io/keeganbrown/pen/lLhjt) by [Keegan Brown](http://codepen.io/keeganbrown) on [CodePen](http://codepen.io/).

[License](http://codepen.io/keeganbrown/pen/lLhjt/license).