The basis for comparison of search methods. All the search algorithms are evaluated on the following these criterias.
1. COMPLETENESS: Does the algorithm always find a solution when there exists one?
2. TIME COMPLEXITY: How much time the algorithm run before finding the solution
3. SPACE COMPLEXITY: How much space does the algorithm used?
4. QUALITY: If some solutions are better than others then what kind of solution does the algorithm find?
Comparison of BFS and DFS
1. Completenes: Both DFS and BFS are complete for finite state spaces. Both are systematic.
Either they pick the goal node and report success or they report failure when OPEN list becomes empty.
The only difference is where the new notes are placed in the OPEN list.
In infinite space, DFS may go down an infinite path and not terminate. BFS will find a solution if there exists one.
If there is no solution, both algorithms will not terminate for infinite state spaces.
2. Time complexity: If the search is space is finite then in the worst case, both the search methods will search all the nodes before reporting failure.
When the goal node exists then the time taken to find it depends upon where the goal node is in it the state space.
The time taken depends upon where the goal happens to be in their path.
DFS:
If the goal is on the extreme left then DFS finds it after examining the nodes.
If the goal is on the extreme right it has to examine the entire search tree which is bd nodes.
On the average, it will examine NDFS nodes given by
NDFS= bd/2
BFS:
If the goal is on the left, it picks only one node which is the goal.
If the goal is on the right, it picks it up in the end like the DFS, that is it picks up nodes at the level d.
NBFS= bd(b+1)/2b
Therefore, we can see that the BFS does marginally worse than DFS.
3. Space complexity: In DFS, it dives down some branch at each level, leaving (b-1) nodes in OPEN. Just when it enters the depth d, it has at most ODFS nodes in the OPEN list.
ODFS = d(b-1) +1
The size of OPEN is linear with depth. In BFS it enters each level at depth d.It sees all the bd nodes ahead of it in OPEN list. When it enters the next level at depth (d+1) it's sees bd+1 nodes in the OPEN list. The size of OPEN grows exponentially with depth.
4. Quality of solution: BFS loses out on space complexity. It makes up on the quality on the solution. Since it pushes into the search space level by level, the BFS inspects candidate solutions in increasing order of solution length.
BFS will always find the shortest solution whereas DFS dives down into the search tree. It backtracks, if it reaches a dead end and tries other parts of the search space.
The first solution found which holds no guarantee that it will be the shortest one.
1. COMPLETENESS: Does the algorithm always find a solution when there exists one?
2. TIME COMPLEXITY: How much time the algorithm run before finding the solution
3. SPACE COMPLEXITY: How much space does the algorithm used?
4. QUALITY: If some solutions are better than others then what kind of solution does the algorithm find?
Comparison of BFS and DFS
1. Completenes: Both DFS and BFS are complete for finite state spaces. Both are systematic.
Either they pick the goal node and report success or they report failure when OPEN list becomes empty.
The only difference is where the new notes are placed in the OPEN list.
In infinite space, DFS may go down an infinite path and not terminate. BFS will find a solution if there exists one.
If there is no solution, both algorithms will not terminate for infinite state spaces.
2. Time complexity: If the search is space is finite then in the worst case, both the search methods will search all the nodes before reporting failure.
When the goal node exists then the time taken to find it depends upon where the goal node is in it the state space.
The time taken depends upon where the goal happens to be in their path.
DFS:
If the goal is on the extreme left then DFS finds it after examining the nodes.
If the goal is on the extreme right it has to examine the entire search tree which is bd nodes.
On the average, it will examine NDFS nodes given by
NDFS= bd/2
BFS:
If the goal is on the left, it picks only one node which is the goal.
If the goal is on the right, it picks it up in the end like the DFS, that is it picks up nodes at the level d.
NBFS= bd(b+1)/2b
Therefore, we can see that the BFS does marginally worse than DFS.
3. Space complexity: In DFS, it dives down some branch at each level, leaving (b-1) nodes in OPEN. Just when it enters the depth d, it has at most ODFS nodes in the OPEN list.
ODFS = d(b-1) +1
The size of OPEN is linear with depth. In BFS it enters each level at depth d.It sees all the bd nodes ahead of it in OPEN list. When it enters the next level at depth (d+1) it's sees bd+1 nodes in the OPEN list. The size of OPEN grows exponentially with depth.
4. Quality of solution: BFS loses out on space complexity. It makes up on the quality on the solution. Since it pushes into the search space level by level, the BFS inspects candidate solutions in increasing order of solution length.
BFS will always find the shortest solution whereas DFS dives down into the search tree. It backtracks, if it reaches a dead end and tries other parts of the search space.
The first solution found which holds no guarantee that it will be the shortest one.
No comments:
Post a Comment