Skip to content

Instantly share code, notes, and snippets.

@FLamparski
Last active May 28, 2019 17:40
Show Gist options
  • Save FLamparski/d3112c77d1a2ad3474b7cd8476f41f63 to your computer and use it in GitHub Desktop.
Save FLamparski/d3112c77d1a2ad3474b7cd8476f41f63 to your computer and use it in GitHub Desktop.
A JS program for playing with different, but related, search algorithms

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.

// 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}`;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment