Principles of Artificial Intelligence
Tutorial-I (Uninformed and Informed Search)
Problem Statement - 1
Each of the trees (G1 through G4) was generated by searching the graph (Figure 1) with
agraph searchalgorithm. Assume children of a node are visited in alphabetical order. Each
tree showsonly the nodes that have been expanded. Numbers next to nodes indicate the
relevant “score” used by the algorithm’s priority queue. The start state is A, and the goal state
is G.
Assume that the following two heuristics may be used in case of heuristic based search.
H1: heuristic 1 = {h(A) = 3, h(B) = 6, h(C) = 4, h(D) = 3}
H2: heuristic 2 = {h(A) = 3, h(B) = 3, h(C) = 0, h(D) = 2}
Figure 1
Q1. Which of the following set of trees are not ensuring the optimality of path obtained?
a) G1,G2
b) G3,G4
c) G2,G3
d) G1,G4
Answer: a, c, d
Q2. Which of the following sentences are not true?
a) The tree G1 is generated using Best First Search.
b) The tree G2 is generated using Depth First Search.
c) The tree G3 is generated using Uniform Cost Search.
d) The tree G4 is generated using A* Search.
Answer:a, c, d
Problem Statement 2
Execute Tree Search through this graph (i.e., do not remember visited nodes). Step costs are
given next to each arc, and heuristic values are given next to each node (as h=x). The
successors of each node are indicated by the arrows out of that node. Successors are returned
in left-to-right order. The start node is S and there are two goal nodes G1 and G2. For each
strategy below report the order in which nodes are expanded and path along with cost that is
obtained.
(i) Depth First Search
(ii) Breadth First Search
(iii) Depth First with Iterative Deepening
(iv) A* Search
Depth First Search: Order of expansion: S A A A A A A…
Path to goal found: None
Cost of path found: None
(ii) Breadth-First Search: Order of expansion: S A B C (G1)
Path to goal: S C G1 Cost of path found: 56
(iii) Iterative Deepening Search: Order of expansion: S S A B C (G1)
Path to goal found: S C G1
Cost of path found: 56
(iv) A * Search: Order of expansion: S A B D C G2
Path to goal found: S A B C G2
Cost of path found: 22
3. You are executing tree search through the graph given below. The start node is S, and
the goal node is G. Actual step costs are shown next to each link. Heuristics are given in
the following table where h* is the true (= optimal) heuristic; here, hi are various other
heuristics.
Which heuristic functions is admissible and consistent both among h1, h2 and h3 and
why? Justify your answer.
h1 is not admissible because h1(C) > h* .
Only h2 and h3 are admissible.
h1 is not consistent because h1 is not admissible.
OR at node F, h1(C) – h1(F) ≤ c(C, F) 5 – 1 ≤ 3 4 ≰ 3, hence, h1 is not consistent.
h2 is not consistent because at node D, h2(S) – h2(D) ≤ c(S, D)
5 – 1 ≤ 3 4 ≰ 3, At node D, h2(B) – h2(D) ≤ c(B, D) 4 – 1 ≤ 1 3 ≰ 1,
hence, h2 is not consistent.
h3 is consistent•
