These are An Introduction to Artificial Intelligence Answers Week 3
Q1. The heuristic path algorithm is a best-first search in which f(n) = (2-w) g(n) + w h(n). Select the correct statement(s) – For w = 1, f(n) represents the A* algorithm. For w = 2, f(n) is complete. For w > 2, f(n) is optimal. For w = 0, f(n) represents UCS.
Answer: a, d For w = 1, f(n) represents the A* algorithm. For w = 0, f(n) represents UCS.
Q2. Consider f(n) = g(n) + 5h(n). What is the order of nodes visited by best-first search algorithm? (Start-node is S, no duplicate detection)
Answer: SAG
These are An Introduction to Artificial Intelligence Answers Week 3
Q3. Start state is a, and goal state is z. Cost of transitioning from one node to another are mentioned over the corresponding edge. Numbers on the node are the heuristic values. Assume successors are returned in reverse lexicographic order. In case of ties, use lexicographic ordering for breaking ties. For A* search with full duplicate detection, what is the order in which the nodes are visited?
Answer: acbfdez
Q4. If h is an admissible heuristic (non-negative), which of the following can never be an admissible heuristic? h+1 2h √h They all can be admissible under some situation
Answer: h+1
These are An Introduction to Artificial Intelligence Answers Week 3
Q5. If h1 and h2 are admissible heuristics, which of the following are guaranteed to be admissible? h1 + h2 min(h1, h2) max(h1, h2) αh1 + (1 – α)h2 for α є [0,1]
Answer: b, c, d min(h1, h2) max(h1, h2) αh1 + (1 – α)h2 for α є [0,1]
Q6. Which of the following statements are true? If a search graph has negative edge costs, Tree Search A* with Admissible Heuristics returns optimal solution. IDA* implementation does not need a priority queue, but A* does. If h1 and h2 are two admissible heuristics, then max(h1 , h2) dominates h1 and h2 An inconsistent heuristic can never be admissible. Depth First Search can never terminate faster than A* search with an admissible heuristic
Answer: b, c IDA* implementation does not need a priority queue, but A* does. If h1 and h2 are two admissible heuristics, then max(h1 , h2) dominates h1 and h2
These are An Introduction to Artificial Intelligence Answers Week 3
Q7. Which of the following is/are true regarding Depth-First Search Branch and Bound (DFS B&B) ? It is optimal even if the search space is infinite It performs well in practice when it is easy to find suboptimal solutions to the goal It can prune certain subtrees in the search tree without the need for exploring them It performs well in practice when there is a single solution to the goal
Answer: b, c It performs well in practice when it is easy to find suboptimal solutions to the goal It can prune certain subtrees in the search tree without the need for exploring them
Q8. Which of the following is/are true for problem relaxation in the context of computing heuristics? For a problem involving finding the shortest path in a city from a source to a destination, removing certain edges from the graph will give a relaxed problem Given an original problem P, we remove certain constraints from P to get a relaxed problem P1 which we solve optimally to compute an heuristic function h1 for P. We then remove additional constraints from P1 to get another relaxed problem P2 which we solve optimally to compute another heuristic function h2 for P, then h2 dominates h1 As we increase the number of constraints removed to get the relaxed problem the total time needed to solve the original problem (including computing the heuristic function) first decreases then increases Optimal solutions to relaxed problems give admissible heuristics to the original problem
These are An Introduction to Artificial Intelligence Answers Week 3
Q9. Which of the following is/are false regarding the A* search algorithm ? It always gives optimal solutions A* search algorithm has a better worst-case space time complexity than DFS if the heuristic used is admissible It is a systematic search algorithm It helps improve the worst-case time complexity of the search
Answer: a, c, d
These are An Introduction to Artificial Intelligence Answers Week 3
Q10. Which of the following evaluation functions will result in identical behavior to greedy best-first search (assume all edge costs are positive)? f(n) = 100 * h(n) f(n) = g(n) * h(n) f(n) = h(n)^2 f(n)=1/h(n)
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)
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.
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
These are An Introduction to Artificial Intelligence Answers Week 3
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
More Solutions of An Introduction to Artificial Intelligence: Click Here
