Heuristic Search Techniques: Greedy, Hill-Climbing, and Beam Search Quiz Quiz

Explore the fundamentals of heuristic search algorithms with questions on Greedy, Hill-Climbing, and Beam Search techniques. Assess your understanding of their strategies, advantages, and practical applications in artificial intelligence and problem-solving.

1. Heuristic Function Role

   Which best describes the primary purpose of a heuristic function in search algorithms such as Greedy and Hill-Climbing search?

   1. To estimate the cost from the current state to the goal
   2. To generate random moves at each step
   3. To guarantee the shortest path is found
   4. To check for loops in the search path

   Explanation: The heuristic function is designed to estimate the cost or distance from the current state to the goal, guiding the algorithm's choices. It does not check for loops or generate random moves; those functions pertain to different parts of the algorithm or other algorithms entirely. Also, the use of a heuristic does not guarantee finding the shortest path, since greedy and hill-climbing algorithms are not always optimal.

2. Greedy Search Characteristics

   What is a defining characteristic of the Greedy Best-First Search algorithm when solving a route-finding problem?

   1. It avoids revisiting nodes entirely
   2. It only moves to neighbors with a lower path cost
   3. It always selects the node with the lowest heuristic value
   4. It evaluates all nodes at each step

   Explanation: Greedy Best-First Search selects the node that appears closest to the goal according to the heuristic function, specifically seeking the lowest heuristic value. It does not necessarily evaluate all nodes or restrict itself to neighbors with lower path costs. While it may avoid cycles, avoiding all repeated nodes is not guaranteed by this strategy alone.

3. Hill-Climbing vs. Greedy Search

   How does the Hill-Climbing search algorithm primarily differ from Greedy Best-First Search?

   1. Hill-Climbing only considers immediate neighbors, while Greedy may jump further ahead
   2. Hill-Climbing guarantees an optimal solution, while Greedy does not
   3. Hill-Climbing uses a random heuristic, while Greedy uses a fixed heuristic
   4. Hill-Climbing explores all paths, while Greedy explores only the optimal one

   Explanation: Hill-Climbing is a local search and evaluates only immediate neighboring states, whereas Greedy Best-First Search can select the most promising node from the entire frontier. Neither algorithm guarantees an optimal solution, so the second option is incorrect. Both use a fixed heuristic, not a random one, and neither explores all possible paths exhaustively.

4. Beam Search Parameter

   In Beam Search, what does the 'beam width' parameter control during the search process?

   1. The length of the solution path
   2. The number of best nodes kept at each level
   3. The size of the heuristic function output
   4. The depth of traversal allowed

   Explanation: Beam width specifies how many of the most promising nodes (according to the heuristic) are retained at each level during Beam Search. It does not determine the length of the final solution path or the search depth explicitly. The beam width is also unrelated to the actual values produced by the heuristic function.

5. Limitation of Greedy Search

   Which limitation is commonly associated with the Greedy Best-First Search algorithm?

   1. It can get stuck in loops or miss the optimal path
   2. It requires exponential memory for every step
   3. It can solve every problem optimally
   4. It does not use any heuristic function

   Explanation: Greedy Best-First Search may revisit nodes or overlook the optimal path due to relying solely on the heuristic. It doesn't require memory for every path explored (as with exhaustive algorithms), and it does use heuristic guidance. The claim that it always solves problems optimally is incorrect.

6. Hill-Climbing Drawback

   What is a common drawback of the basic Hill-Climbing algorithm?

   1. It requires a complete map of all possible states
   2. It ignores heuristic information
   3. It always finds the global maximum
   4. It can get stuck on local maxima

   Explanation: Hill-Climbing often gets stuck at local maxima or plateaus where no neighboring state is better, potentially missing the global optimum. It certainly does not guarantee finding the global maximum, and it does use heuristic information to make local decisions. A complete map is not required for local evaluation.

7. Beam Search Application

   In which scenario might Beam Search offer better performance compared to full Breadth-First Search?

   1. When searching in a cyclic undirected graph
   2. When memory resources are limited and only the best few paths are tracked
   3. When the heuristic function is always inaccurate
   4. When all paths are equally promising

   Explanation: Beam Search restricts memory usage by maintaining only a fixed number of best candidate nodes, making it practical when resources are limited. In cyclic graphs or with inaccurate heuristics, effectiveness can decline. If all paths are equally good, Beam Search provides little advantage over exhaustive searching.

8. Heuristic Admissibility

   Which statement about heuristic functions is correct in the context of these search algorithms?

   1. Heuristics guarantee that every search will be complete
   2. Heuristics are only used in backward search
   3. An admissible heuristic never overestimates the true cost to the goal
   4. A heuristic must always return zero

   Explanation: An admissible heuristic is defined by its property of never overestimating the real cost to reach the goal, crucial in some informed search algorithms. Heuristics do not always return zero and are not limited to backward search. Finally, using a heuristic alone does not guarantee the search algorithm's completeness.

9. Variation in Hill-Climbing

   Which technique can help the Hill-Climbing algorithm escape from plateaus or local maxima?

   1. Always selecting the lowest cost path
   2. Random restarts
   3. Reducing beam width
   4. Using no heuristic function

   Explanation: Random restarts enable Hill-Climbing to begin the search anew from different random positions, helping to overcome getting stuck at plateaus or local maxima. Reducing beam width is to modify Beam Search, not Hill-Climbing. Both using no heuristic and always picking the lowest cost path pertain to other search methods and do not address this algorithm's primary limitation.

10. Comparison of Techniques

    Which statement best distinguishes Beam Search from basic Greedy and Hill-Climbing algorithms?

    1. Beam Search keeps multiple paths at each step, while Greedy and Hill-Climbing follow only one
    2. Beam Search always finds the shortest path, unlike the others
    3. Greedy and Hill-Climbing never use heuristics
    4. Beam Search ignores heuristic values in selection

    Explanation: Beam Search preserves several top-scoring candidates at every level, increasing diversity in possible solutions, whereas Greedy and Hill-Climbing generally pursue a single path at a time. None of these algorithms guarantee the shortest path and both Greedy and Hill-Climbing are heuristic-based. Beam Search does not ignore heuristic values, but uses them to select the top candidates.