An Introduction to Artificial Intelligence Week 3
Course Name: An Introduction to Artificial Intelligence
Course Link: Click Here
These are An Introduction to Artificial Intelligence Answers Week 3
Q1. Consider the undirected graph below. Cost for each edge is written adjacent to the edge. S is the start node and G is the goal node. The TREE-SEARCH version of A* SEARCH is performed on this undirected graph. Assume that the heuristic function h for a node is the least number of edges required to reach G from that node. For example, h(A) =2 since we can reach G from A by the path ABG. However, h(S) is defined as 0. Find the order of exploration of states. Ties are broken in the order GSABC.
(Write the answer as a capitalized string with no spaces. For example, if the order of exploration is A followed by B followed by A followed by D then write ABAD. Include the goal state in the answer)
Answer: SASBG
These are An Introduction to Artificial Intelligence Answers Week 3
Q2. Which of the following evaluation functions will result in identical behaviour to greedy best-first search (assume all edge costs are positive)?
a.f(n) = 100 * h(n)
b. f(n) = g(n) * h(n)
c. f(n) = h(n)^2
d. f(n) = 1 / h(n)
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 3
Q3. 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)=8, h(B)=7, h(C)=6, h(D)=5, h(E)=4, h(F)=2, h(G)=0}:
Which of the following is correct regarding heuristic function h?
a. It is admissible
b. It is not admissible
c. It is consistent
d. It is not consistent
Answer: a, d
These are An Introduction to Artificial Intelligence Answers Week 3
Q4. Which of the following statements are true (assume all edge costs are positive)?
a. h(n) = 0 is always a consistent heuristic function
b. Manhattan distance is an admissible heuristic for the problem of moving a rook from any square on a chessboard to another square in the smallest number of moves
c. Depth First Search can never terminate faster than A* search with an admissible heuristic
d. Straight line distance is an admissible heuristic for the problem of moving from one city to another by covering the smallest distance
Answer: a, d
These are An Introduction to Artificial Intelligence Answers Week 3
Q5. In the directed graph given below, with edge weights as cost of those edges, and heuristic values of node written in red, TREE-SEARCH A* search is performed on the graph with the starting node “0” and one goal node “4” (node numbers are written inside the nodes). Consider the two sub cases: a) ties in selecting node for expansion from the fringe are resolved by choosing the node with the LARGER index b) ties in selecting node for expansion from the fringe are resolved by choosing the node with the SMALLER index. Which of the following are correct statements?
a. In the first case, 5 node expansions are performed in the search.
b. In the second case, node with the index 7 is expanded twice.
c. The cost of path to the goal is different in the above two cases.
d. Number of nodes in the optimal path from the start node to the goal is same for both the cases above.
Answer: a, b
These are An Introduction to Artificial Intelligence Answers Week 3
Q6. Which of the following is(are) correct?
a. An inadmissible heuristic might be consistent.
b. An inconsistent heuristic might be admissible.
c. If the heuristic is consistent, A* using TREE-SEARCH is optimal.
d. If the heuristic is consistent, A* using GRAPH-SEARCH is optimal.
Answer: b, c, d
These are An Introduction to Artificial Intelligence Answers Week 3
Q7. Consider the following directed graph.
The heuristic function for the nodes is defined as h(A) = 15, h(B) = 10, h(C) = 12, h(D) = 7, h(E) = 10, h(F) = 6, h(G) = 4, h(H) = 0. The start node is A and the goal node is H. Assume that ties in selecting node for expansion from the fringe are resolved by choosing the alphabetically smaller node. Which of the following statements are correct?
a. The optimal path has cost 10.
b. GRAPH-SEARCH A* results in a path with optimal cost.
c. TREE-SEARCH A* results in a path with optimal cost.
d. The heuristic is admissible.
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 3
Q8. Suppose there are two admissible heuristics h1 and h2 for some problem, which of the following are correct?
a. max(h1,h2) is an admissible heuristic.
b. max(h1,h2) dominates h1 and h2
c. min(h1,h2) is an admissible heuristic.
d. min(h1,h2) dominates h1 and h2
Answer: a, b, c
Q9. Which of the following algorithms are guaranteed to be complete and optimal? (Assume positive edge costs greater than 1)
a. Depth-first search
b. GRAPH-SEARCH A* with zero heuristic
c. Uniform Cost Search
d. GRAPH-SEARCH A* with admissible heuristic
Answer: b, c
These are An Introduction to Artificial Intelligence Answers Week 3
Q10. We want to sort an array of n distinct integers using A* search. The start state is a random permutation of the integers. The expansion function applied on a given state yields all permutations that can be achieved by swapping one pair of different numbers in the original state with all edge costs as 1. There is one goal state: the sorted array. Let S(p) be the number of elements of the array p that are not in the position they are supposed to be in the sorted array. Which of the following are admissible heuristics for this problem?
a. S(p)
b. S(p)/2
c. S(p)/3
d. 0
Answer: b, c, d
These are An Introduction to Artificial Intelligence Answers Week 3
These are An Introduction to Artificial Intelligence Answers Week 3
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.