DFS = queue
BFS = stack
Dijstra's = priority queue keyed by edge weight
A* = priority queue with heuristic function
Beam search = bounded priority queue with heuristic function
Topological sort = priority queue keyed by number of unvisited inbound edges
Copying garbage collector = pointer address
Mark & sweep garbage collector = dirty bit on the object pointed to
Generational garbage collector = multi-level grey set represented by the write barriers between each generation.
· BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges
· Dijkstra's is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = sum over edges
· A* is priority queue with key h(n) + g(n), where h(n) = heuristic(n), g(n) = sum over edges
It's cute.
This is the insight behind the decorate-sort-undecorate pattern; it's just heapsort, with a different key function allowing you to represent several different algorithms.
> BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges
He doesn't say that, and it isn't true.
My sentence was supposed to be read as "g(n) = number of edges", and implicitly, of course (since we're talking about BFS), that means number of edges seen up until now, from ns perspective. And yes, n usually denotes the size of the graph, however, in the context of A*, we usually write n to denote the current node (as per AI:MA).
I take full responsibility. (Disclaimer: I'm a CS professor teaching BFS and Dijkstra's algorithm every semester and A* every 2nd year.)
You're thinking too hard. :-) Just think of a map the same way a 10-year-old would.
Straight-line (Euclidean) distance is the most obvious heuristic on a map for estimating distance, and it's admissible.
Straight lines minimize distances i.e. they never overestimate. Which is enough to remind you that you want an underestimate.
> the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue
A much less obvious but much more fascinating (IMO) way to look at A* is that A* is actually Dijkstra but with a modified graph, where you adjust the heuristic delta between each edge's vertices to the edge's weight.
To remember the sign of the adjustment with this method, just imagine the next vertex getting super close to the destination, and then work out whether the weight needs to increase or decrease significantly in that case. (It needs to decrease, given you're getting closer to the destination.)
I have no information other than the fact that my agent has a decision to make (left or right).
- DFS or BFS
I have some information about the cost of the decision.
- UCS or Djikstra's algorithm
I have some idea of the cost of the decision, and a rough idea which direction the goal is in.
- A star
As well as knowing the cost, and a rough idea of the direction, I also know that I have a uniform cost grid.
- Jump point search
Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue)
Dijkstra: Priority is distance so far + next edge distance
A*: Priority is distance so far + next edge distance + estimate of distance to target node.
This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.