Algorithms_Coursera_Part IV_Programming_Assignment_2.js

Algorithms_Coursera_Part IV_Programming_Assignment_2.js

/* eslint-env node */

/**
* -------------------------- Part 1 -----------------------------
*/

/**
* In this assignment you will implement one or more algorithms for the traveling
* salesman problem, such as the dynamic programming algorithm covered in the
* video lectures. Here is a data file describing a TSP instance.
*
* tsp.txt
*
* The first line indicates the number of cities. Each city is a point in the
* plane, and each subsequent line indicates the x- and y-coordinates of a single
* city.
*
* The distance between two cities is defined as the Euclidean distance --- that
* is, two cities at locations (x,y) and (z,w) have distance
* sqrt{(x-z)^2 + (y-w)^2} between them.
*
* In the box below, type in the minimum cost of a traveling salesman tour for
* this instance, rounded down to the nearest integer.
*
* OPTIONAL: If you want bigger data sets to play with, check out the TSP
* instances from around the world [here](http://www.tsp.gatech.edu/world/countries.html).
* The smallest data set (Western Sahara) has 29 cities, and most of the data
* sets are much bigger than that. What's the largest of these data sets that
* you're able to solve --- using dynamic programming or, if you like, a
* completely different method?
*
* HINT: You might experiment with ways to reduce the data set size. For 
* example, trying plotting the points. Can you infer any structure of the
* optimal solution? Can you use that structure to speed up your algorithm?
*/

/**
* -------------------------- FILE I/O -----------------------------
*/

const fs = require("fs");
const FILE_PATH = "tsp.txt"; // relative to this script's dir

/**
* TODO: Write JSDOC block
*/
class Graph {
  constructor(file) {
    // each element is a node labled (1, ..., n)
    this.nodes = [];
    // keys are node numbers (1, ..., n), values are [x, y] coords
    this.nodeVsCoords = {};
    this._parseFile(file); // populates this.nodes and this.nodeVsCoords
    // number => distToOtherNodes Map
    this.nodeVsDistToOtherNodes = new Map();
    this._computeAllDistances();
  }

  _parseFile(file) {
    const data = fs.readFileSync(file, "utf8");
    const rows = data.split("\n");
    for (let i = 0; i < rows.length; i++) {
      let row = rows[i];
      // Ignore the first row, which is the total number of cities
      if (i === 0) {
        this.n = Number(row);
        continue;
      }
      // Get rid of empty row at EOF
      if (row === "") {
        continue;
      }
      this.nodes.push(i - 1);
      // Remove excess white space at the end of the line
      row = row.trim();
      // Break each row into its own array
      row = row.split(" ");
      // The 0th ele is the x-coord and the 1st ele is the y-coord of city i
      this.nodeVsCoords[i - 1] = [Number(row[0]), Number(row[1])];
    }
  }

  _computeAllDistances() {
    for (const node1 of this.nodes) {
      const distToOtherNodes = new Map();
      this.nodeVsDistToOtherNodes.set(node1, distToOtherNodes);
      for (const node2 of this.nodes) {
        // TODO: memoize results; should only have to do this for the first
        // half of the nodes. There are redundant calculations
        const [x1, y1] = this.nodeVsCoords[node1];
        const [x2, y2] = this.nodeVsCoords[node2];
        const dist = this._euclidean(x1, y1, x2, y2);
        distToOtherNodes.set(node2, dist); // check: 0 if node1 === node2
      }
    }
  }

  _euclidean(x1, y1, x2, y2) {
    const [distX, distY] = [Math.abs(x1 - x2), Math.abs(y1 - y2)];
    return Math.sqrt(
      Math.pow(distX, 2) + Math.pow(distY, 2)
    );
  }
}

/**
* ----- Traveling Salesman Problem (TSP) Dynamic Programming Algorithm --------
*/

// NOTE: TRY USING CHROME DEVTOOLS DEBUGGER:
// https://medium.com/@paul_irish/debugging-node-js-nightlies-with-chrome-devtools-7c4a1b95ae27

/**
* How many edges are in an undirected, complete graph?
* There n nodes. Each has an edge to all the (n-1) others. (n * (n-1))
* But that counts each one twice, since the edge from A to B
* is the same as the one from B to A. So divide by 2. 
*/


/**
* Pseudocode:
* - Let A = 2D Array, indexed by Subsets S <= {1, 2, ..., n} that contain 1 and
*   destinations j in {1, 2, ..., n}.
* - Base case: A[S, 1] = {
*               0 if S = {1},
*               +Infinity otherwise (no way to avoid visiting vertex 1 twice)
*              }
* - For m = 2, 3, ... n: (m = subproblem size)
*   - For each set S <= {1, 2, ..., n} of size m htat contains 1:
*     - For each j in S where j != 1:
*       A[S_ij] = min_k in S, k != j {A[S - {j}, k] + C_kj} (same as recurrence)
* - Return min_j = 2 {A[{1, 2, ..., n}, j] + C_j1}
*/
function tsp(graph) {
  // NOTE: I ended up using minimum Hamiltonian cycles per this post, using the
  // euclidean distances between nodes computed in graph.nodeVsDistToOtherNodes
  // which was much easier to understand (I renumbered my nodes form 0 to 24 to
  // match the plot in this post):
  // https://www.coursera.org/learn/algorithms-npcomplete/discussions/weeks/2/threads/FNo8tpFPEeeH2hLapWklpg
  // Solution is H1 + H2 - 2 * (edge11_12)
  return graph.nodeVsDistToOtherNodes;
}

const graph = new Graph(FILE_PATH);
console.log(tsp(graph));

// Solution: 26442

tsp.txt

25
20833.3333 17100.0000
20900.0000 17066.6667
21300.0000 13016.6667
21600.0000 14150.0000
21600.0000 14966.6667
21600.0000 16500.0000
22183.3333 13133.3333
22583.3333 14300.0000
22683.3333 12716.6667
23616.6667 15866.6667
23700.0000 15933.3333
23883.3333 14533.3333
24166.6667 13250.0000
25149.1667 12365.8333
26133.3333 14500.0000
26150.0000 10550.0000
26283.3333 12766.6667
26433.3333 13433.3333
26550.0000 13850.0000
26733.3333 11683.3333
27026.1111 13051.9444
27096.1111 13415.8333
27153.6111 13203.3333
27166.6667 9833.3333
27233.3333 10450.0000