An Introduction to Artificial Intelligence Week 4
Course Name: An Introduction to Artificial Intelligence
Course Link: Click Here
These are An Introduction to Artificial Intelligence Answers Week 4
Q1. We want to sort an array of n distinct integers using local search. The start state is a random permutation of the integers. All neighbors of a state are those permutations that can be achieved by swapping one pair of different numbers. For n=7, which of the following are INCORRECT options?
a. Number of reachable states from the start state is 77 .
b. The number of reachable states from the start state depends on the randomly sampled initial state.
c. Every state has 42 neighbors.
d. For S = {i|a_i < a_i+1}, minimizing |S| leads to the desired goal state.
Answer: a, b, c, d
These are An Introduction to Artificial Intelligence Answers Week 4
Q2. Which of the following are correct statements?
a. Local search through random sampling is not asymptotically complete because it takes a lot of steps.
b. Random walk with restarts is asymptotically complete
c. Hill climbing is not asymptotically complete because it can get stuck in plateaus/local optima.
d. Hill climbing with sideways moves is asymptotically complete.
Answer: b, c
These are An Introduction to Artificial Intelligence Answers Week 4
Q3. Which of the following statement is correct about the temperature parameter in simulated annealing?
a. If the initial temperature is set too small, the search can get stuck at a local optimum.
b. The tendency to remain at a local optimum increases with an increase in temperature.
c. It is increased over time to provide stability to the search process.
d. It is increased over time to accelerate exploration.
Answer: a. If the initial temperature is set too small, the search can get stuck at a local optimum.
These are An Introduction to Artificial Intelligence Answers Week 4
Q4. Identify all differences between Simulated Annealing (SA) and Genetic Algorithms (GA)
a. GA maintains multiple candidate solutions while SA does not.
b. GA provides stronger guarantees about convergence to the global optimum than SA
c. SA has no parameters to set whereas GA requires you to set multiple parameters such as crossover rate
d. GA will always converge to an optimal solution faster than SA on any given problem.
Answer: a. GA maintains multiple candidate solutions while SA does not.
These are An Introduction to Artificial Intelligence Answers Week 4
Q5. Which of the following optimization objectives will convert a constraint satisfaction problem to an equivalent optimization problem?
a. Minimize the number of satisfied constraints
b. Maximize the number of satisfied constraints
c. Maximize R where R is 0 when all constraints are satisfied and 1 otherwise
d. Maximize R where R is 1 when all constraints are satisfied and 0 otherwise
Answer: b, d
These are An Introduction to Artificial Intelligence Answers Week 4
Q6. Which of the following statements are correct about Local Beam Search?
a. It consumes more memory than greedy hill-climbing search regardless of beam size
b. It can never find the optimal solution with a beam size of k if it does not find the optimal solution with a beam size > k for a single run
c. It may find the optimal solution with a beam size of k even if it does not find the optimal solution with a beam size > k for a single run
d. Local Beam Search with a beam size of k is equivalent to performing k random walk searches with random starts in parallel.
Answer: c. It may find the optimal solution with a beam size of k even if it does not find the optimal solution with a beam size > k for a single run
These are An Introduction to Artificial Intelligence Answers Week 4
Q7. Consider a state space having 3 states: s1, s2 and s3. The value of each state is V(s1) = 0, V(s2) = 4, V(s3) = 2. There can be transitions from s1 to s2, s2 to s1 and s3, and s3 to s2. Starting at s1, what is the probability that we end up back at s1 after 2 steps of simulated annealing? Assume that we follow a temperature schedule of [10, 5, 1].Next state is chosen uniformly at random whenever there are multiple possibilities.
Round answer to 3 digits after decimal point.
Answer: 0.225
These are An Introduction to Artificial Intelligence Answers Week 4
Q8. In the previous question, what is the probability that simulated annealing terminates at the state with highest value? Assume that the run terminates after 3 steps.
Round answer to 3 digits after decimal point.
Answer: 0.966
Q9. Which of the following statements are correct about Tabu Search?
a. It never visits the same state more than once.
b. It never visits a state that is currently in the tabu list.
c. As the size of the tabu list increases to infinity, tabu search reduces to a systematic search.
d. It is guaranteed to escape any local optimum it is stuck in.
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 4
Q10. Assume that we have a function y = (x – 1)4. Starting at x = 2, which of the following values of the step size λ will allow gradient descent to converge to the global minimum?
a. 0.05
b. 0.2
c. 0.5
d. 0.75
Answer: a, b
These are An Introduction to Artificial Intelligence Answers Week 4
These are An Introduction to Artificial Intelligence Answers Week 4
More Solutions of An Introduction to Artificial Intelligence: Click Here
More NPTEL Solutions: https://progiez.com/nptel/
This content is uploaded for study, general information, and reference purpose only.