Unit-2 short answers

 

🔹 1. What is the difference between Breadth-First Search and Depth-First Search?

Answer:

• Breadth-First Search (BFS):
  Explores all nodes level by level using a queue (FIFO) structure.

• Depth-First Search (DFS):
  Explores deep into one branch before backtracking, using a stack (LIFO) or recursion.

Example Tree:

        A
       / \
      B   C

• BFS Order: A → B → C

• DFS Order: A → B → (backtrack) → C

---

🔹 2. What is Alpha-Beta Pruning?

Answer:

Alpha-Beta Pruning is an optimization technique for the Minimax algorithm used in adversarial game playing. It prunes branches of the game tree that don't affect the final decision.

Example:

• If one move leads to a guaranteed win, other branches are skipped.

• This reduces time and space complexity without losing the optimal move.

---

🔹 3. What is the difference between informed and uninformed search strategies?

Answer:

• Uninformed Search:
  No domain knowledge is used (e.g., BFS, DFS). It explores blindly.

• Informed Search:
  Uses heuristics to guide the search more efficiently (e.g., A*, Greedy search).

Example (Map Navigation):

• BFS: Tries all roads randomly.

• A*: Uses estimated distances (heuristics) to find the shortest path faster.

---

🔹 4. Define A* Algorithm.

Answer:

The A* (A-Star) algorithm finds the least-cost path to a goal using:

f(n) = g(n) + h(n)

Where:

• g(n): Actual cost from start to node n

• h(n): Estimated cost from n to the goal (heuristic)

Example:
In a grid maze:

• A* may choose diagonal paths because it "knows" they're shorter, while BFS might explore all paths equally.