Brute Force Random Traveling Salesman solver

Developer
Keegan Brown
Size
5,376 Kb
Views
38,456
  1. Brute Force Random Traveling Salesman solver Previews
  2. Brute Force Random Traveling Salesman solver HTML Codes
  3. Brute Force Random Traveling Salesman solver CSS Codes
  4. Brute Force Random Traveling Salesman solver JS Codes

How do I make an brute force random traveling salesman solver?

Work in progress.. What is a brute force random traveling salesman solver? How do you make a brute force random traveling salesman solver? This script and codes were developed by Keegan Brown on 16 October 2022, Sunday.

Brute Force Random Traveling Salesman solver Previews
IQ Test

Brute Force Random Traveling Salesman solver - Script Codes HTML Codes

<!DOCTYPE html>
<html >
<head> <meta charset="UTF-8"> <title>Brute Force Random Traveling Salesman solver</title> <style> /* NOTE: The styles were added inline because Prefixfree needs access to your styles and they must be inlined if they are on local disk! */ 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;
} </style> <script src="https://cdnjs.cloudflare.com/ajax/libs/prefixfree/1.0.7/prefixfree.min.js"></script>
</head>
<body>	<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 src="js/index.js"></script>
</body>
</html>

Brute Force Random Traveling Salesman solver - Script Codes CSS Codes

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

Brute Force Random Traveling Salesman solver - Script Codes JS Codes

// 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. Minmum Solve Length 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(10, 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>");	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(",");	distancedata[i][j] = getDistance( city1[0], city1[1], city2[0], city2[1] );	out.push( '<td class="'+getCityClass(data[i])+'_to_'+getCityClass(data[j])+'">' + 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 { 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, certainty) {	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.beginPath();	ctx.moveTo( firstCity.x*scale, firstCity.y*scale );	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 ( true && 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.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 ( !certainty ) {	var certainty = solveCertainty;	}	if ( fullpath ) {	ctx.lineWidth = lineWidth;	ctx.strokeStyle = "hsla("+hue+",70%,60%,"+certainty+")";	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\/\>");	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;	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;	}	}	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!" );	}	}	// 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 );
Brute Force Random Traveling Salesman solver - Script Codes
Brute Force Random Traveling Salesman solver - Script Codes
Home Page Home
Developer Keegan Brown
Username keeganbrown
Uploaded October 16, 2022
Rating 3
Size 5,376 Kb
Views 38,456
Do you need developer help for Brute Force Random Traveling Salesman solver?

Find the perfect freelance services for your business! Fiverr's mission is to change how the world works together. Fiverr connects businesses with freelancers offering digital services in 500+ categories. Find Developer!

Keegan Brown (keeganbrown) Script Codes
Name
Paint drips up the wall, sometimes.
A CSS Trip through outer space
Particles, Particles, Particles -- 3
Trying out GSAP 1.19
Particles with GSAP and SketchJS
Grow3.js Starter Pen
Meteor Shower
Text With Mouse Reactive Soft Shadow
Easy-peasy 3D Scrolling Parallax with GSAP
Particles with pixi.js
Create amazing sales emails with AI!

Jasper is the AI Content Generator that helps you and your team break through creative blocks to create amazing, original content 10X faster. Discover all the ways the Jasper AI Content Platform can help streamline your creative workflows. Start For Free!