4 ms·
> 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.
by 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.)