II$.$ Hill Climbing

Next, complete the solve$()$ method for the HillclimbingSolver class below.

The hill$-$climbing search algorithm is the most basic local search technique. At each step the current

node is replaced by the neighbor with the highest value. $[$AIMA $3$rd ed$,$ Chapter $4]$

function HILL$-$CLIMBING$($problem$)$ returns a state that is a local maximum

current larr MAKE$-$NODE $($problem$.$INITIAL$-$STATE$)$

loop do

neighbor larr a highest$-$valued successor of current

if neighbor.VALUE $$ current.VALUE then return current.STATE

current larr neighbor

Pseudocode for the hill climbing function from the AIMA textbook. Note that our Problem class is already a "node",

so the MAKE$-$NODE line is not required.

In $[]$: class HillclimbingSolver:

Parameters

epochs : int

The upper limit on the number of rounds to perform hill climbing; the

algorithm terminates and returns the best observed result when this

iteration limit is exceeded.

def$\_\_$init$\_($self$,$ epochs$=100)$:

self.epochs $=$ epochs

def solve$($self$,$ problem$)$:

$""$I$"$ Optimize the input problem by applying greedy hill climbing.

Parameters

problem : Problem

An initialized instance of an optimization problem. The Problem class

interface must implement a callable method "successors$()"$ which returns

a iterable sequence $($i$.$e$.,$ a list or generator$)$ of the states in the

neighborhood of the current state, and a property "utility" which returns

a fitness score for the state. $($See the 'TravelingSalesmanProblem' class

for more details.$)$

Returns

Problem

The resulting approximate solution state of the optimization problem

Notes

$(1)$ DO NOT include the MAKE$-$NODE line from the AIMA pseudocode

# TODO: Implement this function!

for $\_$ in $(3)$:

neihbor problem. successors $(),)$

if$($neihbor$.$some $$ problem. something$)$:

raise NotImplementedError