# NPTEL An Introduction to Artificial Intelligence Assignment 3 Answers

NPTEL An Introduction to Artificial Intelligence Assignment 3 Answers 2022:- All the Answers provided here to help the students as a reference, You must submit your assignment at your own knowledge.

## What is An Introduction to Artificial Intelligence?

An Introduction to Artificial Intelligence by IIT Delhi course introduces the variety of concepts in the field of artificial intelligence. It discusses the philosophy of AI, and how to model a new problem as an AI problem. It describes a variety of models such as search, logic, Bayes nets, and MDPs, which can be used to model a new problem. It also teaches many first algorithms to solve each formulation. The course prepares a student to take a variety of focused, advanced courses in various subfields of AI.

## CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of the average of best 8 assignments out of the total 12 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100

Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF THE AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.

## NPTEL An Introduction to Artificial Intelligence Assignment 3 Answers 2022:-

Q1. If h1 and h2 are two admissible heuristics, then which of the following are guaranteed to be admissible?

(A) max(h1,h2)
(B) min(h1,h2) + 1
(C) sqrt(h1*h2)
(D) h1 + h2

Q2. Which of the following evaluation functions would emulate the behavior of greedy best-first search?

(A) f(n) = g(n)
(B) f(n) = h(n)
(C) f(n) = g(n) + h(n)
(D) f(n) = 2h(n)

Q3. Which of the following graph search algorithms are guaranteed to be complete and optimal? (Assume positive edge costs)

(B) A* with zero heuristic
(C) Uniform Cost Search

Q4. Consider the following directed graph,having A as the starting node and G as the goal node, with edge costs as mentioned, and the heuristic values for the nodes are given as – {h(A)=7, h(B)=6, h(C)=5, h(D)=4, h(E)=3, h(F)=3, h(G)=0}:

Which of the following options are correct?

(A) Given heuristic function is not admissible
(B) Given heuristic function is admissible
(C) Given heuristic function is not consistent
(D) Given heuristic function is consistent

Q5. With A as the starting node and G as the goal node, we run the IDA* graph search with depths 1,2,3.. . Assume we stop as soon as the goal node is reached. At what depth will we reach the goal node? (Assume A is at depth 0)

Q6. With A as the starting node and G as the goal node, we run the IDA* graph search with depths 1,2,3.. . Assume we stop as soon as the goal node is reached. What is the optimal path from A to G predicted by IDA*? (Assume A is at depth 0)

Q7.

Pacman is a famous game in which the agent(Pacman) is controlled by the keyboard keys and the goal is to eat the maximum amount of food whilst avoiding being eaten by ghosts. Consider a version of Pacman in which there are no ghosts at all. In any state, Pacman can move left, right, up, or down with a cost of 1. Assume that Pacman can’t move into a wall. The goal of Pacman is to eat all the food in the maze(in any order).
We wish to compute admissible heuristics for this problem by relaxing the domain. Consider the following relaxation:
Pacman can now “teleport” from any cell to any other cell with a cost of 1
What is the cost of the optimal solution in the relaxed domain?

(A) Length of the shortest path through all the food in the maze
(B) Maximum of the length of the shortest path to all food items from the current location.
(C) Number of food items in the maze.
(D) None of these

Answer:- (C) Number of food items in the maze.

Q8. Is the cost of the optimal solution an admissible heuristic in the original domain? Why?

(A) No
(B) Yes, because all solutions of the relaxed domain are solutions in the original domain
(C) Yes, because all solutions of the original domain are solutions of the relaxed domain.

Answer:- (C) Yes, because all solutions of the original domain are solutions of the relaxed domain

Q9. Consider the graph below. A is the starting node and B is the goal state. We perform a depth first search branch and bound algorithm (assume zero heuristic) with upper bound cost 6.5. If there are any ties, then the algorithm chooses to expand the lexicographically smaller node. Also, we stop as soon as we reach the goal. What is the first path predicted by the algorithm?

Q10. Consider the graph below. A is the starting node and B is the goal state. We perform a depth first search branch and bound algorithm (assume zero heuristic) with upper bound cost 6.5. If there are any ties, then the algorithm chooses to expand the lexicographically smaller node. Also, we stop as soon as we reach the goal. Now, suppose I change my upper bound to 7.5. What will be the path predicted in this case?

Q11. Are these true or false?

(i). All admissible heuristics are consistent.
(ii). All consistent heuristics are admissible.

(A) False, False
(B) False, True
(C) True, False
(D) True, True

Q12. Which of the following will return an optimal solution in case the search graph has negative edge-costs?

(A) Uniform cost search
(B) Graph search A* with consistent heuristic
(C) Both of these
(D) None of these

Q13. Consider the graph shown below and answer the next three questions based on it. In the graph, all nodes represent a state. A is the start state, and G is the goal state. The value of the heuristic function for each node is mentioned alongside. For example, the value of the heuristic at E is 1, and at C is 4, etc. Similarly the cost of transitioning from a state to another state is mentioned on the edges. For example, the cost of transitioning from B to D is 3 points.

Write down the order of nodes visited by A* graph search algorithm?

(A) A, C, D, E, G
(B) A, B, C, D, F, E, G
(C) A, B, D, F, C, E, G
(D) A, B, D, F, E, G

Answer:- (C) A, B, D, F, C, E, G