| A connection that tickled my fancy... In the "Finding Paths, Faster" section it specifies: 1. that we can only use the standard A* algo when we know enough about "the graph in question" to exploit that knowledge to pick a heuristic. 2. When we don't know anything specific to "the graph in question", we need to rely on BFS or by extension BiDi BFS (Bi-directional BFS) to find the shortest path in general. Then way down the page in the "Finding the Right Path, Faster" section it specifies an optimisation for speeding up a correct BiDi BFS algo in a general graph is to order our searching by always check the side with the least queued branches. The connection comes from realising that while we might not know anything specific to the graph in question, we know enough about graphs in general (of which "the graph" is one) that gives us enough knowledge to exploit the graph in question. So a BiDi BFS where we repeatedly choose the side with the fewest branches IS essentially a BiDi A* algo that can be applied on a general graph. Or put another way, Unidirectional A* search can't be used on a general graph, but Bidirectional A* search can. |