Search Algorithms: BFS, DFS, and UCS

Breadth First Search (BFS)

• Procedure: Uses a queue (FIFO) to traverse level by level.
• Traversal: First, visit all nodes at the present depth, then move on to nodes at the next depth level.

Depth First Search (DFS)

• Procedure: Uses a stack (LIFO) to dive deep into each branch before moving to the next sibling.
• Traversal: Start at the root (node 1), go to its child (node 2), and continue downward as deep as possible, then backtrack.
  • Example: Node 1 → Node 2 → Node 3 → Node 4 → Node 5 → Node 6 → backtrack to Node 5 → backtrack to Node 4... until all nodes are visited.
• Backtracking: DFS is often associated with backtracking.
• Strengths:
  • Suitable when there are space restrictions.
  • Works well if many solutions exist or tree depth can be tuned.
• Weaknesses:
  • Can get caught in infinite loops if cycles are present in the graph.
  • Might take a long time if the solution is at a deeper level of the tree.

Example

• Start at node S:
  • Nodes available: A, B, C.
  • First visit A → expand nodes D, E, G.
  • Follow nodes in stack order (latest on top): D → E → G.
• Goal: Reached G by expanding 5 nodes, path: S → A → G, cost: 18.
• Comparisons: Not the most optimal path, another path (S → C → G) costs 13.

Uniform Cost Search (UCS)

• Procedure: Uses a priority queue to select nodes based on cumulative cost.
• Traversal: Prioritizes nodes with the least cost from the root.
  • Assume all nodes are equidistantly accessible from root node.

Example

• Start at node S:
  • Nodes available: A (cost 3), B (cost 1), C (cost 8).
  • First visit B → expand path to G (cost 21).
  • Next visit A → expand nodes D (cost 6), E, G (cost 18).
  • Continue using priority queue to select next node.
• Goal: Reached optimal path S → C → G with cost 13.
• Comparisons: UCS found optimal solution with minimal cost of 13.

Comparison of Algorithms

• BFS: Expanded 7 nodes, total cost: 38.
• DFS: Expanded 5 nodes, total cost: 28.
• UCS: Expanded 7 nodes, total cost: 27 but found the optimal path with cost 13.

UCS Pros & Cons

• Pros:
  • Complete and optimal.
  • Handles loops gracefully.
• Cons:
  • Potentially high computational complexity due to multiple directions being explored.

Implementation Exercise

• Solve a problem from node A to B using all three search strategies (BFS, DFS, UCS).
• To be discussed in the next session.

Note: For complex problems, avoid blind search strategies and use approaches with more environmental info when possible.