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 mode 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

Depth first search: order of node expansion path found cost

SACGB SACG 12

Uniform cost search: Order of node expansion path found cost

SACG=12,SBG=17 SACG 12

Iterative deepening: Orderof node expansion path found cost

SACG SACG 12

greedy best first search order of node expansion path found cost

S/4->A/4->C/4->G/0 SACG 12

A* search: values of h :-A:2,B:3,C:3,G:0

Expand s

{S,A}=4+2=6

{S,B}=7+3=10

Expand A

{S,A,C}=4+4+3=11

{S,B}=10

Expand b

{S,A,C}=11

{S,B,G}=7+10+0=17

Expand c

{S,A,C,G}=4+4+4=12

{S,B,G}=17

Path found:SACG cost:12

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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