Artificial Intelligence - Local Search Starting from a randomly generated state of the 15-puzzle game, steepest-ascent hill-climbing (the vanilla version of hill-climbing search) gets stuck 76% of the...

Artificial Intelligence - Local Search

Starting from a randomly generated state of the 15-puzzle game, steepest-ascent hill-climbing (the vanilla version of hill-climbing search) gets stuck 76% of the time, i.e., solving only 24% of problem instances. But it works very quickly, i.e., it takes just 6 steps on average when it succeeds and 5 steps when it gets stuck. In contrast, if sideways moves are allowed, this raises the percentage of problem instances solved by hill-climbing from 24% to 81%, with the success at a cost: the algorithm averages roughly 7 steps for each successful instance and 32 steps for each failure. Now suppose that we are implementing

random-restart hill climbing

(i.e., if a search fails, it keeps to try, and try, until it gets a success) by the following two versions:

1. one uses vanilla steepest-ascent hill climbing, and


2. the other one uses hill climbing with sideways moves.

Can you please tell which version of

random-restart hill-climbing
listed above runs faster
on average
? Please justify your answer.

Please answer the posted question. The question is regarding a

RANDOM-RESTART

hill-climbing algorithm.