3 ms·
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)
by JohnKemeny 1y ago
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 1y agoLikewise, 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 1y ago> 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.
- kragen 1y agoI 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.
- JohnKemeny 1y agoIn (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.)