In the following 4-queens board, 3 pairs of queens attack each other. Let the va

Question

In the following 4-queens board, 3 pairs of queens attack each other. Let the value function be defined as v(board) = 6 - #attacking pairs. Therefore, the following board has value 6-3=3. Suppose of a board is generated by first selecting a column where the board's value would be maximized keeping the other queens unchanged, with ties broken randomly. This way each given board (like the one below) will have 4 successors. Generate 4 successor of the following board (the arts values: will not be unique) and show their values. Which of the above successors will be selected by the hill-climbing algorithm as the next state? Simulated annealing will first select one of these 4 successors at random, and then check if it has a higher value than the current state (i.e, value > 3), in which case that successor will be returned as the next state. But if the selected successor has a lower value (i.e., 0, 1, 2, or 3), then it may be returned with some probability. Among the successors that you generated in part (a), what are the probabilities of the successors with value lessthanorequalto 3 of being selected as next state, if the temperature is T?

Explanation / Answer

Part a) Starting from the left-most column and moving towards right-

v(board) = 6 - 2

=4

v(board) = 6 - 3

=3

Successor 3 is same as the given board state as any other arrangement would decrease the board value.

v(board) = 6 - 3

= 3

v(board) = 6 - 1

= 5

Part b) Successor 4 will be selected by the hill-climbing algorithm as the next state because it is the steepest ascent i.e. it is nearest to the local maxima which in this case will be v(board) = 6.

Part c) There are two successors with value<=3, successor 3 & successor 2 both of which have value 3. Now the probability of them being selected as the next state is given by->

P(x_as_next_state)=exp( (old cost - new cost)/ temperature)

considering value as cost here, and temperature T we get :

P(x)= exp( (3 - 3)/ T )

=exp(0)

=1.

Hence the probability of successor 2 & 3 to be selected as next state is 1.

Successor 1 x x x x

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.