Computer Science Homework Help

Try to solve the problems 8-puzzle seen in class by using hill climbing search and random restart(Just add a loop to the hill climbing search algorithm and keep track of the max in every iteration). . Formulate the problem and provide the algorithm. Please comment your results.

Please do not plagiarize

You can refer to below:

-Random restart hill climbing (pag. 124). This is an update of Hill climbing search. It applies the algorithm over and over again until the global maximum is reached. There is no guarantee to avoid falling into a local optima, but it increases the chances to reach the Global optima.

Picture Hill_Climbing.jpg and pg 123 of textbook. One step of the algorithm is moving one queen up or down in its column. From (a) f=17 by applying hill climbing reaches a local minimum for the objective function f=1(b) and from there, with this algorithm it’s impossible to reach the global minimum=0; From (b) the value increases regarding the step taken.

By running this algorithm several times from different initial states, falling into local optima is less likely.

-Simulated annealing pg 125 See https://en.wikipedia.org/wiki/Simulated_annealing