Q1. Scenario: A delivery drone needs to find the shortest route to multiple drop-off points. What search algorithm would you use? Compare uninformed vs informed search.
Uninformed: BFS or Dijkstra (no heuristic). Informed: A* with Euclidean distance heuristic. A* is more efficient. For multiple points (TSP), use A* with state representing visited set.
Q2. Scenario: You need to arrange five tasks with dependencies (like project scheduling). How would you model this as a search problem? What algorithms apply?
Model each state as a set of completed tasks, actions as starting a new task whose prerequisites are met. Use topological sort (not search) or heuristic search (e.g., to minimize makespan).
Q3. Scenario: A robot navigates a maze with loops. How does BFS differ from DFS in terms of completeness and optimality? Which one would you use and why?
BFS is complete and optimal (shortest path) but uses more memory. DFS may not find shortest path and can get stuck in infinite loops without cycle detection. Use BFS for unweighted mazes.
Q4. Scenario: In a puzzle like the 8-puzzle, A* with Manhattan distance heuristic is optimal. Why does A* guarantee optimality, and what is the requirement for the heuristic?
A* is optimal if the heuristic is admissible (never overestimates cost to goal). Manhattan distance is admissible for 8-puzzle. The algorithm expands nodes with lowest f(n)=g(n)+h(n), ensuring the first goal found is optimal.
Q5. Scenario: A pathfinding game uses Dijkstra's algorithm on a grid. How would you optimize it for larger maps?
Switch to A* with heuristic (e.g., Euclidean). Use bidirectional search, jump point search (JPS), or hierarchical pathfinding (waypoints). For huge maps, use precomputed navmeshes.