{{ message }}

Instantly share code, notes, and snippets.

Last active May 28, 2019
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}`; }