Pseudo$-$code for the Simulated$-$Annealing algorithm is given below; note that in the version

of the algorithm given, we wish to maximize the objective function $($i$.$e$.$ walk uphill$).$

function SIMULATED$-$ANNEALING$($ problem, schedule$)$ returns a solution state

inputs: problem, a problem

schedule, a mapping from time to "temperature"

local variables: $T,$ a "temperature" controlling the probability of downward steps

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

for $t=1$ to $$ do

Tlarr schedule $(t)$

if $T=0$ then return current

next larr a randomly selected successor of current

$Elarrnext.$VALUE $-$ current. VALUE

if $E>0$ then current larr next

else current larr next only with probability $e^{\frac{E}{T}}$

$($i$)$ Describe the idea behind the Simulated$-$Annealing algorithm. Be sure to briefly explain the role

of each component in the algorithm.

$($ii$)$ Indicate how you could change the Simulated$-$Annealing algorithm so that it implements a

"strict" version of hill$-$climbing.

$($iii$)$ With regards to Simulated$-$Annealing, what is the probability of accepting the following moves?

Assume the problem is trying to maximize the objective function. $($If you don't have a calculator,

you can leave your answers in the form of mathematical expressions$)$