Using the figure below, determine the sequence that the nodes are expanded using

Question

Using the figure below, determine the sequence that the nodes are expanded using (a) breath first search, (b) depth first search, (c) uniform search, (d) greedy best first search, (e) iterative deepening, (f) A*. For each search strategy, Show the order in which nodes are expanded (i.e., to expand a node means that its children are generated), ending with the goal node that is found. Show the path from start to goal, or write "None". Give the cost of the path found. The first one is done for you as an example.

Explanation / Answer

Order of node expansion

Path Found

Cost of Path found

Depth First Search

S A C G B

S A C G

12

Uniform Cost

S A B C G

S A C G

12

Gready (Best-First) Search

S A B C G

S B G

17

Iterated Deepening Search

S A B C G

S B G

17

A* Search

S A B C G

S A C G

12

Depth first search can expand any children, suppose it expands A and goes on with their children.

Uniform costs expands the path with lowest cost first. So A, B first then chooses path from A as its cost is 4, explores c, now chooses path S B of cost 7, since S A C path cost is 8 and explore G. the search continues till all paths are explored, so expands again path S A C, and finds path of less cost =12.

Best first search picks the path with minimum heuristic cost. So first explore picks A, B. Now chooses to expnad A as its h value is 2 and explores C. Now B , C both have same heuristic value 3, it expands B arbitrarily and explores G.

Iterative deepening runs DFS at each level with increasing levels from 1, till we find goal node.

So at first level it explore A , B.. Now with level = 2 it agian runs DFS till height 2, starts from S and goes lke this S -> A -> C -> B ->G

Order of node expansion

Path Found

Cost of Path found

Depth First Search

S A C G B

S A C G

12

Uniform Cost

S A B C G

S A C G

12

Gready (Best-First) Search

S A B C G

S B G

17

Iterated Deepening Search

S A B C G

S B G

17

A* Search

S A B C G

S A C G

12

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.