Preferences

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