a) Uniform cost search

States expanded:

Path returned:

b) Greedy search with the heuristic h1

States expanded:

Path returned:

c) A* search with heuristic h1

States expanded:

Path returned:

d) A* search with heuristics h2

States expanded:

Path returned:

e) Is h1 admissible or not? (Admissible means that h(N) Opt(N), where Opt(N) = optimal cost from N to goal.)

True

False

f) Is h2 admissible or not?

True

False

g) Is h1 consistent or not? (Consistent means that for all paths, h(N) - h(L) path(N,L).)

True

False

h) Is h2 consistent or not?

True

False

Informed Search and Heuristics For each of the following search algorithm, work out 1) the order in which states are expanded, and 2) the path returned by graph search. In all cases, ties are broken alphabetically. The start state is S. The goal state is G. Remember that in graph search, a state is expanded only once. How to answer: list states in a capital letter separated by a comma and no space (i.e., "S,A,C,G"). 7 Heuristics 1 A G 7 4 2 o in in un S h(s) h(A) h(B) h(C) h(G) 5 6 2 2 5.5 4 B 0