In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as being: $O(b^{d+1})$ with the following explanation:
Normally (or at least in my experience thus far in Algorithms) I've seen the running time of BFS to be $O(V+E)$ so why is it different here. Is this a special case?
Asked By : loremIpsum1771
Answered By : D.W.
This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve.
The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits everything in the graph. We measure the number of vertices ($V$) and the number of edges ($E)$, and the running time is measured in terms of these two parameters. Also, the algorithms community usually analyzes the case where we run BFS until every vertex in the graph has been visited. If this is the goal, and those are the parameters we care about, the running time to visit every vertex is indeed $O(V+E)$.
The artificial community typically considers a different scenario: we have an infinite or very large graph, and we're not going to visit all of it; we're going to visit only a tiny fraction of the graph, only as much as necessary until we can find one node with a particular property (a target node / goal node). Think of the state space of a game like chess, or the 15-puzzle, or something like that. In addition, in the cases that typically arise in artificial intelligence, usually the portion of the graph that we're going to visit looks sorta like a tree: each vertex has on average about $b$ edges leading out of it. So in this situation, a bound like $O(V+E)$ is not helpful: it is a valid upper bound, but it is extremely loose -- the number of states (vertices) you actually need to visit might be much smaller than the total number of states (vertices) that exist. So, in AI applications, we usually want a better estimate of the number of states visited. That's what leads to the $O(b^d)$ estimate.
Both upper bounds are valid, in the situation where they apply. But the two situations they're focused on are very different. It's the same algorithm (BFS), applied in two different contexts... and because of some differences in the characteristics, it makes sense to measure its running time differently in the two settings.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/64412
0 comments:
Post a Comment
Let us know your responses and feedback