Hacker Neue

Preferences
JohnKemeny parent
OP's point is that

· 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.

nostrademons
Likewise, you can represent a queue as a priority queue with key = i, where i is an integer monotonically increasing at insertion time. And you can represent a stack as a priority queue where key = -i.

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.

thaumasiotes
> OP's point is that

> 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.

JohnKemeny OP
In (theoretical) computer science, we write "#xs" to denote "number of xs".

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.)

kragen
I think it is true, although "#edges" needs to be understood as "the number of the edges in the path from the starting point to the node", which was not one of my first three candidate interpretations.

This item has no comments currently.