One-point Hill Climbing can get stuck due to which of the following phenomenon?
- Local Maxima
- Inadmissible heuristic
- Ridges
- Plateau
Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this communityOne-point Hill Climbing can get stuck due to which of the following phenomenon?
This question really looks like a homework problem, in part because it is too vague (what does it mean to 'get stuck' exactly?).
Hill climbing stops when it reaches a local maximum.
Hill climbing is an uninformed search algorithm, so it does not make use of a heuristic.
Hill climbing may or may not stop on a ridge, depending on the implementation. Some common implementations move randomly when equal (but not better) moves are available. Others stop in this situation.
Hill climbing may or may not stop on a plateau, depending on how the implementation handles the case of ties, like with ridges. Whether you think it 'gets stuck' depends a lot on your definition. Implementations that stop when encountering a tie will stop. Implementations that don't stop will eventually exit the plateau through random movements, but it could take infinite time if your movements in the gradient-free region are unlucky.
It should be crystal clear to those who understand the word "stuck" that the term "get stuck" means, in this context, to either
reach an answer that appears to be an optimum before reaching an optimum and stopping or
never stopping.
The answer to the question is simply 1.
If 4. is the global maximum, that it is a plateau is irrelevant. The value (height) function finds all values on the surface of the plateau equal in value.
If 3. is encountered but it is not a local maximum, the gradient would direct ascension around the ridge unless the ridge were perfectly perpendicular to the normal line.
If a logical system were added to the inversion (gradient ascent) of gradient descent to augment it in some way, which is the only way 2. would make sense, it would be inadmissible to allow the insertion of rules, heuristic or not, that were inadmissible, so 2. applies only if the system designer was of the kind that does not understand fault resistant systems architecture.