How does randomized hill-climbing choose the next move each time ?
2016
How does randomized hill-climbing choose the next move each time ?
- A.
It generates a random move from the moveset, and accepts this move.
- B.
It generates a random move from the whole state space, and accepts this move.
- C.
It generates a random move from the moveset, and accepts this move only if this move improves the evaluation function.
- D.
It generates a random move from the whole state space, and accepts this move only if this move improves the evaluation function.
Attempted by 89 students.
Show answer & explanation
Correct answer: C
Answer: Randomized hill-climbing picks a single random neighbor from the available moves (the moveset) and accepts it only if it improves the evaluation (objective) function.
Procedure:
From the current state, generate one random neighbor from the moveset.
Evaluate that neighbor using the evaluation function.
If the neighbor's evaluation is better than the current state's, accept the neighbor as the new current state; otherwise, remain at the current state.
Repeat these steps until no further improvements are found or a stopping condition (such as a maximum number of iterations) is reached.
Notes:
The algorithm samples from local neighbors (the moveset), not the entire state space.
Because it only accepts improvements, it can get stuck in local maxima; random restarts or other metaheuristics are commonly used to mitigate this.
Implementation detail: some variants allow accepting equal-quality moves or use probabilistic acceptance to encourage exploration.
A video solution is available for this question — log in and enroll to watch it.