AI_TEST-2

Which of the following is (are) drawback(s) of Hill Climbing?

• Global Maxima

• Local Maxima

• Diagonal Ridges

• Plateaus

Select the CORRECT statement-

• Local beam search (with k nodes in memory) is the same as k random-start searches in parallel.

• Simulated annealing with temperature T = 0 behaves identically to greedy hill-climbing search

• Enforced Hill Climbing performs a depth-first search from a local minima.

• In Tabu Search, we never make a currently tabu’ed step.

Select the CORRECT statements -

• Genetic Algorithm has the effect of “jumping” to completely new parts of search-space, and making “non-local” moves.

• As the size of the tabu list increases to infinity, tabu search reduces to a systematic search.

• Greedy Hill Climbing with Random Restarts is asymptotically complete, whereas Random Walk is not.

• If the initial temperature in Simulated Annealing is set too small, the search can get stuck at a local optimum.

Consider the Hill Climbing Search algorithm for the N-Queens problem with N = 4. The image represents the start state. We want to reach a state i.e. configuration of the board with 4 queens such that no two queens attack each other. The objective function we consider is the number of pairs of queens that attack each other and we want to minimise this objective function. The successor function we consider is moving a single queen along its column by one square either directly up or directly down.
Let the objective function for the start state = x , the number of neighbours of the start state = y, the objective function of the neighbour of the start state with the lowest objective function = z, then what is the value of 2x + y + 3z ?

Consider the Hill Climbing Search algorithm for the N-Queens problem with N = 4. The image represents the start state. We want to reach a state i.e. configuration of the board with 4 queens such that no two queens attack each other. The objective function we consider is the number of pairs of queens that attack each other and we want to minimise this objective function. The successor function we consider is moving a single queen along its column by one square either directly up or directly down.we apply the hill climbing algorithm to minimise the objective function. The hill climbing algorithm stops when the objective function becomes 0 i.e. no two queens attack each other. To break ties b/w two neighbours with the same objective function pick the neighbour obtained by moving the queen in the lower column number (a < b < c < d) and if a tie still exists pick the neighbour obtained by moving the queen downward. The number of steps required by the hill climbing algorithm is:

Consider the 1-D state space shown by the image below. For which of the following start state regions using the greedy local search hill-climbing algorithm will we not reach the global maximum ?

• A

• B

• C,D

• E

• F

Consider a Constraint Satisfaction Problem (CSP) where we need to assign values to three variables - X, Y, and Z. The domain for each variable is {1, 2, 3}. The following constraints must be satisfied:

1. 1) X+Y>Z

2. 2) X>Y

3. 3) Z<X+Y

Based on the revised constraints, which of the following assignments is a valid solution for the variables X, Y, and Z?

• a) X=1, Y=3 , Z=2

• b) X=2, Y=1, Z=3

• c) X=3, Y=2, Z=1

• d) X=3, Y=1, Z=2

Consider the map of AI-Land.

AI-Land is divided into 7 regions. Two regions are said to be neighbors if they share an edge (or a part of an edge - e.g., 2 and 6 are neighbors). We want to color the regions using one of the 3 colors - Green, Yellow, or Purple so that no 2 neighbors have the same color.

Suppose we assign Green to the region identified in the previous question. Let x be the label number of the region that we should color next. Let y be the number of colors we can assign to it. What is 4x+3y?

Consider the map of AI-Land.

AI-Land is divided into 7 regions. Two regions are said to be neighbors if they share an edge (or a part of an edge - e.g., 2 and 6 are neighbors). We want to color the regions using one of the 3 colors - Green, Yellow, or Purple so that no 2 neighbors have the same color. Consider that we first color Region 1 with Purple and want to color Region 6 next. Which of the following color (s) should we use?

• Purple

• Green

• Yellow

• We can’t use any colour

(True/False) Consider the following constraint graph, where nodes represent variables, edges represent constraints between them and the domains of each variable are indicated using the set notation. If we perform arc-consistency on this constraint graph, then we will be able to detect that no solution is possible.

• True

• False