- 2070 Bhadra · 4+4 marks
Informed vs blind search; DFS vs BFS
Short answer
Informed search uses a heuristic h(n) to guide toward the goal; blind search uses only the problem definition. BFS expands level by level with a queue, is complete and optimal for equal costs, with time and space O(b^d). DFS uses a stack, goes deep first, needs O(b*m) space but may fail in infinite spaces.
Differentiate between informed and blind search. How is depth first search different from breadth first search? Compare with evaluation parameters.
Informed vs blind (uninformed) search
| Basis | Blind (uninformed) search | Informed (heuristic) search |
|---|---|---|
| Knowledge used | Only the problem definition | Problem-specific knowledge as a heuristic h(n), the estimated cost to the goal |
| Direction | Systematic, no idea of goal direction | Guided towards the goal |
| Efficiency | Explores many unnecessary nodes; slow | Explores fewer nodes; faster |
| Time and space | Usually very high | Much lower with a good heuristic |
| Optimality | Only some (BFS with equal cost, UCS) | A* with an admissible heuristic is optimal |
| Examples | BFS, DFS, uniform-cost, depth-limited, iterative deepening | Greedy best-first, A*, hill climbing, beam search |
DFS vs BFS
- BFS expands nodes level by level using a FIFO queue; DFS goes as deep as possible along a branch before backtracking, using a LIFO stack (or recursion).
- Example tree A → (B, C), B → (D, E), C → (F, G): BFS visits A B C D E F G; DFS visits A B D E C F G.
With b = branching factor, d = depth of shallowest goal, m = maximum depth:
| Evaluation parameter | BFS | DFS |
|---|---|---|
| Completeness | Complete | Not complete in infinite or cyclic spaces |
| Optimality | Optimal when step costs are equal | Not optimal |
| Time complexity | O(b^d) | O(b^m) |
| Space complexity | O(b^d) (stores all nodes of a level) | O(b·m) (stores one path) |
| Data structure | Queue | Stack |
| Behaviour | Finds the shallowest goal | May find a deep goal first or go into an infinite branch |
| Suitable when | Solution is shallow, shortest path needed | Memory is limited, many solutions deep in the tree |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Searching: BFS vs DFS comparison · Artificial Intelligence, chapter 3 · asked 5×
- Informed vs uninformed; min-max; alpha-beta · Artificial Intelligence, chapter 3
- Advantage of depth limit search · Artificial Intelligence, chapter 3
- Differences between DFS and BFS · Data Structure and Algorithm, chapter 10
- BFS and DFS with example · Data Structure and Algorithm, chapter 10 · asked 4×
- Breadth first traversal in graph · Data Structure and Algorithm, chapter 10 · asked 2×
- Rectangular beam dimensions, depth twice breadth · Strength of Materials, chapter 7