Travelling Salesman Sketches: Max Distance

index.html

<header>
  <input type="range" min="3" max="9" step="1" value="5">
</header>
<div>
  <canvas id="cvs1" height="800" width="800"></canvas>
  <canvas id="cvs2" height="800" width="800"></canvas>
</div>
<footer>
  <ul>
    <li>Calculated "Max" Distance <span id="max"></span></li>
    <li>Actual Distance <span id="actual"></span></li>
    <li>Total Point Count <span id="points"></span></li>
    <li>Total Permutation Count <span id="permutations"></span></li>
    <li>Skipped Permutation Point (on avg) <span id="skipped"></span></li>
  </ul>
</footer>

script.babel

console.clear();
const PI = Math.PI;
const PI2 = PI * 2;

class Point {
  constructor() {
    this.x = Math.random();
    this.y = Math.random();
    this.prox = Math.hypot(0.5 - this.x, 0.5 - this.y);
  }
}

class Permutations {
  constructor(pointCount) {
    this.pointCount = pointCount;
    this.loadOrGeneratePermutations();
  }

  loadOrGeneratePermutations() {
    let existing = window.sessionStorage.getItem(`permutations-${this.pointCount}`);
    if (existing) {
      this.data = JSON.parse(existing);
    } else {
      this.data = [];
      let array = [];
      // initial array ignores 0. we start permutations at 1.
      for (let i = 1; i <= this.pointCount - 1; i++) array.push(i);

      do {
        // copy to check if reverse exists
        let copy = Array.from(array).reverse();
        // if reverse does not exist
        if (!this.data.includes([0].concat(copy).join(''))) {
          // add it
          this.data.push([0].concat(array).join(''));
        }
      } while(this.nextPermutation(array));
      this.data = this.data.map((perm) => {
        return perm.split('').map((int) => { return parseInt(int) });
      });
      window.sessionStorage.setItem(
        `permutations-${this.pointCount}`,
        JSON.stringify(this.data)
      );
    }
  }

  // https://stackoverflow.com/a/34014930
  nextPermutation(array) {
    // Find non-increasing suffix
    let i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) i--;
    if (i <= 0) return false;

    // Find successor to pivot
    let j = array.length - 1;
    while (array[j] <= array[i - 1]) j--;
    let temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
      temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++; j--;
    }
    return true;
  }
}

class Canvas {
  constructor() {
    this.element1 = document.querySelector('#cvs1');
    this.context1 = this.element1.getContext('2d');
    this.element2 = document.querySelector('#cvs2');
    this.context2 = this.element2.getContext('2d');
    this.gutter = 30;
    this.diameter = this.element1.width;
    this.switchContext(0);
  }

  clear() {
    this.context1.clearRect(0, 0, this.diameter, this.diameter);
    this.context2.clearRect(0, 0, this.diameter, this.diameter);
  }

  switchContext(idx) {
    this.context = [this.context1, this.context2][idx];
  }

  text(x, y, text, offset = 1) {
    this.context.textAlign = 'center';
    this.context.textBaseline = 'middle';
    let fontSize = 14;
    let offsetY = (y > 0.5) ? fontSize * (offset * 1.5) : fontSize * (offset * -1.5);
    this.context.fillStyle = 'white';
    this.context.font = `${fontSize}px Helvetica`;
    this.context.fillText(text, this.relative(x), this.relative(y) + offsetY);
  }

  rect(x, y, w, h, color = 'red') {
    this.context.strokeStyle = color;
    this.context.strokeRect(
      this.relative(x), this.relative(y), 
      this.relativeSize(w), this.relativeSize(h)
    );
  }

  point(x, y, fill = 'red') {
    this.context.fillStyle = fill;
    this.context.beginPath();
    this.context.arc(this.relative(x), this.relative(y), 4, 0, PI2);
    this.context.fill();
  }
  
  path(x1, y1, x2, y2, stroke = 'red') {
    this.context.strokeStyle = stroke;
    this.context.lineWidth = 2;
    this.context.beginPath();
    this.context.moveTo(this.relative(x1), this.relative(y1));
    this.context.lineTo(this.relative(x2), this.relative(y2));
    this.context.stroke();
  }
  
  relativeSize(size) {
    return size * (this.diameter - this.gutter * 2);
  }

  relative(plot) {
    return this.relativeSize(plot) + this.gutter;
  }
}

class App {
  constructor() {
    this.canvas = new Canvas();
    this.$max = document.querySelector('#max');
    this.$actual = document.querySelector('#actual');
    this.$skipped = document.querySelector('#skipped');
    this.$permutations = document.querySelector('#permutations');
    this.$points = document.querySelector('#points');
  }

  run(pointCount) {
    this.pointCount = pointCount;
    this.permutations = new Permutations(this.pointCount);
    this.skippedPermutations = 0;
    this.skippedPermutationPoint = 0;
    this.generatePoints();
    this.generateMaxDistance();
    this.generatePaths();
    this.drawPoints();
    this.$max.innerHTML = Math.round(this.maxDistance * 100) / 100;
    this.$actual.innerHTML = Math.round(this.actualDistance * 100) / 100;
    this.$skipped.innerHTML = Math.round(this.skippedPermutationPoint * 100) / 100;
    this.$permutations.innerHTML = this.permutations.data.length;
    this.$points.innerHTML = this.pointCount;
  }

  generatePoints() {
    this.points = [];
    this.minX = 1; this.minY = 1; this.minP = 1;
    this.maxX = 0; this.maxY = 0; this.maxP = 0;

    for (let i = 0; i < this.pointCount; i++) {
      let point = new Point();
      this.minX = Math.min(this.minX, point.x);
      this.minY = Math.min(this.minY, point.y);
      this.minP = Math.min(this.minP, point.prox);
      this.maxX = Math.max(this.maxX, point.x);
      this.maxY = Math.max(this.maxY, point.y);
      this.maxP = Math.max(this.maxP, point.prox);
      this.points.push(point);
    }
    this.w = this.maxX - this.minX;
    this.h = this.maxY - this.minY;
    this.d = Math.min(this.w, this.h);
    this.x = this.w / 2 + this.minX;
    this.y = this.h / 2 + this.minY;
  }

  generateMaxDistance() {
    this.maxDistance = this.w * 2 + this.h * 2;
  }

  generatePaths() {
    console.time('generatePaths');
    this.distances = {};
    this.actualDistance = Infinity;
    for (let d = 0; d < this.permutations.data.length; d++) {
      let permutation = this.permutations.data[d];
      let distance = 0;
      let breakThrough;
      for (let i = 0; i < this.pointCount; i++) {
        let idx1 = permutation[i];
        let idx2 = permutation[(i + 1) % this.pointCount];
        let dist = this.distanceFromIndexes(idx1, idx2);
        distance += dist;
        if (distance > this.maxDistance && i < this.pointCount - 1) {
          breakThrough = i / (this.pointCount - 1);
          break;
        }
      }
      if (breakThrough) {
        this.skippedPermutations++;
        this.skippedPermutationPoint += breakThrough;
      } else if (distance < this.actualDistance) {
        this.actualDistance = distance;
        this.permutation = permutation;
      }
    }
    console.timeEnd('generatePaths');
    if (this.skippedPermutations) this.skippedPermutationPoint /= this.skippedPermutations;
  }

  distanceFromIndexes(idx1, idx2) {
    let args = [idx1, idx2];
    if (args in this.distances) return this.distances[args];
    let p1 = this.points[idx1];
    let p2 = this.points[idx2];
    let dist = Math.hypot(p1.x - p2.x, p1.y - p2.y);
    this.distances[args] = dist;
    this.distances[[idx2, idx1]] = dist;
    return dist;
  }

  drawPoints() {
    this.canvas.clear();
    this.canvas.point(this.x, this.y, 'yellow');
    this.canvas.rect(this.minX, this.minY, this.w, this.h, 'yellow');
    this.points.forEach((point) => {
      this.canvas.point(point.x, point.y, 'red');
    });
    this.permutation.forEach((idx, i) => {
      let p1 = this.points[idx];
      let p2 = this.points[this.permutation[(i + 1) % this.pointCount]];
      this.canvas.path(p1.x, p1.y, p2.x, p2.y);
    });
  }
}

let app = new App();
let $range = document.querySelector('input');
app.run(parseInt($range.value));

document.body.addEventListener('click', () => {
  app.run(parseInt($range.value));
});

$range.addEventListener('change', () => {
  app.run(parseInt($range.value));
});

style.scss

body {
  background: #121212;
}

header,
footer {
  text-align: center;
  margin: 1rem 0;
  color: #F00;
  font-weight: 300;
  font-size: 0.8rem;
  span {
    color: white;
  }
  ul {
    list-style: none;
    padding: 0;
  }
}
div {
  position: relative;
  width: 95%;
  max-width: 600px;
  margin: 1rem auto;
  cursor: pointer;
  &:after {
    content: '';
    padding-bottom: 100%;
    display: block;
  }
  canvas:last-child {
    display: none;
  }
  &:hover canvas:last-child {
    display: block;
  }
  canvas {
    &:first-child {
      background: black;
    }
    position: absolute;
    top: 0; left: 0;
    width: 100%;
    height: auto;
  }
}

travelling-salesman-sketches-max-distance.markdown

Travelling Salesman Sketches: Max Distance

An optimization for brute force. Given an array of points, calculate a known maximum distance round trip. This can be used to abort attempts that go longer than this calculated distance.

For example, if I know the distance is less than 50 units for 10 points with an unknown optimal distance of 25, when brute forcing the path, any attempt that goes longer than 50 can be immediately stopped.

Currently I am setting this to the outer square's (w * 2 + h * 2) and it seems to be doing the job. This will definitely become inaccurate with larger data sets.

A Pen by HARUN PEHLİVAN on CodePen.

License.