Essential Search Strategies: BFS, DFS, and A* in Artificial Intelligence Quiz

Explore fundamental search strategies in Artificial Intelligence, including Breadth-First Search, Depth-First Search, and the A* algorithm. This quiz helps you understand their key principles, characteristics, and applications for solving pathfinding and problem-solving tasks.

1. BFS Node Expansion Order

   In Breadth-First Search (BFS), which nodes are expanded first in a search tree when finding a solution path?

   1. Nodes with the highest cost
   2. Nodes that are at the shallowest depth
   3. Nodes at the deepest level
   4. Randomly selected nodes

   Explanation: BFS always expands nodes at the shallowest depth first, ensuring the algorithm explores all nodes at one level before moving to the next. This property often finds the shortest path in an unweighted graph. Nodes with the highest cost are not prioritized, random node selection is not characteristic of BFS, and expanding the deepest nodes applies instead to Depth-First Search.

2. DFS Characteristic

   Which key feature distinguishes Depth-First Search (DFS) from Breadth-First Search (BFS) when searching a simple maze?

   1. DFS uses a heuristic to order node expansion
   2. DFS explores one possible path as deeply as possible before backtracking
   3. DFS expands all neighbors at the current depth first
   4. DFS always finds the shortest path

   Explanation: DFS goes as deep as possible along a branch before backtracking, making it memory efficient in some cases. It does not guarantee the shortest path as BFS does in unweighted graphs. Expanding all neighbors at the current depth is a BFS trait, and using heuristics is a feature of informed algorithms like A*, not DFS.

3. A* Algorithm Components

   What does the evaluation function f(n) in the A* search algorithm represent for a given node n?

   1. The sum of the path cost to reach n and the estimated cost from n to the goal
   2. The number of visited nodes so far
   3. The cost of reaching the goal from the start without estimation
   4. The maximum branching factor of the tree

   Explanation: In A*, f(n) = g(n) + h(n), where g(n) is the cost to reach node n, and h(n) is the heuristic estimate from n to the goal. This guides the search efficiently. The function does not represent the branching factor or count visited nodes. The cost of reaching the goal without estimation ignores the importance of heuristics in A*.

4. Completeness of BFS

   Under what conditions is Breadth-First Search (BFS) complete when used for pathfinding in a finite graph?

   1. BFS is incomplete if the solution is at the first level
   2. BFS ignores certain nodes, making it incomplete
   3. BFS is always complete in finite graphs, as it systematically explores all nodes
   4. BFS is never complete regardless of the graph

   Explanation: BFS is guaranteed to be complete in finite graphs since it explores every node at each level before moving deeper, ensuring no solution is missed. If the solution is at the first level, it will still be found, not ignored. BFS does not intentionally skip nodes, and claiming it's never complete is incorrect for finite graphs.

5. DFS Memory Usage

   Why does Depth-First Search (DFS) typically use less memory compared to Breadth-First Search (BFS) in tree traversal problems?

   1. DFS saves copies of the entire tree
   2. DFS only needs to store a single path from the root to a leaf at any time
   3. DFS stores all possible paths explored so far
   4. DFS stores the shortest encountered path at each level

   Explanation: DFS stores only the current path from the root to a node and backtracks when needed, resulting in much lower memory requirements. Storing all possible paths would significantly increase memory usage. Saving an entire tree or the shortest path at each level is not part of standard DFS behavior.

6. Heuristic Role in A*

   What is the primary role of the heuristic function h(n) in the A* algorithm?

   1. To randomly choose the next node to expand
   2. To estimate the remaining cost to reach the goal from node n
   3. To increase the branching factor of the search
   4. To store all visited nodes for later review

   Explanation: The main job of the heuristic is to provide an estimate of the lowest possible cost to reach the goal, helping A* make informed decisions. Heuristics are not used for random choices or simply for storing nodes. Increasing the branching factor is not a heuristic's function and can make searches inefficient.

7. BFS Application

   Suppose you are searching for the shortest route in an unweighted road network; which algorithm should you typically use and why?

   1. Breadth-First Search, because it guarantees the shortest path in unweighted graphs
   2. Depth-First Search, because it avoids cycles
   3. Depth-First Search, because it visits each node just once
   4. A* algorithm, because it ignores path costs

   Explanation: BFS is well-suited for finding the shortest path in unweighted graphs because it explores all nodes at each depth level, guaranteeing no shorter path exists. DFS is not designed for shortest path problems and visiting each node once does not ensure shortest routes. A* can find shortest paths but does not ignore path costs; it requires a heuristic.

8. DFS Infinite Path Trap

   In a search space that contains very deep or infinite paths and no solution, why can Depth-First Search (DFS) fail to find a solution?

   1. DFS always chooses the shortest path first
   2. DFS always backtracks after each node
   3. DFS uses too much memory to store all paths
   4. DFS may follow an infinite branch and never backtrack

   Explanation: DFS can get stuck exploring infinitely long paths if backtracking is never triggered, causing the algorithm to fail in infinite or very deep spaces without a solution. While DFS eventually backtracks, infinite branches prevent this in some cases. Memory use is lower in DFS, and it does not guarantee the shortest path is chosen first.

9. Optimality in Search

   Which condition must a heuristic function satisfy for the A* algorithm to be guaranteed to find the optimal path?

   1. The heuristic must never overestimate the true cost to the goal (admissibility)
   2. The heuristic must return the maximum possible cost
   3. The heuristic must always be greater than the actual cost
   4. The heuristic should be random for varied results

   Explanation: An admissible heuristic always provides estimates that are equal to or less than the actual cost, ensuring that A* will find the optimal path. Returning the maximum possible cost or values greater than the actual cost could cause optimal solutions to be missed. Random heuristics can result in inconsistent or incorrect paths.

10. Search Tree vs. Search Graph

    What is the main reason Breadth-First Search (BFS) needs to keep track of visited nodes when applied to a graph rather than a tree?

    1. To ensure all nodes are stored in a fixed order
    2. To increase the branching factor for faster searching
    3. To avoid revisiting nodes and prevent infinite loops caused by cycles
    4. To allow BFS to use heuristics for node selection

    Explanation: In graphs, cycles can cause BFS to revisit nodes endlessly, making it essential to mark visited nodes and avoid infinite loops. Storing nodes in a fixed order is not unique to BFS in graphs, and branching factor manipulation or heuristic use is not relevant to this context.