A JS program for playing with different, but related, search algorithms

README.md

This is an extension of the previous gist - while that gist explored a particular question, this one tries to compare some algorithms which have very similar implementations, but different requirements and performance characteristics. It generates a random but somewhat believable geography on a plane and then tries to get from Q to W (noting that there may be more than one connection between two cities, with different costs). Each run is different.

An example result:

====================================================================================
Algorithm A*:
Expanded Q; Agenda = [(E, 308), (P, 190), (D, 289), (A, 497)]
Expanded E; Agenda = [(P, 190), (W, 412), (D, 289), (I, 512), (A, 497)]
Expanded P; Agenda = [(W, 412), (D, 289), (L, 338), (M, 385), (I, 512), (G, 420), (A, 497), (V, 528)]
Expanded W; Goal reached
Path: Q -> E -> W, Cost: 412
====================================================================================
Uniform Cost Search:
Expanded Q; Agenda = [(P, 190), (D, 289), (E, 308), (A, 497)]
Expanded P; Agenda = [(D, 289), (E, 308), (L, 338), (M, 385), (G, 420), (A, 497), (V, 528)]
Expanded D; Agenda = [(E, 308), (L, 338), (M, 385), (G, 420), (W, 444), (B, 486), (A, 497), (V, 528)]
Expanded E; Agenda = [(L, 338), (M, 385), (W, 412), (G, 420), (B, 486), (A, 497), (I, 512), (V, 528)]
Expanded L; Agenda = [(M, 385), (W, 412), (G, 420), (S, 485), (B, 486), (A, 497), (I, 512), (V, 528), (T, 533)]
Expanded M; Agenda = [(W, 412), (G, 420), (U, 460), (S, 485), (B, 486), (A, 497), (I, 512), (H, 523), (V, 528), (T, 533), (C, 598), (J, 713)]
Expanded W; Goal reached
Path: Q -> E -> W, Cost: 412
====================================================================================
Iterative Deepening Search:
Expanded Q; Agenda = [(P, 190), (D, 289), (E, 308), (A, 497)]
Expanded P; Agenda = [(D, 289), (E, 308), (A, 497), (M, 385), (V, 528), (G, 420), (L, 338)]
Expanded D; Agenda = [(E, 308), (A, 497), (M, 385), (V, 528), (G, 420), (L, 338), (W, 444), (B, 486)]
Expanded E; Agenda = [(A, 497), (M, 385), (V, 528), (G, 420), (L, 338), (W, 444), (B, 486), (I, 512)]
Expanded A; Agenda = [(M, 385), (V, 528), (G, 420), (L, 338), (W, 444), (B, 486), (I, 512), (O, 589)]
Expanded M; Agenda = [(V, 528), (G, 420), (L, 338), (W, 444), (B, 486), (I, 512), (O, 589), (U, 460), (S, 623), (H, 523), (J, 713), (C, 598)]
Expanded V; Agenda = [(G, 420), (L, 338), (W, 444), (B, 486), (I, 512), (O, 589), (U, 460), (S, 623), (H, 523), (J, 713), (C, 598), (Y, 917)]
Expanded G; Agenda = [(L, 338), (W, 444), (B, 486), (I, 512), (O, 589), (U, 460), (S, 623), (H, 523), (J, 713), (C, 598), (Y, 917)]
Expanded L; Agenda = [(W, 444), (B, 486), (I, 512), (O, 589), (U, 460), (S, 623), (H, 523), (J, 713), (C, 598), (Y, 917), (T, 533)]
Expanded W; Goal reached
Path: Q -> D -> W, Cost: 444
====================================================================================

Both UCS and A* picked the same route and report the same final cost. This makes sense, because they are both optimal - they find the cheapest solution to any given problem. IDS, however, has taken a different path with a higher cost. That is because it is only complete for this problem - it would be optimal if every path had the same cost. The difference between UCS and A* is that A* has to expand fewer nodes to find the destination.

Notably, each of these algorithms has the same worst case performance characteristics as Breadth-First Search. You kinda have to work pretty hard for this to happen, such as giving A* a heuristic which always returns 0 - essentially turning it into UCS - and then engineering your state space such that the resulting tree forces the agenda to behave like an ordinary queue. I think in practice this is pretty hard, and A* is a fairly popular algorithm for path finding, as well as other, perhaps slightly less intuitive problems.

agendaSearch.js

// Create a random (but somewhat believable) geography on a 500x500 plane. Each node is connected
// to around 3 others. Cost between nodes is deliberately greater than their Euclidian distance.
// Two nodes may be connected by more than one link.
const nodes = [...'QWERTYUIOPASDFGHJKLZXCVBNM'].map(letter => makeNode(letter, [], { x: Math.floor(Math.random() * 500), y: Math.floor(Math.random() * 500) }));
for (const node of nodes) {
    for (let n = 0; n < 3; n++) {
        const neighbour = nodes[Math.floor(Math.random() * nodes.length)];
        if (node !== neighbour) {
            const d = distance(node, neighbour);
            makeBidiEdge(node, neighbour, d + Math.floor(Math.random() * 50));
        }
    }
}

// Compare the different search approaches. A* uses cost so far + Euclidian distance from node
// to destination; UCS only uses cost so far, and IDS is UCS but hop cost is always 1. In the worst
// case both UCS and IDS will be about as memory-intensive as BFS.
console.log('====================================================================================');
console.log('Algorithm A*:');
console.log(formatPathAndCost(searchForPath(nodes[0], nodes[1], 'A*')));
console.log('====================================================================================');
console.log('Uniform Cost Search:');
console.log(formatPathAndCost(searchForPath(nodes[0], nodes[1], 'UCS')));
console.log('====================================================================================');
console.log('Iterative Deepening Search:');
console.log(formatPathAndCost(searchForPath(nodes[0], nodes[1], 'IDS')));
console.log('====================================================================================');

function makeNode(name, children = [], extras = {}) {
  return { name, children, ...extras };
}

function makeBidiEdge(nodeA, nodeB, cost) {
  nodeA.children.push(makeEdge(nodeB, cost));
  nodeB.children.push(makeEdge(nodeA, cost));
}

function makeEdge(node, cost) {
  return { node, cost };
}

function distance(nodeA, nodeB) {
    const sqDiffX = (nodeA.x - nodeB.x) ** 2;
    const sqDiffY = (nodeA.y - nodeB.y) ** 2;
    return Math.floor(Math.sqrt(sqDiffX + sqDiffY));
}

function searchForPath(startNode, endNode, mode = 'A*') {
  // Keeps track of which nodes we already expanded at some point
  const globalVisitedNodes = [];
  let agenda = [{node: startNode, cost: 0, path: []}];
  do {
    if (!agenda.length) return null;
    if (agenda[0].node === endNode) {
      console.log(`Expanded ${agenda[0].node.name}; Goal reached`);
      return {
        path: [...agenda[0].path, agenda[0].node],
        cost: agenda[0].cost
      };
    }
    
    const state = agenda[0];
    agenda = [
      ...agenda.slice(1),
      ...expand(state),
    ].sort(byCost);
    
    // Reduces agenda size by not adding nodes to which there is a cheaper path.
    // This works by picking the first encountered state for a particular node,
    // which because the agenda is sorted will be the cheapest path to that node.
    const nodeToAgendaItem = new Map();
    for (const item of agenda) {
      if (!nodeToAgendaItem.has(item.node)) {
        nodeToAgendaItem.set(item.node, item);
      }
    }
    // We have to re-sort the agenda here because the Map() implementation might have hashed
    // the entries in a different order to what was on the agenda before
    agenda = [...nodeToAgendaItem.values()].sort(byCost);
    console.log(`Expanded ${state.node.name}; Agenda = ${formatAgenda(agenda)}`);
  } while (true);

  function expand(state) {
    if (!state.node.children.length) return [];
    globalVisitedNodes.push(state.node);
    const visitedNodeSet = new Set(globalVisitedNodes);
    // Only add nodes to the agenda which we already expanded elsewhere.
    // Is this the right optimization here? We may be missing cheaper paths,
    // but this method was used to obtain the exam solution.
    return state.node.children.filter(edge => !visitedNodeSet.has(edge.node)).map(edge => ({
      node: edge.node,
      cost: state.cost + edge.cost,
      path: [...state.path, state.node],
    }));
  }

  function byCost(stateA, stateB) {
    const costA = getCost(stateA, mode);
    const costB = getCost(stateB, mode);
    return costA - costB;
  }

  // The practical difference between A*, UCS, and IDS is in how they calculate costs for each
  // node in the agenda. A* uses cost so far + estimate of remaining cost, which in this case is
  // the Euclidian distance between current node and the destination. UCS uses only cost so far, and
  // is the best you can do if you don't have an admissible heuristic (ie. one that never over-estimates)
  // for the remaining cost. IDS is perhaps the best you can do if all hop costs are equal - here,
  // cost so far is the number of hops, which is also the depth of the search tree.
  function getCost(state, mode) {
      switch (mode) {
          case 'A*': return state.cost + distance(state.node, endNode);
          case 'UCS': return state.cost;
          case 'IDS':
          default: return 1;
      }
  }
}

function formatAgenda(agenda) {
  const agendaStr = agenda.map(state => `(${state.node.name}, ${state.cost})`).join(', ');
  return `[${agendaStr}]`;
}

function formatPathAndCost({ path, cost }) {
  const pathStr = path.map(node => node.name).join(' -> ');
  return `Path: ${pathStr}, Cost: ${cost}`;
}